S****h
发帖数: 558 | 1 It is a small bay area IT firm. They asked first how to find 10 most
frequent strings from 10 billion (string, frequency) pairs. Easy, use heap
O(10^9*log10). Then they asked the second question.
How to find 10 most frequent strings in 10 billion string list?
Not much idea. I answered to sweep once to build (string,frequency) pair
and then sweep again to find the first 10. Is there any better way? |
D*******e
发帖数: 151 | 2 split the strings into buckets, e.g., from a to z 26 ones
count them separately
then merge the results |
D*******e
发帖数: 151 | 3 guarantee the splitting is exclusive |
f*******t
发帖数: 7549 | 4 以前有帖讨论过。可以用bloom filter把只出现一次的string去掉，通过的用堆存，算
是一种实际应用中比较有效的办法吧。
不知道最佳答案是什么 |
d*******d
发帖数: 2050 | 5 bloom filter的具体用法能说说么?
【在 f*******t 的大作中提到】
: 以前有帖讨论过。可以用bloom filter把只出现一次的string去掉，通过的用堆存，算
: 是一种实际应用中比较有效的办法吧。
: 不知道最佳答案是什么
|
f*******t
发帖数: 7549 | 6 http://en.wikipedia.org/wiki/Bloom_filter
非常节省空间的验证数据是否出现过的数据结构。很简单，就是几个hashtable，每个
key只占1个bit，用来标记是否出现过。
会有false positive，也就是说你检验一个数据，在几个hashtable里对应的bit都为1
，但实际上它没出现过。
而出现过的绝对不会漏判。
【在 d*******d 的大作中提到】
: bloom filter的具体用法能说说么?
|
d*******d
发帖数: 2050 | 7 这个我明白.如何用它来过滤掉只出现一次的呢?
这和直接用一个hashmap来count的区别在哪里呢?
1
【在 f*******t 的大作中提到】
: http://en.wikipedia.org/wiki/Bloom_filter
: 非常节省空间的验证数据是否出现过的数据结构。很简单，就是几个hashtable，每个
: key只占1个bit，用来标记是否出现过。
: 会有false positive，也就是说你检验一个数据，在几个hashtable里对应的bit都为1
: ，但实际上它没出现过。
: 而出现过的绝对不会漏判。
|
