k*******r
发帖数: 355 | 1 我知道无限stream中维持topK frequent query是用hashtable加一个大小为K的minheap
但sliding window中维持topk频繁的query这应该怎么做？如果用一个大小为K的
minheap再加一个大小为N-k的maxheap, 再加上hash table应该可以搞定。但通常N>>K
所以维持N-k的maxheap代价太大。
这题标准答案应该是什么样的？ |
s**x
发帖数: 7506 | 2 我搞糊涂了，moving window 的时候把左边移出去的相应的hash table 项 减1，右边
刚进入window的加1就行了吧？ |
k*******r
发帖数: 355 | 3 hash table减1以后，可能就不再是topK元素了，就要从原来小于topK的N-k个元素中找
一个顶上来。这样就不得不在N-K个元素中维持一个类似于heap的数据结构。但N>>k,这
样滑动一次, 为了维持heap最坏需要O(logN)开销太大啊 |
g*********e
发帖数: 14401 | 4 heap必须得把window里的东西都存在里面吧。想不出能怎么优化。哪的题？ |
s**x
发帖数: 7506 | 5
嗯，那就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*******r
发帖数: 355 | 6 但delete操作以后，如果使得这K个element里面最小的一个减1，那就不得不和剩下N-k
个元素做某种比较，那N就出现在时间复杂度里面了，没法做到logK吧 |
s**x
发帖数: 7506 | 7
-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******7
发帖数: 1758 | 8 剩下N-k没必要维护一个 max heap , 记录一个最大值足矣，所以还是了log k
-k
【在 k*******r 的大作中提到】
: 但delete操作以后，如果使得这K个element里面最小的一个减1，那就不得不和剩下N-k
: 个元素做某种比较，那N就出现在时间复杂度里面了，没法做到logK吧
|
k*******r
发帖数: 355 | 9 剩下N-k记录一个最大值是不够的，
因为做减1操作时如果刚好减到了原来N-K个纪录中最大值那里，你要判断这个最大值减
一后是否还是最大，如果不是最大用那哪个变成新的最大值。这就要一个N-K大小的
heap来维护 |
p**o
发帖数: 3409 | 10 "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*******r
发帖数: 355 | 11 就是比如在任意时刻，会查当过去8小时的top100个访问最频繁的google query. 现在
要求设计一种数据结构方便这种查询
相当于有一个8小时的time window不断滑动，随时要查这个time window内访问最频繁
的top100 query |
