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


需求描述

有40亿个整数,再给一个新的整数,需要判断新的整数是否在40亿个整数中,你会怎么做?

解决方案

思考:整数32位,这个存储整数的Set需要多大?

一个整数4个字节,40亿个整数160亿字节,将近16G的内存

问题是,如果我只有2G的内存,该怎么办呢?

分8次加载?那样的话会很慢的,从磁盘加载数据是磁盘io操作,是非常慢的,每次都要加载这么大的数据,还要8次,估计找一个数的时间可以达到分钟甚至小时级了。

8台机器分别计算,最终汇总结果,一次性读入数据,查找很快。

这样做的话,因为每台机器都可以一次性把数据读入内存,在比较的时候不用来回加载数据了,所以可以节省加载数据的开销。

32位int的范围,总共就是2的32次方,大概42亿多点。所以可以申请2的32次方个位。把整个整数范围都覆盖了。

1代表第一个位,2代表第二个位,2的32次方代表最后一个位。40亿个数中,存在的数就在相应的位置1,其他位就是0。

比如来了一个新的数1234,就找一下第1234位,如果是1就存在,是0就不存在。

这样的话,需要多大内存呢?

2的32次方个位,相当于2的29次方个字节,500多MB,节省了不少内存。

思考一下,32位int的范围是42亿,40亿整数中肯定有一些是连续的,可以先对数据进行一个外部排序,然后用一个初始的数和一个长度构成一个数据结构,来表示一段连续的数,举例:

如果数据是1 2 3 4 6 7……这种的,那么可以用(1,4)和(6,2)来表示,这样一来,连续的数都变成了2个数表示。

来了一个新数之后,就用二分法进行查找了。

这样一来,最差情况就是2亿多的断点,也就是2亿多的结构体,每个结构体8个字节,大概16亿字节,1.6GB,在内存中可以放下。