2019-05-25

位图法总结

缘起

位图法是桶排序思想的延伸. 比如我们想知道 200以内的正整数某个元素，例如163，是否存在, 我们需要

int flag[200], flag[163]=1表示存在, 0表示不存在. 即需要 200*4=800字节的桶才能维护这样的状态. 或者至少

bool flag[200], 即 200字节维护这一状态. 但是如果使用位图思想——它精简到使用一个bit来记录某个正整数的状态. 例如163, 163/8=20…3 即第20字节的第3个比特的状态就可以刻画163. 所以使用位图思想的话, 只需要200/8=25字节就足够了.

位图思想使用1个比特位表示一个状态，算法的精简性适用于海量数据，但数据状态又不是很多的情况。通常是用来判断某个数据存不存在的。

分析

位图法常见的应用场景

Q: 40亿个不重复的unsigned int的整数，没排过序的，然后再给一个数，如何快速判断这个数是否在那40亿个数当中

A: 40亿比特=476.8 MB，所以只需要申请512MB内存, 就可以使用位图法维护这40亿个数字的状态. 读入这40亿数字, 修改比特的状态. 然后读取要找的数字, 就知道该数字是否在这个数组中了
Q: 使用位图法判断整形数组是否存在重复.

A: 本质上就是桶排序思想, 只是使用位图维护状态，而不是使用整型数组或者bool数组.
Q: 使用位图法进行整形数组排序(这些数不允许重复，这是位图法的前提，不然就不能使用1个比特位刻画该整数的状态了)

A: 本质就是桶排序. 只是使用位图维护状态，而不是使用整型数组或者bool数组.
Q: 在2.5亿个整数中找出不重复的整数，注，所给内存不足以容纳这2.5亿个整数(也就是说，所给内存<2.510^832bit=2.510^84Byte=10^9Byte约为953.67MB)

A: 使用位图法, 而且使用2个比特位刻画一个整数的状态, 2个零比特位（这就是前面说的，位图法的要以是每个元素不重复出现或者状态有限个——可以使用有限个比特位刻画清楚），即00表示不曾出现，01表示出现1次, 10表示出现多次, 11无意义. 则只需要2.510^8\2/8/1024/1024=60MB内存即可! 或者用两张bitmap就是,每一张bitmap都是普通的bitmap,即1bit表示一个数,然后，如果出现一次,就在第一张bitmap相应位置置1,如果出现了2次及以上，就在第二张bitmap相应位置处置1,若一次都没有出现，则第一张bitmap相应位置处都置0.（个人偏好是用2张bitmap,比2-bitmap好，因为时间、空间复杂度是一样的,但是更好理解）
数组中寻找第K小的数—-位图法（bitmap)
算法就是用位图将这些数（这些数不允许重复，这是位图法的前提）存储起来.然后从左到右读取，读到的第K个就是第K大的元素,这种算法很快，就不写代码了
Q: 求两个数组的交集

A: 用两位图，然后对两位图进行按位与运算，可得两数组的交集
编程珠玑中的问题:

Q: 输入：一个最多包含n个正整数的文件，每个数都小于n，其中n=10^7(一千万)。如果在输入文件中有任何正数重复出现就是致命错误。没有其他数据与该正数相关联。
输出：按升序排列的输入正数的列表。

约束：最多有1MB的内存空间可用，有充足的磁盘存储空间可用。运行时间最多几分钟，运行时间为10秒就不需要进一步优化。

A: 使用位图法的话,

10^7/8/1024/1024 = 1.1920928955078 MB > 1MB

所以分两次即可. 第一次读取 [1,500w]之间的整数, 因为不能重复, 所以最多占用

1.1920928955078 MB /2 =0.5960464477539 MB 内存. 不会导致内存溢出.

然后使用位图法进行桶排序. 输出到屏幕或者指定输出文件. 第二次读取 [500w, 1000w]之间的整数, 同理处理, 则完毕之后, 就排完了序. 只需要进行2次文件IO. 位图法效率还是不错的. 本质是因为不需要使用8比特来刻画一个数的状态，只需要1比特就够了. 也就是位图法比一般的数组表示法至少节省8倍的空间.