海量数据问题

高频八股之海量数据问题

本文参考自教你如何迅速秒杀掉：99%的海量数据面试题

数据量过大，而内存空间不足或短时间内无法迅速求解的问题

分治 ===> hash ===> 求解子问题 ===> 归并

现有海量日志数据，要提取出某日访问百度次数最多的那个IPv4地址
内存空间有限，不足以全部加载。

分治 — IP地址范围0.0.0.0 --- 255.255.255.255共$2^{32}$个，根据其规律将其按地址划分(类似子网划分，在此根据掩码来划分为多个文件，以$2^8$为例，划分到$2^8$个子文件中，每个文件$2^{24} = 16M$个不同的IP地址)
hash — 将unsigned int32类型的IP地址，做hash(IP)%256处理，划分到256个子文件中(哈希函数一定，某特定IP的多次计算得到的值一定相同，一定在同一个文件)
求解子问题 — 所求问题为最大值，如果我们对每个子问题（子文件）求最大值，则全局最大值一定在这些子问题最大值中。对每个小文件构建map，统计出现次数的最大值。
归并 — 得到多个子文件中的最大值（局部最优解）进行比较，得到全局最优解。$ File_i{Max} > File_{else}Max > File_{else}else$（子文件最大值中的最值 > 其他子文件的最值 > 其他子文件所有值）

有一个1G大小的一个文件，里面每一行是一个词，词的大小不超过16字节，返回频数最高的100个词。
内存限制大小1M

解题思路与上述基本相同，此外

内存限制为1M，则至少需要1G/1M = 1024个文件(考虑分布不均，应至少为4、5倍，合理即可)
由于返回的是最大的100个词，同样防止分布不均（高频词都在一个文件），应每个子文件都要求TOP100
如若子文件划分过多，每个的TOP100在内存中放不下（无法直接排序）可以：
- 重复上述步骤
- 维持一个堆，记录高频词及出现次数。依次读不同文件来维持这个堆。

海量数据分布在100台电脑中，想个办法高效统计出这批数据的TOP10。
海量数据中找出重复次数最多的一个
上千万或上亿数据（有重复），统计其中出现次数最多的前N个数据。

同上

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

分治 — $2^8\times 5G = 5\times2^{40} = 320G > 4G$，将文件划分到多个子文件中（防止分布不均应多划分几个区间，如500个）
hash — 文件a、b分别hash(url)%500存入各自子文件中（采用相同的hash函数，则相同的url存在于同一类子文件，如某url在a的子文件$a_{13}$中，则如果b中也有,则一定在$b_{13}$中）
求解子问题 — 分别读子文件$a_i\qquad b_i$，对比hash值得到相同url（如先将$a_i$中的值存入hash表，然后遍历$b_i$中的值和hash表比对，相同则存在重复元素）
归并

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

方案1 — 上述解决方案仍可行。
方案2 — bitmap
- 观察要求，数据分为三类：没出现过、出现一次（所求）、出现多次。我们可以用2bit来反应其出现情况，00 ===>没出现过 01 ===> 出现1次 10 ===> 出现多次
- 我们只需要人为规定一种映射来对应其关系即可，无需存储具体数字。由于，我们可以用2bit来表示出现情况，则1Bytes大小我们可以表示四个数字的出现情况。比如100即第[100/4]Bytes的第[100%4 * 2]和 [100%4 * 2 + 1]两位。利用移位及&操作即可得到其值。（bitmap[25] >> 6）
- 理论原值存储使用空间0.25G*4Bytes = 1GB，实际使用空间0.25G * 2bit = 64MB

5亿个int型整数，找中位数

按照前面的方案，我们可以将这些数据划分为多个子区域，然后再去寻找中位数。关于如何划分子区域，还能够让其保持一个相对顺序：

首先，我们判断最高位，根据最高位为1 or 0可以分为两个子数组
再此基础上判断次高位为1 or 0再次划分
至此，我们有4个区间0b11XXXXX 0b10XXXXX 0b01XXXXX 0b00XXXXX，分组间的大小关系显而易见。
借此思路，我们可以直接根据前X位的值，将其划分为$2^X$个子文件，然后根据中位数（第K顺序统计量）所在的角标来判断其应该处于哪个子文件，然后在子文件中去排序、查找。

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