主要看数据量和可用内存大小.
基本解题思路: 分治法(hash), 堆排序.
查询最热门的字符串
从大量数据中找出高频词
堆排序
给定 a、b 两个文件，各存放 50 亿个URL，每个URL各占 64B，内存限制是 4G。 请找出 a、b 两个文件共同的 URL。
每个URL为64B, 那么50亿则为5 000 000 000 * 64 = 5GB * 64 = 320GB.
由于内存大小只有4G, 所以不能一次性把所有URL加载到内存里面. 所以只能采取分治策略, 将一个文件中的URL按照某个特征划分为多个小文件,
使得每个小文件的大小不超过4GB, 这样就可以把小文件读到内存中去处理了.
首先遍历文件a, 对遍历的URL求hash(URL) % 1000, 根据计算结果把遍历到的URL存储到a0, a1, a2.....a999, 这样每个文件大小约为300MB.
对文件b同样的方法处理. 这样处理后, 所有可能相同的URL肯定都在对应的小文件中(不同的URL也可能存在对应的小文件, 因为哈希冲突),
即a0对应b0... a999对应b999, 不对应的小文件不可能存在相同的URL.
接着遍历ai(i>=0 and i<=999), 把URL存在一个HashSet集合中. 然后遍历bi中的每个URL, 看在HashSet集合中是否存在. 存在则说明这就是共同的URL,
将URL输出到单独的文件中.
- 分而治之, 通过哈希取余.
- 对每个子文件进行HashSet统计.
有 10 个文件，每个文件大小为 1G，每个文件的每一行存放的都是用户的 query，每个文件的 query 都可能重复。要求按照 query 的频度排序。
如果query重复率高, 说明不同的query总数比较小, 可以考虑所有把所有的Query都加载到内存的HashMap中. 接着就可以按照Query出现的次数进行排序.
分治法需要根据数据量的大小及可用内存的大小来确定划分问题的规模.
- 用
hash(query)%10将这些大文件划分到10个小文件中. 之后对每个小文件使用HashMap统计query的出现次数, 依次对这些小文件进行排序. - 对所有的文件按照query的次数进行排序, 这里可以使用归并排序(由于无法将所有的Query都读入内存, 因此需要使用外部排序).
- 内存若够，直接读入进行排序.
- 内存不够，先划分为小文件，小文件排好序后，整理使用外排序进行归并.
有 20 个数组，每个数组有 500 个元素，并且有序排列。如何在这 20*500 个数中找出前 500 的数？
TOPk问题, 使用堆排序.
- 首选从各个数组拿出每个数组的最大值, 构建一个大小为20的大顶堆.[heapInsert]
- 将大顶堆的头结点删除掉, 保存到另一个大小为500的数组, 然后向大顶堆插入删除元素所在数组的下一个元素, 重新生成大顶堆.[heapify]
- 重复上面的步骤, 直到大小为500的数组填满, 也找出了最大的前500个数.