【算法专题】海量数据处理

一般问题类型

• 海量数据，求 TopK 或者 Top1
• 海量数据，统计出现次数最多的数字
• 海量数据，存在查询
• 海量数据，统计只出现一次的数字
• 海量数据，排序（任意大小，或者 0～10000）
• 两个海量数据，找公共元素

解决方案

「数据拆分」

• 数据太大无法一次性放入内存，可使用 hash 将数据映射到不同文件分而治之，单独处理每个文件后合并结果。

「频率统计 Top1」

• 频率统计可使用 hashmap，遍历一遍得到出现频率表，遍历过程中记录频率最大的值。

• 若数据量太大则分片读入数据，维护一个最大值，也可以每片得到一个最大值后排序。

「TopK (K>1)」

• 使用一个大小限制为 K 的小根堆（堆顶元素就是这 K 个数中的最小值），逐个添加元素，小根堆满了则将堆顶元素与当前遍历元素 x 对比，若 x 大于堆顶元素则将堆顶元素取出，将新值放入。

• 若数据量太大则分片读入数据，维护这一个小根堆即可得到最终的 TopK。

「存在查询」

• 查询数据在不在可以使用位图，前提是数据范围不超过内存大小。

「只出现一次」

• 数据量小：位图法（2bit-Bitmap，00 不存在，01 出现一次，10 多次，11 无意义）
• 数据量大：先 hash 分拆到 N 个小文件，每个文件使用位图或 hashmap 判断出现一次的数，最后所有小文件的结果合并

「数据排序」

• 任意大小：外排序
  • 先将数据拆分到多个文件，分别加载到内存中排序，然后归并到一个文件
  • 代价是要进行多次 IO，性能较差
• 范围为 [0, 10000]：计数排序
• 范围更大：位图
  • 适合下标密集的情况，否则会浪费大量的空间
  • 位图会自动去重，适合不考虑重复元素的情况，比如大量 QQ 号排序

「找公共元素」

• 位图 or 布隆过滤器，分拆文件 + hashmap

案例

例 1：提取出某日访问百度次数最多的 IP

IP 是 32 位有 $2^{32}$ =4G 个可能，单个 IP xxx.xxx.xxx.xxx\0 长度 8~15 个字节，不考虑编码格式估计为 10B。

假设百度 PV（10 亿=1G），当所有 IP 无法一次性放入内存，就需要拆分。

1. 计算 IP 的 $hash (IP)%1024$ 映射到 1024 个文件；
2. 每个文件通过 hashmap 统计频率并记录最大值；
3. 得到 1024 个极大值整体排序得到最终结果。

---

例 2：有10个文件（每个文件1G），文件的每一行存放的都是用户的 query，每个文件的 query 都可能重复。要求你按照 query 的频度排序。

「方案一」：内排序+外排序

1. 顺序读取 10 个 A 文件并通过 hash 映射到另外的 10 个 B文件（假设映射均匀每个文件为 1G），这样相同的 query 都在一个文件中；
2. 每个 B 文件通过 hashmap 统计频率，完成排序输出到 C 文件
3. 对这 10 个文件进行归并排序

重复 query 比较多，可以尝试把所有的 query 可以一次性加入内存

「方案2」：内排序

1. 顺序读取 10 个 A 文件通过 hashmap 统计频率，按频率排序

---

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

「方案一」：拆分遍历（50亿个 url 总共大小 $50G*64B = 320G$，大于内存限制，需要文件拆分）

1. 通过 hash 进行分解拆分，映射到 1000 个文件中，平均每个文件 320M；
2. 遍历 A 的小文件

「方案二」：布隆过滤器（4G 内存大概可表示 340亿 bit）

1. 将其中一个文件中的 url 使用布隆过滤器映射为这 340 亿 bit；
2. 挨个读取另外一个文件的 url，检查布隆过滤器，如果相应位为 1 那么该 url 可能是共同的 url（有一定误差）

布隆过滤器用于判断某样东西一定不存在或者可能存在，判断存在会有一定的错误率

---

例 4：40亿个「无序不重复」的 unsigned int 整数，如何快速判断另一个数 x 是否在那40亿个数当中？

int 最大 2^31-1=2147483647（21 亿）

使用位图，申请 512M 内存，一个 bit 位代表一个 unsigned int 值

---

例 5：在 2.5 亿个整数中找出不重复的整数（内存不足以容纳这2.5亿个整数）

采用 2-Bitmap（每个数分配 2bit，00表示不存在，01表示出现一次，10表示多次，11无意义），只需要 $2^{29}*2$ bit 空间（大约 128MB）

• 扫描这 2.5 亿个整数，查看 Bitmap 中相对应位，如果是 00 变 01，01 变 10，10 保持不变
• 所描完成后，查看 bitmap，把对应位是 01 的整数输出即可

相关资料

• imageslr’s blog: 海量数据问题
• 十道海量数据处理面试题与十个方法大总结
• 教你如何迅速秒杀掉：99% 的海量数据处理面试题