Python | BitMap算法及其实现
2021/7/7 22:38:15
本文主要是介绍Python | BitMap算法及其实现,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
BitMap概述
本文介绍 BitMap 算法的应用背景,算法思想和相关实现细节。
概括而言,BitMap 主要用来解决海量数据中元素查询,去重、以及排序等问题。这里对海量数据场景的强调,似乎暗示了这个算法对空间的利用相当的精巧和经济,事实确实如此。
BitMap算法
本来数据序列的排序是一个平凡的任务,现有的多种排序算法,都有各自擅场能适应不同情形的具体要求。但我们考虑这样一个场景:有一台内存为 4 GB 的 PC,其硬盘中的一个存储了 30 亿个无符号整型数据文件,这些整数一行一个且无重复。现在需要我们对这个文件中的数据进行排序后输出。
简单计算不难得到,这个数据文件的大小为 \(4⋅3⋅10^9/2^{30}\) 约为 11.2 GB,显然将这个数据文件直接读入内存是办不到的。能否强行利用现有的内存 size 来存储这些数据呢?答案是可能的,此时 BitMap 算法就该 C 位亮相了。BitMap 的想法相当精妙,它对整型数据作了一种转化,使得这个办不到的存储成为可能。我们这里忽略不同语言的设定,假设一个 int 整数占 4 个字节,即32 bit,如果我们能用一个 bit 位来标示一个 int 整数,那么需要的存储空间将大大减少,估算一下可知,30亿个整数需要的内存空间为 \(4⋅3⋅10^9/8/2^{20}\) 大概为 357.6 MB,这样,我们可以轻易将这 30 亿个 int 数放到内存中进行处理。
具体而言,BitMap 对数据的转化可简述如下:
一个整型 int 占 4 bytes,共32位,我们申请一个 int 长度为 N//32 + 1 的数组,即可存储完这些数据,其中 N 表示要进行查找的最大整数,这可以经读取遍历一轮数据获得。通过数组中的每个元素在内存在占 32 位对应表示十进制数 0-31,故可得到 BitMap 表:
array[0] 可表示 0-31
array[1] 可表示 32-63
array[2] 可表示 64-95
...
下面就只剩下如何将十进制数转换为对应的二进制 bit 位,实现以 1 当 32 的效果,显然,这部分实现只需用到一些位运算操作,具体细节见下面的代码示例。不难看出,Bitmap 排序需要的时间复杂度和空间复杂度依赖于数据中最大的数字。
代码实现
from array import array class BitMap: def __init__(self): self.n = 5 self.bitsize = 1 << self.n self.typecode = 'I' # 32位unsighed整型 self.lowerbound = 0 # 若数组中有负数,则所有数都减去最小的那个负数 @staticmethod def greater_power2n(x): i = 1 while True: y = x >> i x |= y if y == 0: break i <<= 1 return x + 1 def load(self, inp): ''' 一般情形,数据应该是流式读取,这里简化起见不失一般性,将数据直接全部读完 ''' mini = min(inp) if mini < 0: self.lowerbound = -mini # 如果数组中有<0的数,则所有数都要减去最小的那个负数 inp = [i + self.lowerbound for i in inp] maxi = max(inp) num_arr = max(self.greater_power2n(maxi) >> self.n, 1) # 至少应该使用一个数组 self.arr = array(self.typecode, [0] * num_arr) for x in inp: self._set(x) def _set(self, x, set_val=True): ''' 将x在数组中对应元置为1 ''' arr_idx = x >> self.n # 元素在第几个数组中,等价于x // 2**self.n bit_idx = x & (self.bitsize - 1) # 元素在相应数组中的第几个bit位,等价于x % 2**self.n if set_val: self.arr[arr_idx] |= 1 << bit_idx else: self.arr[arr_idx] &= ~(1 << bit_idx) def search(self, x): if self.lowerbound != 0: x += self.lowerbound arr_idx = x >> self.n bit_idx = x & (self.bitsize - 1) existence = True if self.arr[arr_idx] & (1 << bit_idx) else False return existence def sort(self): sorted_seq = [] for arr_idx, a in enumerate(self.arr): for bit_idx in range(self.bitsize): if a & (1 << bit_idx): sorted_seq.append(arr_idx * self.bitsize + bit_idx - self.lowerbound) return sorted_seq def show_bitmap(self): for i, a in enumerate(self.arr): print('The {}th array elements: {:032b}'.format(i, a))
运行测试
>>> bitmap = BitMap() >>> bitmap.load([-3, 2, 56, -34, 40, 21, 99, 25]) >>> bitmap.search(21), bitmap.search(3) (True, False) >>> bitmap.sort() [-34, -3, 2, 21, 25, 40, 56, 99]
参考资料
黑胡同里の猫,详解BitMap算法,https://www.520mwx.com/view/59057
位图算法及其实现,BitMap,https://www.pythonf.cn/read/84436
这篇关于Python | BitMap算法及其实现的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-12-24Python编程入门指南
- 2024-12-24Python编程基础入门
- 2024-12-24Python编程基础:变量与数据类型
- 2024-12-23使用python部署一个usdt合约,部署自己的usdt稳定币
- 2024-12-20Python编程入门指南
- 2024-12-20Python编程基础与进阶
- 2024-12-19Python基础编程教程
- 2024-12-19python 文件的后缀名是什么 怎么运行一个python文件?-icode9专业技术文章分享
- 2024-12-19使用python 把docx转为pdf文件有哪些方法?-icode9专业技术文章分享
- 2024-12-19python怎么更换换pip的源镜像?-icode9专业技术文章分享