面向自由编程

海量数据问题

Posted on Edited on In
Symbols count in article: 2.3k Reading time ≈ 2 mins.

海量数据问题

海量日志找出现次数最多的记录

  • 问题主要是记录不能全部载入到内存
  1. 先把整个文件分割成若干个小文件，比如1000个小文件
  2. 找出每个文件中出现次数最多的记录（输出1000个记录+频次）
  3. 从每个文件出现最多的记录找出全局出现次数最多的记录（合并记录，找出最多的频次）

统计topk个热门记录

  1. 依次遍历这些文件，通过hash映射，将每个文件的每条数据映射到新构造的多个小文件中（设生成了nn个小文件）；
  2. 依次统计每个小文件中出现次数最多的kk条数据，构成hash表，hash表中每个键值对的形式为 dataItem: count；
  3. 利用堆排序，依次遍历这些hash表，在n∗kn∗k条数据中，找出count值最大的kk个；

海量数据查重

  1. 遍历A中的所有数据，通过hash映射将他们分布存储在n个小文件中，记为{a1,a2,…,an}；
  2. 遍历B中的所有数据，通过hash映射将他们分布存储在n个小文件中，记为{b1,b2,…,bn}；
  3. 根据hash函数性质可知，A和B中的相同数据一定被映射到序号相同的小文件，所以我们依次比较{ai,bi}即可；
  4. 如果问题更进一步，要求返回重复次数最多的k条数据，则可以将对比小文件找到的数据存入hash表，键为数据，值为该数据出现的次数。再用大小为k的堆，排序找出即可。

海量数据频率排序

  1. 顺序读文件，利用hash将相同的记录输出到相同的文件里。
  2. 每个小文件统计频率， 排序
  3. 归并排序(外部排序)
    外部排序参考

int数字重复数据查找（BitMap）

  • 例如：在2.5亿个整数里找不重复的整数
  1. 使用2bitmap算法， 00 代表没有出现，01表示出现一次，10表示出现多次。
  2. 计算下：整数4B，最多表示2^32个数，每个数用2个bit表示，就是2^32 * 2 / 2^30 / 8 = 1G，注意那个8是B转bit。
  3. 然后扫描这2.5亿个整数，查看Bitmap中相对应位，如果是00变01，01变10，10保持不变。所描完事后，查看bitmap，把对应位是01的整数输出即可。
  • 再例如：给40亿个不重复的unsigned int的整数，没排过序的，然后再给一个数，如何快速判断这个数是否在那40亿个数当中？
    原理和上面一样，使用1bitmap就可以了

超大文件求交集

  • 现有两个各有20亿行的文件，每一行都只有一个数字，求这两个文件的交集。
  1. 开辟128M的int数组。
    • int最大表示4G，也就是需要2^32bit位， 一个int是4B，也就是32bit，因此需要2^32/2^5=2^27bit。
  2. 对于每个数，先 /32，确定在数组哪个位置，然后%32，确定在该int的哪一位，然后对这个数组取并集即可统计
  3. 如果存在正负数的话，设置正负两个bitmap然后分别求交集即可

超大文件字符串重复

  • 给定a、b两个文件，各存放50亿个url，每个url各占64字节，内存限制是4G，让你找出a、b文件共同的url

  1. 分文件：

    • 遍历文件a，对每个url求取hash(url)%1000，然后根据所取得的值将url分别存储到1000个小文件（记为a0,a1,…,a999）中。这样每个小文件的大约为300M。

    • 遍历文件b，采取和a相同的方式将url分别存储到1000小文件（记为b0,b1,…,b999）。这样处理后，所有可能相同的url都在对应的小文件（a0vsb0,a1vsb1,…,a999vsb999）中，不对应的小文件不可能有相同的url。然后我们只要求出1000对小文件中相同的url即可。

  2. 逐个找重复：

  • 求每对小文件中相同的url： 把其中一个小文件的url存储到hash_set中，然后遍历另一个小文件的每个url，看其是否在刚才构建的hash_set中，如果是，那么就是共同的url，存到文件里面就可以了。

海量数据中位数（计数排序）

  • 只有2G内存的pc机，在一个存有10G个整数的文件，从中找到中位数，写一个算法。

  • 分析：
    明显是一道工程性很强的题目，和一般的查找中位数的题目有几点不同。

  1. 原数据不能读进内存，不然可以用快速选择，如果数的范围合适的话还可以考虑桶排序或者计数排序，但这里假设是32位整数，仍有4G种取值，需要一个16G大小的数组来计数。

  2. 若看成从N个数中找出第K大的数，如果K个数可以读进内存，可以利用最小或最大堆，但这里K=N/2,有5G个数，仍然不能读进内存。

  • 解法一：桶排序

  1. 读一遍10G个整数，把整数映射到256M个区段中，用一个64位无符号整数给每个相应区段记数。

  2. 从前到后对每一段的计数累加，当累加的和超过5G时停止，找出这个区段（即累加停止时达到的区段，也是中位数所在的区段）的数值范围，设为[a，a+15]，同时记录累加到前一个区段的总数，设为m。然后，释放除这个区段占用的内存。

  3. 再读一遍10G个整数，把在[a，a+15]内的每个值计数，即有16个计数。

  4. 对新的计数依次累加，每次的和设为n，当m+n的值超过5G时停止，此时的这个计数所对应的数就是中位数。

  • 解法二：二进制分文件

    假设10亿个数字保存在一个大文件中，依次读一部分文件到内存(不超过内存的限制：1GB)，将每个数字用二进制表示，比较二进制的最高位(第32位)，如果数字的最高位为0，则将这个数字写入 file_0文件中；如果最高位为 1，则将该数字写入file_1文件中。【这里的最高位类似于快速排序中的枢轴元素】

    从而将10亿个数字分成了两个文件（几乎是二分的），假设 file_0文件中有 6亿 个数字，file_1文件中有 4亿 个数字。那么中位数就在 file_0 文件中，并且是 file_0 文件中所有数字排序之后的第 1亿 个数字。