一、Top K问题

1、含义

在海量数据找出频率最高的前k个数，或从海量数据中找出最大的前k个数，

2、举例

1、有10个文件，每个文件1GB。文件内每行存放字符串，可能重复，内存限制大小是1MB。按照字符串频度排序；返回频数最高的100个词。

• 搜索最热门的10个查询词。
• 在歌曲库中统计下载最高的前10首歌。
• 提取某日访问网站次数最多的那个IP。
• 找出出现次数最多的身份证号。

3、实际

// Shopee二面
Datetime,              keyword, count
2021-01-01 08：00：00, toys,     1
2021-01-01 08：01：00, makeup,   2
2021-01-01 08：01：00, cups,     3
2021-01-01 08：02：00, abc,      1
2021-01-01 08：03：00, candy,    5
….

2021-01-01 09：30：00, toys, 2

给定：csv 10T， 1 driver 256 G memory， 512 T storage
求解：top 10 keywords

二、解决

1、好方案：分治+Trie树/Hash+小顶堆

• S1、将数据集按照Hash方法分解成多个小数据集；
• S2、用Trie树或Hash统计每个小数据集中的query词频；用小顶堆求出每个数据集中出现频率最高的前K个数。
• S3、（这里可能涉及Trie树/Hash合并）在所有top K中求出最终的top K。

2、其他

1、全排序

• 步骤： 先排序，如快排，最快时间复杂度一般为O(nlogn)。
  32位机器，每个float类型占4字节，1亿浮点数就占400MB( 4*10^8/2^20 )的存储空间。
• 问题： 目的的找出最大10000个数即可，而排序却将所有的元素都排序了，做了很多的无用功。

2、局部淘汰法

• 步骤： 用一个容器保存前10000个数，如果后续所有元素都比容器内10000个数小，那容器内就是最大10000个数。如果某元素比容器内最小数字大，则删掉容器内最小元素，并将该元素插入容器。时间复杂度为O(n+m^2)，其中m为容器的大小，即10000。

3、分治法

• 步骤：
  S1：分-- 将1亿个数据分成100份，每份100万个数据，找到每份数据中最大的10000个，最后在剩下的100*10000个数据里面找出最大的10000个。如果100万数据选择足够理想，那么可以过滤掉1亿数据里面99%的数据。
  S2：100万个数找最大10000个数方法：用快排，将数据分为2堆，如果大的那堆个数N大于10000个，继续对大堆快速排序一次分成2堆，如果大的那堆个数N大于10000个，继续对大堆快速排序一次分成2堆，如果大堆个数N小于10000个，就在小的那堆里面快速排序一次，找第10000-n大的数字；递归以上过程，就可以找到第1w大的数。
  S3：参考上面的找出第1w大数字，就可以类似的方法找到前10000大数字了。此方法要每次内存空间为10^6*4=4MB，一共要101次比较。

4、Hash法

• 步骤：
  S1：先Hash去重。如果重复率很高，会减少很大内存消耗。
  S2：通过分治法或最小堆法查找最大的10000个数。

5、最小堆

• 步骤：
  S1：先读入前10000个数来创建大小为10000的最小堆，然后遍历后续的数字，并于堆顶（最小）数字进行比较。
  S2：如果比最小数小，则读取后续数字；如果比堆顶数大，则替换堆顶元素并重调最小堆，直至全部遍历完。
  S3：按中序遍历输出堆中10000个数字。该算法时间复杂度为O(nmlogm)，空间复杂度是10000（常数）。

三、延申

处理海量数据问题方法：

• 分治/hash映射 + hash统计 + 堆/快速/归并排序；
• 双层桶划分；
• Bloom filter/Bitmap；
• Trie树/数据库/倒排索引；
• 外排序；
• 分布式处理之Hadoop/Mapreduce。

四、举一反三练习

……

五、参考

1、海量数据中的TOPK问题小结
2、海量数据处理 - 10亿个数中找出最大的10000个数（top K问题）
3、10 亿个数中找出最大的 10000 个数（topK 问题）
4、Top K Problems
5、教你如何迅速秒杀掉：99%的海量数据处理面试题