处理大数据的算法

Published: 10 Oct 2015 Category: algorithm

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

方案1:申请512M的内存(2^32/8=512MB),一个bit位代表一个unsigned int值。读入40亿个数,设置相应的bit位,读入要查询的数,查看相应bit位是否为1,为1表示存在,为0表示不存在。

方案2:因为2^32为40亿多,所以给定一个数可能在,也可能不在其中;这里我们把40亿个数中的每一个用32位的二进制来表示假设这40亿个数开始放在一个文件中。

然后将这40亿个数分成两类: 1. 最高位为0 2. 最高位为1

并将这两类分别写入到两个文件中,其中一个文件中数的个数<=20亿,而另一个>=20亿(这相当于折半了);与要查找的数的最高位比较并接着进入相应的文件再查找

再然后把这个文件为又分成两类: 1.次最高位为0 2.次最高位为1

并将这两类分别写入到两个文件中,其中一个文件中数的个数<=10亿,而另一个>=10亿(这相当于折半了); 与要查找的数的次最高位比较并接着进入相应的文件再查找。 ……. 以此类推,就可以找到了,而且时间复杂度为O(logn)。

2. 2.5亿个整数中找出不重复的整数的个数,内存空间不足以容纳这2.5亿个整数。##

整数个数为2^32,我们可以将这2^32个数,划分为2^8个区域(比如用单个文件代表一个区域),然后将数据分离到不同的区域,然后不同的区域在利用bitmap(占用4MB,内存可以存下)就可以直接解决了。也就是说只要有足够的磁盘空间,就可以很方便的解决。

3. 5亿个int找它们的中位数##

(指将统计总体当中的各个变量值按大小顺序排列起来,形成一个数列,处于变量数列中间位置的变量值就称为中位数)

首先我们将int划分为2^16个区域(肯定是按大小的),然后读取数据统计落到各个区域里的数的个数,之后我们根据统计结果就可以判断中位数落到那个区域,同时知道这个区域中的第几大数刚好是中位数。 然后第二次扫描我们只统计落在这个区域中的那些数就可以了。

4. 已知某个文件内包含一些电话号码,每个号码为8位数字,统计不同号码的个数(共有都少个不同的号码)。##

8位最多99 999 999(0-99 999 999共1亿个数),每个数字对应一个Bit位,所以只需要99MBit==1.2MBytes,这样,就用了小小的1.2M左右的内存表示了所有的8位数的电话)