海量数据处理 海量数据处理面试题小结

对大量数据进行无重复排序

bitmap法。

示例:电话号码排序

使用重复的海量数据进行排序

示例:存在重复的电话号码排序

你可以把电话号码想象成一个大整数。

自己猜答案:

方法1:

外部排序。分成几个小文件，对小文件进行排序。然后合并小文件。(缺点是需要大量IO，耗费时间，效率不高)

方法2:

应该有更高效的方法。

从海量数据中寻找重复次数最多的前k条记录

注意这个求top k出现次数的问题，应该转化为先求每个记录的出现次数，再求TOP K的出现次数，如果top k大，用小根桩更方便。

方法1:(如果这些数据可以放入内存)

(1)对这批海量数据进行预处理，用哈希表在O(N)时间内完成统计；

②借助堆的数据结构，找出Top K，时间复杂度为NlogK。维护一个k大小的小根堆，然后遍历数据，分别与根元素进行比较。因此，如果大于根元素，就用根元素替换，然后调整堆。我们最后的时间复杂度是:O(N)+N*O(logK)

方法2:(如果没有足够的内存来存放这些数据的哈希统计)

也应该可以用分而治之的方法，把它分成1000个文件，找出每个文件的前k个文件。然后合并每个文件。

方法3:

例如，在一个大的文本文件中找到词频最高的10个单词，

可以用字典树+小根堆的方法。

维护一个大小为10的数组，存储当前出现次数最多的单词及其出现次数，按降序排列。在二进制排序树中每次搜索成功后，更新单词的出现次数，并与前10个数组进行比较。如果单词已经出现在前10个数组中，直接更新相应的值。如果单词没有出现，删除最多的一个，然后插入。

还有别的办法吗？

附:前K题特例:前1

比如ip访问日志，找到频率最高的ip

算法思路:分而治之+Hash

按照IP地址的Hash(IP)%1024值，把海量IP日志分别存储到1024个小文件中。这样，每个小文件最多包含4MB个IP地址；对于每一个小文件，可以构建一个IP为key，出现次数为value的Hash map，同时记录当前出现次数最多的那个IP地址；可以得到1024个小文件中的出现次数最多的IP，再依据常规的排序算法得到总体上出现次数最多的IP； 多个文件海量数据排序

例如:有10个文件，每个文件为1G，每个文件的每一行存储用户的查询，每个文件的查询都可能重复。您需要根据查询频率进行排序。

方法1:

顺序读取10个文件，按照hash(query)%10的结果将query写入到另外10个文件（记为）中。这样新生成的文件每个的大小大约也1G（假设hash函数是随机的）。找一台内存在2G左右的机器，依次对用hash_map(query,query_count)来统计每个query出现的次数。利用快速/堆/归并排序按照出现次数进行排序。将排序好的query和对应的query_cout输出到文件中。这样得到了10个排好序的文件（记为）。对这10个文件进行归并排序（内排序与外排序相结合）。 （可是这一步的话，不会涉及到所有文件读入内存吗？？） 答：因为有排序，所以可以避免需要一次读入全部的情况

方法2:

hash完成并划分为多个文件后，可以交给多个文件进行处理，采用分布式架构进行处理(如MapReduce)，最后合并。

两个大文件的重复记录

举例:给定两个文件，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:

如果允许一定的错误率，可以使用布隆过滤器

从海量数据中寻找不重复出现的记录。

示例:从2.5亿个整数中找出不重复的整数。注意，内存不足以容纳这2.5亿个整数。

方法1:

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

方法2:

您也可以使用类似于问题1的方法来分割小文件。然后找出小文件中不重复的整数，排序。(因为有排序，可以避免一下子全部读完的需要。)然后合并，注意去掉重复的元素。

在海量数据中搜索

举例:腾讯面试问题:给出40亿个不重复的无符号整数，不排序，然后再给出另一个数字，如何快速判断这个数字是否在那40亿个数字中？

方法1:

申请512M内存，一位代表无符号int值。读入40亿的数字，设置对应的位，读入要查询的数字，检查对应的位是否为1，表示存在，0表示不存在。

方法2:

2 ^ 32大于40亿，所以给定的数字可能在其中，也可能不在其中；

这里，我们用32位二进制表示40亿个数字中的每一个

假设这40亿个数字开始放在一个文件中。

然后将这40亿个数字分成两类:

最高位为0最高位为1

并将这两种类型分别写入两个文件，其中一个文件中的数字个数:= 20亿(这相当于一半)；

与要搜索的数字的最高位进行比较，然后输入相应的文件再次搜索

然后将该文档分为两类:

次最高位为0次最高位为1

并将这两种类型分别写入两个文件，其中一个文件中的数字个数:= 10亿(这相当于一半)；

与要搜索的数字的下一个最高位进行比较，然后输入相应的文件再次搜索。

.......

类比一下就能找到，时间复杂度为O(logn)

参考数据

编程珠玑http://blog.csdn.net/v_JULY_v

来源:https://www.cnblogs.com/xawei/p/6726620.html