海量数据问题处理

海量数据，是指 数据量太大，所以导致要么是无法在较短内时间迅速解决，要么是数据量太大，导致无法一次性装入内存

  • 针对时间，可以考虑采用巧妙算法搭配合适的数据结构，比如 Bloom Filter/Hash/BitMap/堆/Trie树等
  • 针对空间，无非就是一个办法

算法思路

题目举例

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

  • unsigned int 占据 4 byte, 32 个 bit，范围是从 0 ~ 2^32-1，也即是 42,9496,7296，42亿

思路1：bitmap

  1. 可以用 1 个bit 表示一个数，那么 1 个 unsigned int 可以表示 32 个数
  2. 2^32 个数需要 2^32 / 2^5 = 2^27 个 unsigned int 来表示，每个 4 Byte，大小为 2^29 B，约为 512MB

设 N 为整数的个数，申请 N/32+1 大小的 unsigned 数组 unsinged int tmp[N/32+1]，也就是 bitmap 表：

则

  • tmp[0] 可表示 0～31
  • tmp[1] 可表示 32～63
  • tmp[2] 可表示 64～95

假设这些数据为 6, 3, 8, 32, 36, …，则具体的 bitmap 可以表示为：

  • 如何确定一个整数在数组的那个元素呢：number / 32 记得到 index
  • 如何判断一个整数是否存在呢？找到对应的元素，判断 (1 << (number % 32)) & element 是否为 1

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

思路一：

  1. 顺序读取 10 个文件，按照 hash(query)%10 的结果将 query 写入到另外 10 个文件（记为）中。
  2. 这样新生成的文件每个的大小大约也 1G（假设 hash 函数是随机的）。 3. 找一台内存在 2G 左右的机器，依次对用 hash_map(query, query_count) 来统计每个query 出现的次数。利用快速/堆/归并排序按照出现次数进行排序。将排序好的 query 和对应的 query_cout 输出到文件中。这样得到了 10 个排好序的文件（记为）。 对这 10 个文件进行归并排序（内排序与外排序相结合）。

内排序与外排序，参考 数据结构与算法

思路二：

一般 query 的总量是有限的，只是重复的次数比较多而已，可能对于所有的 query，一次性就可以加入到内存了。这样，我们就可以采用 trie 树/hash_map等直接来统计每个 query出现的次数，然后按出现次数做快速/堆/归并排序就可以了。

思路三：

与方案 1 类似，但在做完 hash，分成多个文件后，可以交给多个文件来处理，采用分布式的架构来处理（比如 MapReduce），最后再进行合并。

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

思路一：

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

思路二：

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

怎么在海量数据中找出重复次数最多的一个？

思路一：

先做 hash，然后求模映射为小文件，求出每个小文件中重复次数最多的一个，并记录重复次数。然后找出上一步求出的数据中重复次数最多的一个就是所求（具体参考前面的题）。

上千万或上亿数据（有重复），统计其中出现次数最多的前 N 个数据。

思路一：

上千万或上亿的数据，现在的机器的内存应该能存下。所以考虑采用 hash_map/搜索二叉树/红黑树等来进行统计次数。然后就是取出前 N 个出现次数最多的数据了，可以用第 2 题提到的堆机制完成。

一个文本文件，大约有一万行，每行一个词，要求统计出其中最频繁出现的前 10 个词，给出思想，给出时间复杂度分析。

思路一：

这题是考虑时间效率。用 trie 树统计每个词出现的次数，时间复杂度是 O(n*le)（le表示单词的平准长度）。然后是找出出现最频繁的前 10 个词，可以用堆来实现，前面的题中已经讲到了，时间复杂度是 O(n*lg10)。所以总的时间复杂度，是 O(n*le) 与 O(n*lg10)中较大的哪一 个。

100w 个数中找出最大的 100 个数。

思路一：

在前面的题中，我们已经提到了，用一个含 100 个元素的最小堆完成。复杂度为 O(100w*lg100)。

思路二：

采用快速排序的思想，每次分割之后只考虑比轴大的一部分，知道比轴大的一部分在比 100 多的时候，采用传统排序算法排序，取前 100 个。复杂度为 O(100w*100)。

思路三：

采用局部淘汰法。选取前 100 个元素，并排序，记为序列 L。然后一次扫描剩余的元素 x，与排好序的 100 个元素中最小的元素比，如果比这个最小的 要大，那么把这个最小的元素删除，并把 x 利用插入排序的思想，插入到序列 L 中。依次循环，直到扫描了所有的元素。复杂度为 O(100w*100)。

有一千万条短信，有重复，以文本文件的形式保存，一行一条，有重复。请用 5 分钟时间，找出重复出现最多的前 10 条。

1）方案 1：在前面的题中，我们已经提到了，用一个含 100 个元素的最小堆完成。复杂度为O(100wlg100)。
2）方案 2：采用快速排序的思想，每次分割之后只考虑比轴大的一部分，知道比轴大的一部分在比 100 多的时候，采用传统排序算法排序，取前 100 个。复杂度为 O(100w100)。
3）方案 3：采用局部淘汰法。选取前 100 个元素，并排序，记为序列 L。然后一次扫描剩余的元素 x，与排好序的 100 个元素中最小的元素比，如果比这个最小的 要大，那么把这个最小的元素删除，并把 x 利用插入排序的思想，插入到序列 L 中。依次循环，直到扫描了所有的元素。复杂度为 O(100w*100)。

参考资料