python实现bitmap数据结构详解-Python教程-PHP中文网

首页

后端开发

Python教程

python实现bitmap数据结构详解

WBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWB

Jun 16, 2016 am 08:45 AM

bitmap 数据结构

bitmap是很常用的数据结构，比如用于Bloom Filter中；用于无重复整数的排序等等。bitmap通常基于数组来实现，数组中每个元素可以看成是一系列二进制数，所有元素组成更大的二进制集合。对于Python来说，整数类型默认是有符号类型，所以一个整数的可用位数为31位。

bitmap实现思路

bitmap是用于对每一位进行操作。举例来说，一个Python数组包含4个32位有符号整型，则总共可用位为4 * 31 = 124位。如果要在第90个二进制位上操作，则要先获取到操作数组的第几个元素，再获取相应的位索引，然后执行操作。

python实现bitmap数据结构详解

上图所示为一个32位整型，在Python中默认是有符号类型，最高位为符号位，bitmap不能使用它。左边是高位，右边是低位，最低位为第0位。

bitmap是用于对每一位进行操作。举例来说，一个Python数组包含4个32位有符号整型，则总共可用位为4 * 31 = 124位。如果要在第90个二进制位上操作，则要先获取到操作数组的第几个元素，再获取相应的位索引，然后执行操作。

初始化bitmap

首先需要初始化bitmap。拿90这个整数来说，因为单个整型只能使用31位，所以90除以31并向上取整则可得知需要几个数组元素。代码如下：

复制代码代码如下:

#!/usr/bin/env python
#coding: utf8

class Bitmap(object):
def __init__(self, max):
self.size = int((max + 31 - 1) / 31) #向上取整

if __name__ == '__main__':
bitmap = Bitmap(90)
print '需要 %d 个元素。' % bitmap.size

复制代码代码如下:

$ python bitmap.py
需要 3 个元素。

计算在数组中的索引

计算在数组中的索引其实是跟之前计算数组大小是一样的。只不过之前是对最大数计算，现在换成任一需要存储的整数。但是有一点不同，计算在数组中的索引是向下取整，所以需要修改calcElemIndex方法的实现。代码改为如下：

复制代码代码如下:

#!/usr/bin/env python
#coding: utf8

class Bitmap(object):
def __init__(self, max):
self.size = self.calcElemIndex(max, True)
self.array = [0 for i in range(self.size)]

def calcElemIndex(self, num, up=False):
  '''up为True则为向上取整, 否则为向下取整'''
  if up:
   return int((num + 31 - 1) / 31) #向上取整
  return num / 31

if __name__ == '__main__':
bitmap = Bitmap(90)
print '数组需要 %d 个元素。' % bitmap.size
print '47 应存储在第 %d 个数组元素上。' % bitmap.calcElemIndex(47)

复制代码代码如下:

$ python bitmap.py
数组需要 3 个元素。
47 应存储在第 1 个数组元素上。

所以获取最大整数很重要，否则有可能创建的数组容纳不下某些数据。

计算在数组元素中的位索引

数组元素中的位索引可以通过取模运算来得到。令需存储的整数跟31取模即可得到位索引。代码改为如下：

复制代码代码如下:

#!/usr/bin/env python
#coding: utf8

class Bitmap(object):
def __init__(self, max):
self.size = self.calcElemIndex(max, True)
self.array = [0 for i in range(self.size)]

def calcElemIndex(self, num, up=False):
  '''up为True则为向上取整, 否则为向下取整'''
  if up:
   return int((num + 31 - 1) / 31) #向上取整
  return num / 31

def calcBitIndex(self, num):
return num % 31

if __name__ == '__main__':
bitmap = Bitmap(90)
print '数组需要 %d 个元素。' % bitmap.size
print '47 应存储在第 %d 个数组元素上。' % bitmap.calcElemIndex(47)
print '47 应存储在第 %d 个数组元素的第 %d 位上。' % (bitmap.calcElemIndex(47), bitmap.calcBitIndex(47),)

别忘了是从第0位算起哦。

置1操作

二进制位默认是0，将某位置1则表示在此位存储了数据。代码改为如下：

复制代码代码如下:

#!/usr/bin/env python
#coding: utf8

class Bitmap(object):
def __init__(self, max):
self.size = self.calcElemIndex(max, True)
self.array = [0 for i in range(self.size)]

def calcElemIndex(self, num, up=False):
  '''up为True则为向上取整, 否则为向下取整'''
  if up:
   return int((num + 31 - 1) / 31) #向上取整
  return num / 31

def calcBitIndex(self, num):
return num % 31

def set(self, num):
  elemIndex = self.calcElemIndex(num)
  byteIndex = self.calcBitIndex(num)
  elem      = self.array[elemIndex]
  self.array[elemIndex] = elem | (1

if __name__ == '__main__':
bitmap = Bitmap(90)
bitmap.set(0)
print bitmap.array

因为从第0位算起，所以如需要存储0，则需要把第0位置1。

清0操作

将某位置0，也即丢弃已存储的数据。代码如下：

复制代码代码如下:

#!/usr/bin/env python
#coding: utf8

class Bitmap(object):
def __init__(self, max):
self.size = self.calcElemIndex(max, True)
self.array = [0 for i in range(self.size)]

def calcElemIndex(self, num, up=False):
  '''up为True则为向上取整, 否则为向下取整'''
  if up:
   return int((num + 31 - 1) / 31) #向上取整
  return num / 31

def calcBitIndex(self, num):
return num % 31

def set(self, num):
  elemIndex = self.calcElemIndex(num)
  byteIndex = self.calcBitIndex(num)
  elem      = self.array[elemIndex]
  self.array[elemIndex] = elem | (1

def clean(self, i):
  elemIndex = self.calcElemIndex(i)
  byteIndex = self.calcBitIndex(i)
  elem      = self.array[elemIndex]
  self.array[elemIndex] = elem & (~(1

if __name__ == '__main__':
bitmap = Bitmap(87)
bitmap.set(0)
bitmap.set(34)
print bitmap.array
bitmap.clean(0)
print bitmap.array
bitmap.clean(34)
print bitmap.array

清0和置1是互反操作。

测试某位是否为1

判断某位是否为1是为了取出之前所存储的数据。代码如下：

复制代码代码如下:

#!/usr/bin/env python
#coding: utf8

class Bitmap(object):
def __init__(self, max):
self.size = self.calcElemIndex(max, True)
self.array = [0 for i in range(self.size)]

def calcElemIndex(self, num, up=False):
  '''up为True则为向上取整, 否则为向下取整'''
  if up:
   return int((num + 31 - 1) / 31) #向上取整
  return num / 31

def calcBitIndex(self, num):
return num % 31

def set(self, num):
  elemIndex = self.calcElemIndex(num)
  byteIndex = self.calcBitIndex(num)
  elem      = self.array[elemIndex]
  self.array[elemIndex] = elem | (1

def clean(self, i):
  elemIndex = self.calcElemIndex(i)
  byteIndex = self.calcBitIndex(i)
  elem      = self.array[elemIndex]
  self.array[elemIndex] = elem & (~(1

def test(self, i):
  elemIndex = self.calcElemIndex(i)
  byteIndex = self.calcBitIndex(i)
  if self.array[elemIndex] & (1    return True
  return False

if __name__ == '__main__':
bitmap = Bitmap(90)
bitmap.set(0)
print bitmap.array
print bitmap.test(0)
bitmap.set(1)
print bitmap.test(1)
print bitmap.test(2)
bitmap.clean(1)
print bitmap.test(1)

复制代码代码如下:

$ python bitmap.py
[1, 0, 0]
True
True
False
False

接下来实现一个不重复数组的排序。已知一个无序非负整数数组的最大元素为879，请对其自然排序。代码如下：

复制代码代码如下:

#!/usr/bin/env python
#coding: utf8

class Bitmap(object):
def __init__(self, max):
self.size = self.calcElemIndex(max, True)
self.array = [0 for i in range(self.size)]

def calcElemIndex(self, num, up=False):
  '''up为True则为向上取整, 否则为向下取整'''
  if up:
   return int((num + 31 - 1) / 31) #向上取整
  return num / 31

def calcBitIndex(self, num):
return num % 31

def set(self, num):
  elemIndex = self.calcElemIndex(num)
  byteIndex = self.calcBitIndex(num)
  elem      = self.array[elemIndex]
  self.array[elemIndex] = elem | (1

def clean(self, i):
  elemIndex = self.calcElemIndex(i)
  byteIndex = self.calcBitIndex(i)
  elem      = self.array[elemIndex]
  self.array[elemIndex] = elem & (~(1

def test(self, i):
  elemIndex = self.calcElemIndex(i)
  byteIndex = self.calcBitIndex(i)
  if self.array[elemIndex] & (1    return True
  return False

if __name__ == '__main__':
MAX = 879
suffle_array = [45, 2, 78, 35, 67, 90, 879, 0, 340, 123, 46]
result       = []
bitmap = Bitmap(MAX)
for num in suffle_array:
  bitmap.set(num)

for i in range(MAX + 1):
  if bitmap.test(i):
   result.append(i)

print '原始数组为: %s' % suffle_array
print '排序后的数组为: %s' % result

bitmap实现了，则利用其进行排序就非常简单了。其它语言也同样可以实现bitmap，但对于静态类型语言来说，比如C/Golang这样的语言，因为可以直接声明无符号整型，所以可用位就变成32位，只需将上述代码中的31改成32即可，这点请大家注意。

本站声明

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系admin@php.cn

热AI工具

Undresser.AI Undress

人工智能驱动的应用程序，用于创建逼真的裸体照片

AI Clothes Remover

用于从照片中去除衣服的在线人工智能工具。

Undress AI Tool

免费脱衣服图片

Clothoff.io

AI脱衣机

Video Face Swap

使用我们完全免费的人工智能换脸工具轻松在任何视频中换脸！

显示更多

热工具

记事本++7.3.1

好用且免费的代码编辑器

SublimeText3汉化版

中文版，非常好用

禅工作室 13.0.1

功能强大的PHP集成开发环境

Dreamweaver CS6

视觉化网页开发工具

SublimeText3 Mac版

神级代码编辑软件(SublimeText3)

显示更多

热门话题

gmail邮箱登陆入口在哪里

7622

CakePHP 教程

1389

steam的账户名称是什么格式

win11激活密钥永久

NYT连接提示和答案

138

显示更多

Related knowledge

使用Java函数比较进行复杂数据结构比较 Apr 19, 2024 pm 10:24 PM

Java中比较复杂数据结构时，使用Comparator提供灵活的比较机制。具体步骤包括：定义比较器类，重写compare方法定义比较逻辑。创建比较器实例。使用Collections.sort方法，传入集合和比较器实例。

Java数据结构与算法：深入详解 May 08, 2024 pm 10:12 PM

数据结构和算法是Java开发的基础，本文深入探讨Java中的关键数据结构（如数组、链表、树等）和算法（如排序、搜索、图算法等）。这些结构通过实战案例进行说明，包括使用数组存储分数、使用链表管理购物清单、使用栈实现递归、使用队列同步线程以及使用树和哈希表进行快速搜索和身份验证等。理解这些概念可以编写高效且可维护的Java代码。

深入了解Go语言中的引用类型 Feb 21, 2024 pm 11:36 PM

引用类型在Go语言中是一种特殊的数据类型，它们的值并非直接存储数据本身，而是存储数据的地址。在Go语言中，引用类型包括slices、maps、channels和指针。深入了解引用类型对于理解Go语言的内存管理和数据传递方式至关重要。本文将结合具体的代码示例，介绍Go语言中引用类型的特点和使用方法。1.切片（Slices）切片是Go语言中最常用的引用类型之一

PHP数据结构：AVL树的平衡之道，维持高效有序的数据结构 Jun 03, 2024 am 09:58 AM

AVL树是一种平衡二叉搜索树，确保快速高效的数据操作。为了实现平衡，它执行左旋和右旋操作，调整违反平衡的子树。AVL树利用高度平衡，确保树的高度相对于节点数始终较小，从而实现对数时间复杂度(O(logn))的查找操作，即使在大型数据集上也能保持数据结构的效率。

Java集合框架全解析：解剖数据结构，揭秘高效存储之道 Feb 23, 2024 am 10:49 AM

Java集合框架概述Java集合框架是Java编程语言的重要组成部分，它提供了一系列可以存储和管理数据的容器类库。这些容器类库具有不同的数据结构，可以满足不同场景下的数据存储和处理需求。集合框架的优势在于它提供了统一的接口，使得开发人员可以使用相同的方式来操作不同的容器类库，从而降低了开发难度。Java集合框架的数据结构Java集合框架中包含多种数据结构，每种数据结构都有其独特的特性和适用场景。下面是几种常见的Java集合框架数据结构：1.List：List是一个有序的集合，它允许元素重复。Li

PHP SPL 数据结构：为你的项目注入速度和灵活性 Feb 19, 2024 pm 11:00 PM

PHPSPL数据结构库概述PHPSPL（标准php库）数据结构库包含一组类和接口，用于存储和操作各种数据结构。这些数据结构包括数组、链表、栈、队列和集合，每个数据结构都提供了一组特定的方法和属性，用于操纵数据。数组在PHP中，数组是存储一系列元素的有序集合。SPL数组类提供了对原生的PHP数组进行加强的功能，包括排序、过滤和映射。以下是使用SPL数组类的一个示例：useSplArrayObject;$array=newArrayObject(["foo","bar","baz"]);$array

基于哈希表的数据结构优化PHP数组交集和并集的计算 May 02, 2024 pm 12:06 PM

利用哈希表可优化PHP数组交集和并集计算，将时间复杂度从O(n*m)降低到O(n+m)，具体步骤如下：使用哈希表将第一个数组的元素映射到布尔值，以快速查找第二个数组中元素是否存在，提高交集计算效率。使用哈希表将第一个数组的元素标记为存在，然后逐个添加第二个数组的元素，忽略已存在的元素，提高并集计算效率。

深入学习Go语言数据结构的奥秘 Mar 29, 2024 pm 12:42 PM

深入学习Go语言数据结构的奥秘，需要具体代码示例Go语言作为一门简洁、高效的编程语言，在处理数据结构方面也展现出了其独特的魅力。数据结构是计算机科学中的基础概念，它旨在组织和管理数据，使得数据能够更有效地被访问和操作。通过深入学习Go语言数据结构的奥秘，我们可以更好地理解数据的存储方式和操作方法，从而提高编程效率和代码质量。一、数组数组是最简单的数据结构之一

See all articles

python实现bitmap数据结构详解

热AI工具

Undresser.AI Undress

AI Clothes Remover

Undress AI Tool

Clothoff.io

Video Face Swap

热门文章

热工具

记事本++7.3.1

SublimeText3汉化版

禅工作室 13.0.1

Dreamweaver CS6

SublimeText3 Mac版

热门话题