如何判断一个数是否在40亿个整数中——bitmap

旧城等待， 2022-02-21 14:00 343阅读 0赞

【题目】  
如何判断一个数是否在40亿个整数中。

【方法】  
方法一：如果用set存储。时间可以达到秒级  
整数是32位，1个整数4个字节，40亿个数，为160亿个字节约16G.  
如果机器是2G，一次加载不完，需要分8次加载。  
如果给一批机器，可以用分布式算法。把数据分散在8台机器上，然后来一个新的数据，8台机器一起找，最后再汇总结果就行了。

方法二：bitmap。时间可以达到毫秒级  
判断一个数在不在，用2个状态表示，可以用一个位来代表。  
申请2^32个位 1代表第1个位，2代表第2个位，…… 2^32代表最后一位。  
40亿个数中，存在的数相应位置为1，其他是0.  
![在这里插入图片描述][20190411090307656.png]  
第五位为0，代表5没有。  
2^32 个位相当于2^29个字节 约500M

**思路整理：**  
32位int的范围是42亿，40亿整数中肯定有一些是连续的，我们可以先对数据进行一个外部排序，然后用一个初始的数和一个长度构成一个数据结构，来表示一段连续的数，举个例子。  
如果数据是1 2 3 4 6 7……这种的，那么可以用(1,4)和(6,2)来表示，这样一来，连续的数都变成了2个数表示。  
![在这里插入图片描述][20190411090322491.png]  
来了一个新数之后，就用二分法进行查找了。  
这样一来，最差情况就是2亿多的断点，也就是2亿多的结构体，每个结构体8个字节，大概16亿字节，1.6GB，在内存中可以放下。

**Bitmap （位图法）**  
用每一位来存放某种状态，适用于大规模数据，但数据状态又不是很多的情况。通常是用来判断某个数据存不存在的。

**应用**  
1、给40亿个不重复的unsigned int的整数，没排过序的，然后再给一个数，如何快速判断这个数是否在那40亿个数当中  
　　首先，将这40亿个数字存储到bitmap中，然后对于给出的数，判断是否在bitmap中即可。  
2、使用位图法判断整形数组是否存在重复  
遍历数组，一个一个放入bitmap，并且检查其是否在bitmap中出现过，如果没出现放入，否则即为重复的元素。  
3、使用位图法进行整形数组排序  
首先遍历数组，得到数组的最大最小值，然后根据这个最大最小值来缩小bitmap的范围。这里需要注意对于int的负数，都要转化为unsigned int来处理，而且取位的时候，数字要减去最小值。  
4、在2.5亿个整数中找出不重复的整数，注，内存不足以容纳这2.5亿个整数  
参 考的一个方法是：采用2-Bitmap（每个数分配2bit，00表示不存在，01表示出现一次，10表示多次，11无意义）。其实，这里可以使用两个普 通的Bitmap，即第一个Bitmap存储的是整数是否出现，如果再次出现，则在第二个Bitmap中设置即可。这样的话，就可以使用简单的1- Bitmap了。

参考：[https://mp.weixin.qq.com/s/M-9OXISosrqRI08QIDJiPA][https_mp.weixin.qq.com_s_M-9OXISosrqRI08QIDJiPA]

[20190411090307656.png]: /images/20220221/2339abc529f244bf85b66d237c23dcb7.png
[20190411090322491.png]: /images/20220221/8c603ea1aa9346fc96d587a1de3e9c50.png
[https_mp.weixin.qq.com_s_M-9OXISosrqRI08QIDJiPA]: https://mp.weixin.qq.com/s/M-9OXISosrqRI08QIDJiPA