P****e
发帖数: 56 | 1 作为系统设计题，问: 寻找数据流中出现最频繁的k个元素(find top k frequent
items in a data stream)。注意是数据流，所以无法一下子知道所有数据。
https://soulmachine.gitbooks.io/system-design/content/cn/bigdata/heavy-
hitters.html
方案1: HashMap + Heap
用一个 HashMap，存放所有元素出现的次数，用一个小根堆，容量为k
，存放目前出现过的最频繁的k个元素，
每次从数据流来一个元素，如果在HashMap里已存在，则把对应的计数器增1，如果不存
在，则插入，计数器初始化为1
在堆里查找该元素，如果找到，把堆里的计数器也增1，并调整堆；如果没有找到，把
这个元素的次数跟堆顶元素比较，如果大于堆丁元素的出现次数，则把堆丁元素替换为
该元素，并调整堆
我知道这不是最优方案，但即使这个方案，也有两个问题：
1）
PriorityQueue只能给出最大值，如果要返回top K, 需要poll() (python 里叫pop())
K 次， 每次Poll() 都是把最大值去掉的。这样返回完top K, 这个 PriorityQueue也
就空了。 以后这个top K 数据就失去了？5分钟后又要返回最新的top K怎么办？
2）
假设K =3 , 如果我现在的PriorityQueue 有 10, 3, 8。 这时候来了一个9. 我用什么
操作能把3给踢了出去？ 我如果就吧9插进去，这时候就有4个数字了，怎么知道最小的
是3？ PriorityQueue只能知道最大的，不能知道最小的啊。
不胜求解还请指教 | s********k
发帖数: 6180 | 2 求最大K，不是用大根堆，是小根堆，就是Top是这K个里面最小的。
k
【在 P****e 的大作中提到】
: 作为系统设计题，问: 寻找数据流中出现最频繁的k个元素(find top k frequent
: items in a data stream)。注意是数据流，所以无法一下子知道所有数据。
: https://soulmachine.gitbooks.io/system-design/content/cn/bigdata/heavy-
: hitters.html
: 方案1: HashMap + Heap
: 用一个 HashMap，存放所有元素出现的次数，用一个小根堆，容量为k
: ，存放目前出现过的最频繁的k个元素，
: 每次从数据流来一个元素，如果在HashMap里已存在，则把对应的计数器增1，如果不存
: 在，则插入，计数器初始化为1
: 在堆里查找该元素，如果找到，把堆里的计数器也增1，并调整堆；如果没有找到，把
| P****e
发帖数: 56 | 3 明白了。确实是我没看仔细。可是如果用了最小堆，只能解决“每次来一个新的成员如
果比现有最小成员大，剔除现有最小成员，把新成员加入”的问题，要return top K,
每次要把这个堆的每个元素都pop()出来，这样一来这个堆不久摧毁了, 以后还要
return top K 怎么处理? 难道每次pop()出来，return top k, 再放回去?
还有，如果考虑数据量太大单机一个heap放不下，放入几个机器里做好几个heap，最后
汇总到另外一台机器上的global heap. 如果每个单机都用的是最小堆，怎么汇总？ 汇
总时候难道不需要把每个单机上最大的item放到global heap上马？min heap 找最大
item 不又要吧所有item都pop() 掉？ |
|
