这个题怎么做啊？ - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

这个题怎么做啊？

这个题怎么做啊？# JobHunting - 待字闺中

l*r2010-12-10 08:12

1 楼

有一个1G大小的一个文件，里面每一行是一个词，词的大小不超过16个字节，内存限制
大小是1M。返回频数最高的100个词。

J*i2010-12-10 08:12

2 楼

可以往硬盘写数据吗？

j*u2010-12-10 08:12

3 楼

可以外排，map-reduce
或者以下优化的近似解法：
词+出现次数=20byte
1M可以放50k个词了，假设hashtable是ideal的
比如限制hashtable大小为10k，read file同时build hashtable的时候如果超过了10k个
item就drop频率低的一半，或者简单些用某一阈值
假设词在文件中出现相对均匀这个方法就可以work

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

: 有一个1G大小的一个文件，里面每一行是一个词，词的大小不超过16个字节，内存限制
: 大小是1M。返回频数最高的100个词。

l*r2010-12-10 08:12

4 楼

外排序用英文怎么说？

10k个

【在 j*****u 的大作中提到】

: 可以外排，map-reduce
: 或者以下优化的近似解法：
: 词+出现次数=20byte
: 1M可以放50k个词了，假设hashtable是ideal的
: 比如限制hashtable大小为10k，read file同时build hashtable的时候如果超过了10k个
: item就drop频率低的一半，或者简单些用某一阈值
: 假设词在文件中出现相对均匀这个方法就可以work

c*b2010-12-10 08:12

5 楼

http://en.wikipedia.org/wiki/External_sorting

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

: 外排序用英文怎么说？
:
: 10k个

b*e2010-12-10 08:12

6 楼

嗯，肯定是要 Divide and Conquer 了
读文件的时候按照词的长度和前缀甄别一下，写入不同的子文件中，
每个子文件的前100再来比较一下就可以了。
子文件过大的时候还要继续甄别。
这个其实就是 Bucket sort，只不过用文件当Bucket。

10k个

【在 j*****u 的大作中提到】