H******7
发帖数: 1728 | 1 find top K most occurring words in streaming data 这题怎么做比较好 |
w*******e
发帖数: 83 | 2 hashtable + heap. Hashtable 记录words发生的次数, heap保持top k words.每次一
个新的word来了后更新hashtable, 然后和heap的root 比较 |
T******7
发帖数: 1419 | 3 though, hashTable is going to grow.....
【在 w*******e 的大作中提到】
: hashtable + heap. Hashtable 记录words发生的次数, heap保持top k words.每次一
: 个新的word来了后更新hashtable, 然后和heap的root 比较
|
l******n
发帖数: 648 | 4 可是这样空间太大了
一个词一个hash
这要几千个词
而且大部分不常见，就是1，2这种
非常不efficient，space wise
【在 w*******e 的大作中提到】
: hashtable + heap. Hashtable 记录words发生的次数, heap保持top k words.每次一
: 个新的word来了后更新hashtable, 然后和heap的root 比较
|
m*********t
发帖数: 527 | 5 那就用 prefix trie，每个节点纪录从 root 到这个节点构成的词的频率 （0 表示不
构成词）。比 hash table 要快一些也省空间。top k 可以用 max heap，用红黑树也
行（比较方便删最小的那个）。 |
d******e
发帖数: 2265 | 6 要是真用到steam,几千个词算什么。
多数情况就是十几，几十台机器在搞。
【在 l******n 的大作中提到】
: 可是这样空间太大了
: 一个词一个hash
: 这要几千个词
: 而且大部分不常见，就是1，2这种
: 非常不efficient，space wise
|
T******7
发帖数: 1419 | 7 可以用hashtable.
还可以周期性做 garbage collection. 把小于阈值的都清了 |
l******n
发帖数: 648 | 8 可以是肯定可以
这不是讨论最优解么
【在 d******e 的大作中提到】
: 要是真用到steam,几千个词算什么。
: 多数情况就是十几，几十台机器在搞。
|
