首页 > 代码库 > TopK-微博今日热门话题
TopK-微博今日热门话题
大纲
- TopK on single node
- TopK on multiple nodes
- Realtime topK with low QPS
- Realtime topK with high QPS
- Approx TopK
- MapReduce
一、TopK on single node
从几个关于TopK的算法引出 TopK 系列问题
1. 给你一个无序整数数组,要求求出TopK (Order By Value)
题目地址:http://www.lintcode.com/zh-cn/problem/top-k-largest-numbers/
数据结构:优先队列(minHeap) (当然如果不是数据流的话,使用QuickSelect效率更高)
时间复杂度:O(nlogk)
空间复杂度: O(k)
2. 给你一个微博话题组成的列表,要求求出TopK(Order by Frequency)
题目地址:http://www.lintcode.com/zh-cn/problem/top-k-frequent-words/
分析:这里需要按照String出现的频数来求解TopK,自然不能像刚刚一样直接使用一个PriorityQueue来实现。但基本原理还是一致的。
使用一个HashMap,HashMap<String, Integer> 表明某个String 出现的频数。然后在PQ中存储的是我们自定义的一个数据结构Pair, Pair包含String 和 频数两个变量,自定义一个Comparator按照频数升序排序就可以了。
数据结构:HashMap PriorityQueue
时间复杂度:O(n + nlog(k)) -> O(nlogk)
空间复杂度: O(|n| + k) 其中 |n|表示unique string数目
二、TopK on multiple nodes
1. 现在假设这样一个场景:给你一组10T的文件,文件内容是10million用户当天的搜索记录,求微博今日话题热搜?
这个场景就不能再使用single node 因为一方面文件太大,单机无法处理,另一方面处理速度太慢
这时候就要采用 分&和 的思想
OverView 如下:
- 分成小文件
- 分发给不同的机器处理
- 每个机器分别获得TopK
- 组合这些TopK获得总的TopK
注意这里一个比较关键的地方:怎么来拆分文件呢?
一种思路是按照文件的先后顺序来拆分,这是有问题的,因为假如某个String比较分散,而总次数是能够进入TopK的,但是在SlaveNode上,这个slaveNode可能并没有入选TopK,这就导致了错误。
所以,我们这里采用 Divide by hash value. 这样相同的String都被分给了同一个slaveNode处理。
2. 假设场景二: 有N台机器, 每台机器各自存储单词文件,求所有单词出现频率的TopK
同样的道理,假如直接求各个单机的TopK在合并的话也是会出现问题的。
这里需要ReHash!
三、 Realtime TopK with Low QPS
之前讨论的情况都是 offline 的,那么实时数据又怎么样呢?
TopK-微博今日热门话题