l*********r
发帖数: 674 | 1 有一个1G大小的一个文件，里面每一行是一个词，词的大小不超过16个字节，内存限制
大小是1M。返回频数最高的100个词。 |
J*******i
发帖数: 2162 | |
j*****u
发帖数: 1133 | 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*********r
发帖数: 674 | 4 外排序用英文怎么说？
10k个
【在 j*****u 的大作中提到】
: 可以外排，map-reduce
: 或者以下优化的近似解法：
: 词+出现次数=20byte
: 1M可以放50k个词了，假设hashtable是ideal的
: 比如限制hashtable大小为10k，read file同时build hashtable的时候如果超过了10k个
: item就drop频率低的一半，或者简单些用某一阈值
: 假设词在文件中出现相对均匀这个方法就可以work
|
c*b
发帖数: 3126 | |
b*****e
发帖数: 474 | 6 嗯，肯定是要 Divide and Conquer 了
读文件的时候按照词的长度和前缀甄别一下，写入不同的子文件中，
每个子文件的前100再来比较一下就可以了。
子文件过大的时候还要继续甄别。
这个其实就是 Bucket sort，只不过用文件当Bucket。
10k个
【在 j*****u 的大作中提到】
: 可以外排，map-reduce
: 或者以下优化的近似解法：
: 词+出现次数=20byte
: 1M可以放50k个词了，假设hashtable是ideal的
: 比如限制hashtable大小为10k，read file同时build hashtable的时候如果超过了10k个
: item就drop频率低的一半，或者简单些用某一阈值
: 假设词在文件中出现相对均匀这个方法就可以work
|
