Find top K most frequent numbers? - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

Find top K most frequent numbers?

Find top K most frequent numbers?# JobHunting - 待字闺中

l*r2012-11-13 08:11

1 楼

I think I saw this before, but can't recall it.
How to find the top K most frequent numbers from a large number set? (or
from a stream of numbers)
Thanks!

p*22012-11-13 08:11

2 楼

priority queue?

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

: I think I saw this before, but can't recall it.
: How to find the top K most frequent numbers from a large number set? (or
: from a stream of numbers)
: Thanks!

w*x2012-11-13 08:11

3 楼

selection sort?

c*a2012-11-13 08:11

4 楼

priority queue+comparator( value, freq)?

c*t2012-11-13 08:11

5 楼

use files as hashmap?

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

: I think I saw this before, but can't recall it.
: How to find the top K most frequent numbers from a large number set? (or
: from a stream of numbers)
: Thanks!

c*s2012-11-13 08:11

6 楼

This is what I heard.
You can first build a hash table to map number to its frequency.
Then you know range of the number and has enough space, you can use counting
sort to sort the frequency to get the top k elements.
If not, you can use merge sort to sort the frequency. But because of most of
the frequency can be very small. It is very likely that they are not in the
top K positions. So you can estimate a threshold to filter this frequency.
The frequency below this threshold in each sublist is not needed to be
considered when sorting. After merging, if you have top K numbers, then you
are done.
If not, lower the threshold, and sort the remaining frequency again until
you get K numbers.
To come up with an threshold, we can randomly sample a subset of all
frequency and do the estimate, or we can use a max-heap of the frequency.
The later approach seems to be a standard one.

c*t2012-11-13 08:11

7 楼

请问ls这几位，priority queue, selection sort 和 hashmap 都需要大空间储存吧，
尤其hashmap不太可能用。
我觉得external merge sort和用file作hashmap似乎更可行啊。

counting
of
the
considered
you

【在 c********s 的大作中提到】

: This is what I heard.
: You can first build a hash table to map number to its frequency.
: Then you know range of the number and has enough space, you can use counting
: sort to sort the frequency to get the top k elements.
: If not, you can use merge sort to sort the frequency. But because of most of
: the frequency can be very small. It is very likely that they are not in the
: top K positions. So you can estimate a threshold to filter this frequency.
: The frequency below this threshold in each sublist is not needed to be
: considered when sorting. After merging, if you have top K numbers, then you
: are done.

w*x2012-11-13 08:11

8 楼

题目看错了, 求正解

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

: I think I saw this before, but can't recall it.
: How to find the top K most frequent numbers from a large number set? (or
: from a stream of numbers)
: Thanks!

d*g2012-11-13 08:11

9 楼

用file作hashmap，求解释~

【在 c********t 的大作中提到】

: 请问ls这几位，priority queue, selection sort 和 hashmap 都需要大空间储存吧，
: 尤其hashmap不太可能用。
: 我觉得external merge sort和用file作hashmap似乎更可行啊。
:
: counting
: of
: the
: considered
: you