@
- 12.海量数据找相同的
URL - 13.海量数据找高频词
- 14.海量数据找不重复的整数
- 15.海量数据判断数字是否存在
- 16.海量数据找热门串
- 17.海量数据找号码个数
- 18.海量数据找中位数
- 19.海量数据找前500
- 20.海量数据问题处理总结
- 21.
heapq - null
12.海量数据找相同的URL
问题：给定a、b两个文件，各存放50亿个url，每个url各占64字节，内存限制是4G，让你找出a、b文件共同的url？
分析：50亿个url，每个url64字节，就是320G，显然是无法一次读入内存的。因此这里需要采用分治法。
方案：分治法，分支方法：哈希
- 将AB两个文件，用相同的哈希函数，分解为1000个独立哈希值相同的小文件，这里哈希函数的设计是个重点。
- 哈希值不同的url必然不在序号对应的文件中，因此只要在序号对应的两个文件中进行互相匹配即可。
- 比较每对小文件时，可以使用hash_set。[^21]
图解详见[1]
13.海量数据找高频词
题目描述
有一个 1GB 大小的文件，文件里每一行是一个词，每个词的大小不超过 16B，内存大小限制是 1MB，要求返回频数最高的 100 个词(Top 100)。
思路如下：
首先遍历大文件，对遍历到的每个词x，执行hash(x) % 5000，将结果为 i 的词存放到文件ai中。遍历结束后，我们可以得到5000个小文件。每个小文件的大小为200KB左右。如果有的小文件大小仍然超过1MB，则采用同样的方式继续进行分解。
接着统计每个小文件中每个词出现频数。最简单的方式是使用HashMap来实现。其中key为词，value为该词出现的频率。具体方法是：对于遍历到的词x，如果在map中不存在，则执行map.put(x, 1)；若存在，则执行map.put(x, map.get(x)+1)，将该词频数加1。
上面我们统计了某个小文件单词出现的频数。接下来，我们可以通过维护一个小顶堆来找出所有词中出现频数最高的100个。具体方法是：构建一个小顶堆，堆大小为100。遍历map，如果遍历到的词的出现次数大于堆顶词的出现次数，则用新词替换堆顶的词，然后重新调整为小顶堆，当所有小文件对应的频数map遍历结束后，小顶堆上的词就是出现频数最高的100个词。
方法总结
- 分而治之，进行哈希取余；
- 使用
HashMap统计频数；- 求解最大的
TopN个，用小顶堆；求解最小的TopN个，用大顶堆。[^22]
详见[2]
14.海量数据找不重复的整数
题目描述
在 2.5 亿个整数中找出不重复的整数。注意：内存不足以容纳这 2.5 亿个整数。
位图法
对于这道题，我们用 2 个 bit 来表示各个数字的状态：
- 00 表示这个数字没出现过；
- 01 表示这个数字出现过一次（即为题目所找的不重复整数）；
- 10 表示这个数字出现了多次。
假设有 232 个整数，总共所需内存为 232*2b=1GB。因此，当可用内存超过 1GB 时，可以采用位图法来判断 232 （42.9亿左右）个整数。假设内存满足位图法需求，进行下面的操作：
遍历 2.5 亿个整数，查看位图中对应的位，如果是 00，则变为 01，如果是 01 则变为 10，如果是 10 则保持不变。遍历结束后，查看位图，把对应位是 01 的整数输出即可。[3]
也可以用分治法，位图及解释详见[3:1]
15.海量数据判断数字是否存在
题目描述
给定 40 亿个不重复的没排过序的 unsigned int 型整数，然后再给定一个数，如何快速判断这个数是否在这 40 亿个整数当中？[4]解答思路
方法一：分治法
依然可以用分治法解决，方法与前面类似，就不再次赘述了。方法二：位图法
40 亿个不重复整数，我们用 40 亿个 bit 来表示，初始位均为 0，那么总共需要内存：4,000,000,000b≈512M。
我们读取这 40 亿个整数，将对应的 bit 设置为 1。接着读取要查询的数，查看相应位是否为 1，如果为 1 表示存在，如果为 0 表示不存在。方法三：布隆过滤器
简单而言，布隆过滤器就是位图+一系列随机映射函数。
使用了N个互相独立的hash函数，对每条数据都进行N次哈希，并将对应单元置为1。
也就是说一个数字在位图当中会有好几位作为标志，只有有某一位没有打上标记，就意味这个数字不存在。
使用多位来标记数字是为了避免哈希冲突
- 布隆过滤器判断数据存在，那么它可能存在也可能不存在。
- 布隆过滤器判断数据不存在，那么它必定不存在。
布隆过滤器的解法见[5]，其本身的说明详见[6]
16.海量数据找热门串
- 题目描述
假设目前有 1000w 个记录（这些查询串的重复度比较高，虽然总数是 1000w，但如果除去重复后，则不超过 300w 个）。请统计最热门的 10 个查询串，要求使用的内存不能超过 1G。（一个查询串的重复度越高，说明查询它的用户越多，也就越热门。）- 解答思路
方法一：分治法
划分为多个小文件，保证单个小文件中的字符串能被直接加载到内存中处理，然后求出每个文件中出现次数最多的 10 个字符串；最后通过一个小顶堆统计出所有文件中出现最多的 10 个字符串。方法二：HashMap 法
虽然字符串总数比较多，但去重后不超过 300w，因此，可以考虑把所有字符串及出现次数保存在一个 HashMap 中，所占用的空间为 300w*(255+4)≈777M（其中，4表示整数占用的4个字节）。由此可见，1G 的内存空间完全够用。方法三：前缀树法
方法二使用了 HashMap 来统计次数，当这些字符串有大量相同前缀时，可以考虑使用前缀树来统计字符串出现的次数，树的结点保存字符串出现次数，0 表示没有出现。
- 总结
前缀树经常被用来统计字符串的出现次数。它的另外一个大的用途是字符串查找，判断是否有重复的字符串等。[7]
具体解释详见[7:1]，外排序详见[8]、[9]，字典树（前缀树）详见[10]、[11]
17.海量数据找号码个数
题目描述
已知某个文件内包含一些电话号码，每个号码为 8 位数字，统计不同号码的个数。
解答思路
申请一个位图数组，长度为 1 亿，初始化为 0。然后遍历所有电话号码，把号码对应的位图中的位置置为 1。遍历完成后，如果 bit 为 1，则表示这个电话号码在文件中存在，否则不存在。bit 值为 1 的数量即为 不同电话号码的个数。
方法总结
求解数据重复问题，记得考虑位图法。[12]
详见[12:1]
18.海量数据找中位数
题目描述
从 5 亿个数中找出中位数。数据排序后，位置在最中间的数就是中位数。当样本数为奇数时，中位数为 第 (N+1)/2 个数；当样本数为偶数时，中位数为 第 N/2 个数与第 1+N/2 个数的均值。
解答思路
方法一：双堆法
维护两个堆，一个大顶堆，一个小顶堆。大顶堆中最大的数小于等于小顶堆中最小的数；保证这两个堆中的元素个数的差不超过 1。
若数据总数为偶数，当这两个堆建好之后，中位数就是这两个堆顶元素的平均值。当数据总数为奇数时，根据两个堆的大小，中位数一定在数据多的堆的堆顶。
方法二：分治法
对于这道题，顺序读取这 5 亿个数字，对于读取到的数字 num，如果它对应的二进制中最高位为 1，则把这个数字写到 f1 中，否则写入 f0 中。通过这一步，可以把这 5 亿个数划分为两部分，而且 f0 中的数都大于 f1 中的数（最高位是符号位）。
划分之后，可以非常容易地知道中位数是在 f0 还是 f1 中。假设 f1 中有 1 亿个数，那么中位数一定在 f0 中，且是在 f0 中，从小到大排列的第 1.5 亿个数与它后面的一个数的平均值。
对于 f0 可以用次高位的二进制继续将文件一分为二，如此划分下去，直到划分后的文件可以被加载到内存中，把数据加载到内存中以后直接排序，找出中位数。[13]
详见[13:1]
19.海量数据找前500
题目描述：
有20个数组，每个数组有500个元素，升序排列，现在在这20*500个数中找出排名前500的数。解答思路：
保持一个20的堆，然后先将每个数组的第1个数入堆。
20个元素的堆一直保持容量为20个，20个数组的最小元素可以将20个数组的第0个元素入堆，最小堆的性质，顶点为最小值。这时候得到了500个结果里的第0个结果。然后再把下一个元素入20个元素的堆，堆插入的时候会保持性质不变，最小元素依然在顶点。再取出20个元素的顶点，得到500个结果里的第1个结果。
假设 [1,3,4,5,6] [2,3,4,5,6] [3,4,5,6,7]
最小的是比较 1 2 3 得到1
第2小的是将刚才的1替换为后面的元素3 再加上刚才的元素2 3，得到2
注意这儿需要保持数来自于哪个数组，以及其在数组里的位置[14]
详见[14:1]
20.海量数据问题处理总结
处理海量数据问题，无非就是：[15]
- 分而治之/hash映射 + hash统计 + 堆/快速/归并排序；
- 双层桶划分
- Bloom filter/Bitmap；
- Trie树/数据库/倒排索引；
- 外排序；
- 分布式处理之Hadoop/Mapreduce。
另一份总结见[16]
其他海量数据处理的问题及解法见[17]、[18]
21.heapq
关于python当中的heapq模块详见[19]
海量数据处理面试题(1) 找出两文件种包含的相同的url ↩︎
【海量数据处理】如何从大量数据中找出高频词？ ↩︎
【海量数据处理】如何在大量的数据中找出不重复的整数？ ↩︎ ↩︎
如何在大量数据中判断一个数是否存在？ ↩︎
如何在海量数据中判断某个数据是否存在？ ↩︎
海量数据处理之Bloom Filter详解 ↩︎
如何查询最热门的查询串？ ↩︎ ↩︎
排序之外部排序 ↩︎
外部排序算法总结 ↩︎
算法与数据结构基础 - 字典树(Trie) ↩︎
字典树(Trie)详解 ↩︎
如何统计不同电话号码的个数？ ↩︎ ↩︎
如何从 5 亿个数中找出中位数？ ↩︎ ↩︎
有20个数组，每个数组有500个元素，升序排列，现在在这20*500个数中找出排名前500的数。求时间复杂度？ ↩︎ ↩︎
教你如何迅速秒杀掉：99%的海量数据处理面试题 ↩︎
海量数据处理 - 10亿个数中找出最大的10000个数（top K问题） ↩︎
十道海量数据处理面试题与十个方法大总结 ↩︎
海量数据查询 ↩︎
实践中总结出来对heapq的一点理解 ↩︎