诚求审稿机会，有机化学 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>EB23 - 劳工卡

诚求审稿机会，有机化学

诚求审稿机会，有机化学# EB23 - 劳工卡

k*r2017-06-13 07:06

1 楼

我知道无限stream中维持topK frequent query是用hashtable加一个大小为K的minheap
但sliding window中维持topk频繁的query这应该怎么做？如果用一个大小为K的
minheap再加一个大小为N-k的maxheap, 再加上hash table应该可以搞定。但通常N>>K
所以维持N-k的maxheap代价太大。
这题标准答案应该是什么样的？

d*32017-06-13 07:06

2 楼

本人今年五月博士毕业，主要从事方法学研究，做的东西较杂：光化学（
Photochemistry），金属催化（transition metal catalysis），氟化学（fluorine
chemistry），纳米技术（nano technolgy），机理研究（mechanism study）等，希
望好心人能提供审稿机会，不胜感激。先提前谢过了。email： [email protected]
com

s*x2017-06-13 07:06

3 楼

我搞糊涂了，moving window 的时候把左边移出去的相应的hash table 项减1，右边
刚进入window的加1就行了吧？

k*r2017-06-13 07:06

4 楼

hash table减1以后，可能就不再是topK元素了，就要从原来小于topK的N-k个元素中找
一个顶上来。这样就不得不在N-K个元素中维持一个类似于heap的数据结构。但N>>k,这
样滑动一次, 为了维持heap最坏需要O(logN)开销太大啊

g*e2017-06-13 07:06

5 楼

heap必须得把window里的东西都存在里面吧。想不出能怎么优化。哪的题？

s*x2017-06-13 07:06

6 楼

嗯，那就keep an ordered map for k elements.
就是一直保证这k 个是排序的，update delete etc should be logk.

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

: hash table减1以后，可能就不再是topK元素了，就要从原来小于topK的N-k个元素中找
: 一个顶上来。这样就不得不在N-K个元素中维持一个类似于heap的数据结构。但N>>k,这
: 样滑动一次, 为了维持heap最坏需要O(logN)开销太大啊

k*r2017-06-13 07:06

7 楼

但delete操作以后，如果使得这K个element里面最小的一个减1，那就不得不和剩下N-k
个元素做某种比较，那N就出现在时间复杂度里面了，没法做到logK吧

s*x2017-06-13 07:06

8 楼

-k
貌似还有个变量W for window size. I was assuming W = k.
I would use heap/map size of W.

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

: 但delete操作以后，如果使得这K个element里面最小的一个减1，那就不得不和剩下N-k
: 个元素做某种比较，那N就出现在时间复杂度里面了，没法做到logK吧

s*72017-06-13 07:06

9 楼

剩下N-k没必要维护一个 max heap , 记录一个最大值足矣，所以还是了log k

-k

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

: 但delete操作以后，如果使得这K个element里面最小的一个减1，那就不得不和剩下N-k
: 个元素做某种比较，那N就出现在时间复杂度里面了，没法做到logK吧

k*r2017-06-13 07:06

10 楼

剩下N-k记录一个最大值是不够的，
因为做减1操作时如果刚好减到了原来N-K个纪录中最大值那里，你要判断这个最大值减
一后是否还是最大，如果不是最大用那哪个变成新的最大值。这就要一个N-K大小的
heap来维护

p*o2017-06-13 07:06

11 楼

"sliding window"具体指什么，完整上下文是什么？
听起来不像是说sliding window protocol

minheap
K

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

: 我知道无限stream中维持topK frequent query是用hashtable加一个大小为K的minheap
: 但sliding window中维持topk频繁的query这应该怎么做？如果用一个大小为K的
: minheap再加一个大小为N-k的maxheap, 再加上hash table应该可以搞定。但通常N>>K
: 所以维持N-k的maxheap代价太大。
: 这题标准答案应该是什么样的？

k*r2017-06-13 07:06

12 楼

就是比如在任意时刻，会查当过去8小时的top100个访问最频繁的google query. 现在
要求设计一种数据结构方便这种查询
相当于有一个8小时的time window不断滑动，随时要查这个time window内访问最频繁
的top100 query