请教一道经典题目：寻找数据流中出现最频繁的k个元素 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Programming - 葵花宝典

请教一道经典题目：寻找数据流中出现最频繁的k个元素

请教一道经典题目：寻找数据流中出现最频繁的k个元素# Programming - 葵花宝典

m*a2018-10-20 07:10

1 楼

和罗根滚了一次床单以后，青梅竹马的男朋友不要了，为了救杀父仇人把自己的爷爷也
干掉了
太狗血的情节了。莫非是金刚狼1里面的催眠术学直接嫁接到2里面了？还是说once go
什么, never go back

r*y2018-10-20 07:10

2 楼

一京族有时候张嘴一口东北味儿，台词有点差。佟大为就好多了，台词很好。佟大为
演技真好，人红也不是没道理明显比里面几个小演员强出好几条街去。感觉他人也是
比较实诚的内种当年追马伊琍马跟他应该更幸福，他也不比文章差。不过他老婆演技
真是，白科班儿出身了。突然发现关悦嘴长的跟关之琳还真挺像的。

P*e2018-10-20 07:10

3 楼

作为系统设计题，问: 寻找数据流中出现最频繁的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只能知道最大的，不能知道最小的啊。
不胜求解还请指教

w*r2018-10-20 07:10

4 楼

size matters

i*y2018-10-20 07:10

5 楼

关悦让人看了有去啃包子的冲动
还是别和关之琳比了吧
虽然关之琳也就是眼睛大

【在 r******y 的大作中提到】

: 一京族有时候张嘴一口东北味儿，台词有点差。佟大为就好多了，台词很好。佟大为
: 演技真好，人红也不是没道理明显比里面几个小演员强出好几条街去。感觉他人也是
: 比较实诚的内种当年追马伊琍马跟他应该更幸福，他也不比文章差。不过他老婆演技
: 真是，白科班儿出身了。突然发现关悦嘴长的跟关之琳还真挺像的。

s*k2018-10-20 07:10

6 楼

求最大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，并调整堆；如果没有找到，把

m*a2018-10-20 07:10

7 楼

我看是持久能力，反正金刚狼不会累

【在 w********r 的大作中提到】

: size matters

c*d2018-10-20 07:10

8 楼

李建军这么痞子样，居然演过永不瞑目 v2 的肖童，v1里面的陆毅那么帅。

P*e2018-10-20 07:10

9 楼

明白了。确实是我没看仔细。可是如果用了最小堆，只能解决“每次来一个新的成员如
果比现有最小成员大，剔除现有最小成员，把新成员加入”的问题，要return top K,
每次要把这个堆的每个元素都pop()出来，这样一来这个堆不久摧毁了, 以后还要
return top K 怎么处理? 难道每次pop()出来，return top k, 再放回去?
还有，如果考虑数据量太大单机一个heap放不下，放入几个机器里做好几个heap，最后
汇总到另外一台机器上的global heap. 如果每个单机都用的是最小堆，怎么汇总？汇
总时候难道不需要把每个单机上最大的item放到global heap上马？min heap 找最大
item 不又要吧所有item都pop() 掉？

d*02018-10-20 07:10

10 楼

因为女主没有试过她爷爷的

go

【在 m********a 的大作中提到】

: 和罗根滚了一次床单以后，青梅竹马的男朋友不要了，为了救杀父仇人把自己的爷爷也
: 干掉了
: 太狗血的情节了。莫非是金刚狼1里面的催眠术学直接嫁接到2里面了？还是说once go
: 什么, never go back

r*y2018-10-20 07:10

11 楼

啃包子为啥？肿肿的？哈哈。

【在 i********y 的大作中提到】

: 关悦让人看了有去啃包子的冲动
: 还是别和关之琳比了吧
: 虽然关之琳也就是眼睛大

b*e2018-10-20 07:10

12 楼

不应该啊，日本应该老爸爷爷啥的都试过才对

【在 d*****0 的大作中提到】

: 因为女主没有试过她爷爷的
:
: go

r*y2018-10-20 07:10

13 楼

可能故意这么打扮？而且有些发福。不管怎样比陆毅还是差远了。也许被内啥了海盐
懂得。。。

【在 c**********d 的大作中提到】

: 李建军这么痞子样，居然演过永不瞑目 v2 的肖童，v1里面的陆毅那么帅。

P*e2018-10-20 07:10

14 楼

管那么多干啥反正那妞不错。。。

go

【在 m********a 的大作中提到】

d*02018-10-20 07:10

15 楼

爷爷要追求长生不老，估计要禁欲

【在 b*****e 的大作中提到】

: 不应该啊，日本应该老爸爷爷啥的都试过才对

b*e2018-10-20 07:10

16 楼

禁欲了就还不如按摩棒，就别怪孙女不留情了

【在 d*****0 的大作中提到】

: 爷爷要追求长生不老，估计要禁欲

B*a2018-10-20 07:10

17 楼

不能同意更多

w*r2018-10-20 07:10

18 楼

肯定是金刚狼射出的东西有活血养颜的作用，得一发年轻1岁。
是个女的都得选金刚狼。

【在 b*****e 的大作中提到】

: 禁欲了就还不如按摩棒，就别怪孙女不留情了

w*r2018-10-20 07:10

19 楼

其实老头直接给金刚狼吹，就能重获青春了。只不过老头口味没那么重。人家会高
科技，懂得直接提取骨髓干细胞。

h*v2018-10-20 07:10

20 楼

那个最后爪子被切割，然后怎么长出来的？长出来的成色也变了，是啥玩意后来？

【在 w********r 的大作中提到】

: 其实老头直接给金刚狼吹，就能重获青春了。只不过老头口味没那么重。人家会高
: 科技，懂得直接提取骨髓干细胞。

w*r2018-10-20 07:10

21 楼

没看过金钢狼1吧。
金钢狼本身就长2个骨爪。被人工手术植入了钢抓。
现在被切下去后，自己恢复原貌了。

【在 h**v 的大作中提到】

: 那个最后爪子被切割，然后怎么长出来的？长出来的成色也变了，是啥玩意后来？

d*o2018-10-20 07:10

22 楼

概括下这片子
白男跟亚女发展了关系，还征服了亚女闺蜜
白女使坏，最后生死未卜（有需要还会出来？）
亚女一家男人全死光

T*u2018-10-20 07:10

23 楼

好莱坞异族女的都这样吧,忠心,虔诚,其实就是低等生物里有身份的女人攀上高枝,被救
赎的套路.

g*t2018-10-20 07:10

24 楼

嗯
而且救赎她们的一般还是洋屌丝（普通人（）

【在 T*****u 的大作中提到】

: 好莱坞异族女的都这样吧,忠心,虔诚,其实就是低等生物里有身份的女人攀上高枝,被救
: 赎的套路.

l*z2018-10-20 07:10

25 楼

金刚狼怎么能算是钓丝? 绝对的高富帅啊.

【在 g******t 的大作中提到】

: 嗯
: 而且救赎她们的一般还是洋屌丝（普通人（）

m*a2018-10-20 07:10

26 楼

恩，长生不老，随便存点东西，过几百年就古董了

【在 l****z 的大作中提到】

: 金刚狼怎么能算是钓丝? 绝对的高富帅啊.

R*a2018-10-20 07:10

27 楼

到这个层次，基本不在乎富不富了吧

【在 m********a 的大作中提到】

: 恩，长生不老，随便存点东西，过几百年就古董了

k*r2018-10-20 07:10

28 楼

其实长生这个设定太bug了，几个alpha level的都垂涎不已啊。

【在 R***a 的大作中提到】

: 到这个层次，基本不在乎富不富了吧

m*a2018-10-20 07:10

29 楼

高帅富死得快，屌丝屌万年。守恒的

【在 k***r 的大作中提到】

: 其实长生这个设定太bug了，几个alpha level的都垂涎不已啊。

l*z2018-10-20 07:10

30 楼

人家是长生的高富帅,这个才牛啊.

【在 m********a 的大作中提到】

: 高帅富死得快，屌丝屌万年。守恒的

m*a2018-10-20 07:10

31 楼

在变异人里面不能算高帅富，基本上每次都是他被打得最惨。主要是血长，还有主角光
环，跟星矢一个类型的
真要弄死他的话，电磁王或者博士定身，然后头砍掉就行了

【在 l****z 的大作中提到】

: 人家是长生的高富帅,这个才牛啊.

R*a2018-10-20 07:10

32 楼

按照x-men前传里面那个继承了金刚狼特技的超级x-men来看，
砍头是没事的。
也就是头砍下来以后，头和身体都能保持不死。这样充其量就是
把头和身子分开，和封印类似。kelly hu扮演的那个女版金刚狼不就是
被封印了么？
另外，不能排除金刚狼有孙悟空的本领，就是头不能接上来的情况下，
可以身体里再生一个头出来。

【在 m********a 的大作中提到】

: 在变异人里面不能算高帅富，基本上每次都是他被打得最惨。主要是血长，还有主角光
: 环，跟星矢一个类型的
: 真要弄死他的话，电磁王或者博士定身，然后头砍掉就行了

m*a2018-10-20 07:10

33 楼

砍头没事，那个超级x-man反派最后是怎么挂的？
金刚狼他哥哥没有做金属处理，就是因为当时觉得他身体可能承受不住。所以绝对不会
是永远不死的。

【在 R***a 的大作中提到】

: 按照x-men前传里面那个继承了金刚狼特技的超级x-men来看，
: 砍头是没事的。
: 也就是头砍下来以后，头和身体都能保持不死。这样充其量就是
: 把头和身子分开，和封印类似。kelly hu扮演的那个女版金刚狼不就是
: 被封印了么？
: 另外，不能排除金刚狼有孙悟空的本领，就是头不能接上来的情况下，
: 可以身体里再生一个头出来。

m*a2018-10-20 07:10

34 楼

在前传里面，金刚狼哥哥和金刚狼有这么个对话，大概是说，怎么才能弄死你，把头砍
下来？
暗示砍头是他们这种不死人的弱点

【在 R***a 的大作中提到】

R*a2018-10-20 07:10

35 楼

呵呵，电影没看完啊，演职员表结束以后还有个镜头

【在 m********a 的大作中提到】

: 砍头没事，那个超级x-man反派最后是怎么挂的？
: 金刚狼他哥哥没有做金属处理，就是因为当时觉得他身体可能承受不住。所以绝对不会
: 是永远不死的。

y*n2018-10-20 07:10

36 楼

唔
维基里面是这么说的:
Xavier Protocols, a series of profiles created by Xavier that lists the stre
ngths and weaknesses of the X-Men, states that Wolverine's healing factor is
increased to "incredible levels" and theorizes that the only way to stop hi
m is to decapitate him and remove his head from the vicinity of his body.
砍头是管用的，不过砍掉之后还得把头从身子旁边移开

【在 m********a 的大作中提到】

m*a2018-10-20 07:10

37 楼

头是个很TRICKY的部位。第一战里面的反派也是爆头死的。按设定的话，他的牛逼程度
不比金刚狼差吧。能无限吸能给自己用

stre
is
hi

【在 y****n 的大作中提到】

: 唔
: 维基里面是这么说的:
: Xavier Protocols, a series of profiles created by Xavier that lists the stre
: ngths and weaknesses of the X-Men, states that Wolverine's healing factor is
: increased to "incredible levels" and theorizes that the only way to stop hi
: m is to decapitate him and remove his head from the vicinity of his body.
: 砍头是管用的，不过砍掉之后还得把头从身子旁边移开

m*a2018-10-20 07:10

38 楼

哦，你这么一说好像还有点印象。

【在 R***a 的大作中提到】

: 呵呵，电影没看完啊，演职员表结束以后还有个镜头

w*r2018-10-20 07:10

39 楼

啥镜头，
我操。没看到

【在 R***a 的大作中提到】

: 呵呵，电影没看完啊，演职员表结束以后还有个镜头