【面经】海量数据处理相关

发表于 | 浏览 次
字数统计: 1,524 | 阅读时长 ≈ 5

第一部分 分而治之/Hash映射 + Hash_map统计 + 堆/快速/归并排序

1. 海量数据选取TOPK

baseline：

用堆，如果取最大的K个，就用最小堆，遍历数组，遇到比堆顶元素大的元素就入堆，同时堆中元素超过k个需要poll操作，保证堆中只有K个元素，最终的topk元素在堆中。

时间复杂度分析:

算法：

先用quick select方法找到第K大的元素，复杂度

然后再遍历一遍，将大于K的元素取出，复杂度

总复杂度

！！！！！卧槽！神奇！！！！

2. 海量数据选取第K大

Quick Select，详见【九章算法强化班】两指针

时间复杂度

3. 大数排序问题

海量数据排序怎么做？

baseline：快排，问题：数据量很大，内存根本存不下，不可行

桶排序：

将数据分桶，每个桶存入一个文件，然后文件内部有序，取出合并的时候可以用K路归并，优化：k路可以建个堆

4. 海量日志数据，提取出某日访问百度次数最多的那个IP

  1. 首先将这一天的访问百度的日志IP取出来，写到一个大文件中，IP是32位的，因此最多有个IP。
  2. 将整个文件的所有IP映射为10000个小文件，再找出每个小文件中出现次数最多的IP，此时可以用HashMap统计一下
  3. 在10000个小文件的top1中寻找整体top1

5. 300万个查询字符串中统计最热门的10个查询

原题：搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来，每个查询串的长度为1-255字节。假设目前有一千万个记录（这些查询串的重复度比较高，虽然总数是1千万，但如果除去重复后，不超过3百万个。一个查询串的重复度越高，说明查询它的用户越多，也就是越热门），请你统计最热门的10个查询串，要求使用的内存不能超过1G。

​ 解答：由上面第1题，我们知道，数据大则划为小的，如如一亿个Ip求Top 10，可先%1000将ip分到1000个小文件中去，并保证一种ip只出现在一个文件中，再对每个小文件中的ip进行hashmap计数统计并按数量排序，最后归并或者最小堆依次处理每个小文件的top10以得到最后的结。

​ 但如果数据规模比较小，能一次性装入内存呢?比如这道题，虽然有一千万个Query，但是由于重复度比较高，因此事实上只有300万的Query，每个Query255Byte，因此我们可以考虑把他们都放进内存中去（300万个字符串假设没有重复，都是最大长度，那么最多占用内存3M*1K/4=0.75G。所以可以将所有字符串都存放在内存中进行处理），而现在只是需要一个合适的数据结构，在这里，HashTable绝对是我们优先的选择。

解法：

  1. Hash_map统计字符串出现次数
  2. 借助堆找出出现次数最多的topK个query

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

  1. 分而治之/hash映射：顺序读文件中，对于每个词x，取hash(x)%5000，然后按照该值存到5000个小文件（记为x0,x1,…x4999）中。这样每个文件大概是200k左右。如果其中的有的文件超过了1M大小，还可以按照类似的方法继续往下分，直到分解得到的小文件的大小都不超过1M。
  2. hash_map统计：对每个小文件，采用trie树/hash_map等统计每个文件中出现的词以及相应的频率。
  3. 堆/归并排序：对于每个小文件，利用堆取出top100的单词，存入新文件，这样又得到了5000个新文件，然后对5000个文件做归并排序，取出全局top100，依然可以用堆优化

7. 海量数据分布在100台电脑中，想个办法高效统计出这批数据的TOP10。

分两种情况：

  1. 如果每个数据元素只出现在一台机器上：可以直接分机器统计，得到top10，然后再100台机器的top10中求全局top10，k路归并，用堆优化
  2. 每个元素不一定只出现在一台机器上，可能同时出现在多台机器上：
    1. 遍历一遍所有数据，重新hash取摸，如此使得同一个元素只出现在单独的一台电脑中，然后采用上面所说的方法，统计每台电脑中各个元素的出现次数找出TOP10，继而组合100台电脑上的TOP10，找出最终的TOP10。
    2. 暴力求解：直接统计统计每台电脑中各个元素的出现次数，然后把同一个元素在不同机器中的出现次数相加，最终从所有数据中找出TOP10。

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

有海量个文件，知道每个文件的大小，给定100个桶，把这些文件塞到桶里，尽量使得每个桶里装的东西大小差不多

  1. 先对文件按照文件大小从大到小排序
  2. 将文件顺序放入桶中，每次都选取当前容量最小的桶，这里就需要用一个堆来维护当前这100个桶里面的文件大小了，每次需要选出当前容量最小的桶，加了数据之后，更新这个桶的容量，再放回堆中。