[算法]海量数据问题之二

题目一:

32位无符号整数的范围是0-2^32-1即0-4294967295,现在有一个正好包含40亿个无符号整数的文件,所以在整个范围中必然有没出现的数。可以使用最多1GB的内存。

1.怎么知道所有没有出现过的数?

哈希表需要占用很多空间,可以使用bit map的方式来表示数出现的情况。具体地说,是申请一个长度为4294967295的bit类型的数组bitArr,bitArr上的每个位置只能表示0或1两个状态。8个bit为1B,所以长度为为4294967195的bit类型的数组占用500MB空间。

遍历这40亿个数,把遇到的数相应位置的值赋为1;

遍历整个数组,值为0的下标即为没有出现过的数。

2.内存限制为10MB,但是只要找到一个没出现过得数即可。

现在只有10MB的内存,但是也只要求找到其中一个没出现过的数即可。首先,0-2^32-1,这个范围是可以平均分成64个区间的,每个区间是67108864个数。如果统计落在每一个区间上的数有多少,肯定有至少一个区间上的计数少于67108864。具体过程为:

第一次遍历时,先申请长度为64的整形数组countArr[0..63],countArr[i]用来统计区间i上的数有多少。遍历40亿个数时,如果当前数为3422552090,3422552090/67108864=51,所以第51区间上的技术增加countArr[51]++。便利完40亿个数后,便利countArr,必然会出现某一位置上的值小于67108864,,表示该区间上至少有一个数没出现过。我们在该区间上继续寻找,此时使用的内存就是countArr的大小(64*4B),是非常小的。

假设找到第37区间上的计数小于67108864,以下为第二次遍历过程:

1.申请长度为67108864的bit map,这占用大约8MB的空间,记为bitArr[0..67108863];

2.再遍历一遍40亿个数,此时的遍历只关注落在第37区间上的数,记为num(num/67108864=37),其他区间的数全部忽略;

3.如果步骤2上的num落在第37区间上,将bitArr[num-67108864*37]的值设置为1,也就是做映射;

4.便利完40亿个数后,在bitArr上必然存在没被设置成1的位置,假设第i个位置上的值没设置成1,那么67108864*37+i,就是一个没出现过得数。


题目二:

有一个包含100个URL的大文件,假设每个URL占用64B,找出其中所有的URL。

解答:

把大文件通过哈希函数分配到机器,或者通过哈希函数把大文件拆成小文件。一直进行这种划分,知道划分的结果满足资源限制的要求。

例如:将100亿字节的大文件通过哈希函数分配到100台机器上,然后每一台机器分别统计分给自己的URL中是否含有重复的URL,同时哈希函数的性质决定了同一条URL不可能分配给不同的机器;或者单机上将单文件通过哈希函数拆成1000个小文件,对每一个小文件再利用哈希表遍历,找出重复的URL;或者在分给机器或拆成文件之后,进行排序,排序过后再看是否有重复的URL出现。


题目三:

在2.5亿个整数中找出不重复的整数,注,内存不足以容纳这2.5亿个整数。

方案1:

采用2-Bitmap(每个数分配2bit,00表示不存在,01表示出现一次,10表示多次,11无意义)进行,共需内存2^32 * 2 bit=1 GB内存,还可以接受。然后扫描这2.5亿个整数,查看Bitmap中相对应位,如果是00变01,01变10,10保持不变。所描完事后,查看 bitmap,把对应位是01的整数输出即可。

方案2:

也可采用与第1题类似的方法,进行划分小文件的方法。然后在小文件中找出不重复的整数,并排序。然后再进行归并,注意去除重复的元素。


题目四:

32位无符号整数的范围是0-4294967295,现在有40亿个无符号整数,可以使用最多1GB的内存,找到所有出现了两次的数。

解答:

可以使用bit map的方式来表示数出现的情况。具体地说,是申请一个长度为4292967295*2的bit类型的数组bitArr,用2个位置表示一个数出现的词频,1B占用8个bit,所以长度为4294967295*2的bit类型的数组占用1GB空间。

开始遍历:

  • 初次遇到:bitArr[num*2+1]=0;bitArr[num*2]=1;
  • 第二次遇到:bitArr[num*2+1]=1;bitArr[num*2]=0;
  • 第三次遇到:bitArr[num*2+1]=1;bitArr[num*2]=1;
  • 以后再遇到:不作处理。

再次遍历bitArr,如果发现bitArr[i*2+1]=1;bitArr[i*2]=0;那么i就是出现了两次的数。


题目五:

32位无符号整数的范围是0-4294967295,现在有40亿个无符号整数,可以使用最多10MB的内存,找到中位数。

解答:

用分区间的方式处理,长度为2MB的无符号整形数组占用空间为8MB,所以将区间的数量定为4294967295/2M,向上取整为2148个区间,第i个区间为2M*i~2M*(i+1)-1。

申请一个长度为2148的无符号整型数组arr[0..2147],arr[i]表示区间i有多少个数。然后遍历到当前数为num,先看num落在哪个区间上【num/2M】,然后执行arr[num/2M]++操作。这样遍历下来,就得到了每一个区间的数的出现状况,通过累加每个区间的出现次数,就可以找到40亿个数的中位数落在哪个区间上。

接下来申请一个长度为2MB的无符号整形数组countArr[0..2M-1],占用空间8MB。然后再遍历40亿个数,此时只关心处在第k区间的数记为numi,其他的数省略,然后将countArr[numi-K*2M]++],也就是对处在第K区间的数做频率统计。

原文地址:https://www.cnblogs.com/xiaomoxian/p/5161616.html