b*********n
发帖数: 1258 | 1 you have a billion google searches a day, design a data structure which
lets you pull out the top 100 unique ones at the end of the day.
我的想法是create hashtable
scan billion data 一次，在hashtable纪录每个query的次数
然后再scan billion data一次,通过heap和hashtable找到top 100
不过这样的话,billion data会被scan 2次，disk i/o会很大
不知道有没有什么scan billion data一次就可以找到top 100的办法
大家讨论一下 |
b*********n
发帖数: 1258 | 2 能简单说一下吗？
只用heap,不用hash吗？ |
b*********n
发帖数: 1258 | 3 hash_table可以iterate吗？
我怎么记得c++里面hash_table是不可以iterate的
另外，hash_table可以distribute到多个机器上吗？ |
g*******y
发帖数: 1930 | 4 你发现我删贴了没，我的方法不对
iterate是没有问题的吧，你可以自己写hash，比如说是数组挂链表那种。
有个问题的是，如果10billion里面，前面7billion都是不同的只出现1次的query，那
就很麻烦了。这样你的hash至少也是这个量级！
当然，如果query的平均出现次数都很多的话，hash就可以解决了。
【在 b*********n 的大作中提到】
: hash_table可以iterate吗？
: 我怎么记得c++里面hash_table是不可以iterate的
: 另外，hash_table可以distribute到多个机器上吗？
|
J******d
发帖数: 506 | 5 不太理解LZ的做法，能不能给解释一下？
如果top 100个query其实也就query了10次以内。
1 billion search里面的hash value有大量重合的怎么办？
如何确定哪些是top 100呢？
还是我理解错LZ的意思了。
【在 b*********n 的大作中提到】
: you have a billion google searches a day, design a data structure which
: lets you pull out the top 100 unique ones at the end of the day.
: 我的想法是create hashtable
: scan billion data 一次，在hashtable纪录每个query的次数
: 然后再scan billion data一次,通过heap和hashtable找到top 100
: 不过这样的话,billion data会被scan 2次，disk i/o会很大
: 不知道有没有什么scan billion data一次就可以找到top 100的办法
: 大家讨论一下
|
n****e
发帖数: 2401 | 6 经典老题了
median of medians, 自己google吧。 |
g*******y
发帖数: 1930 | 7 你指的是linear k-th element selection algorithm? 是的话，明显不对啊。
【在 n****e 的大作中提到】
: 经典老题了
: median of medians, 自己google吧。
|
R*******n
发帖数: 162 | 8 第二次直接 iterate hash table 里的 key就可以了。用 a heap keeps the top 100.
真正做的时候直接上map-reduce了 |
R*******n
发帖数: 162 | 9 第二次直接 iterate hash table 里的 key就可以了。用 a heap keeps the top 100.
真正做的时候直接上map-reduce了 |
