Home Page
Search
\begin{md} ## 题目 有一个 1 G 大小的一个文件,里面每一行是一个词,词的大小不超过 16 字节,内存限制大小是 1 M,要求返回频数最高的 100 个词。 ## 思路 **采用分治的思想** 1. 顺序读取文件,对于每个词 x, 取 hash(x) % 5000, 然后按照该值存储到 5000 个小文件 $a_0, a_1, ..., a_{4999}$ 中,这样每个文件大概 200 KB,如果文件大小过大,再用类似的方法分解,直到单文件不超过 800 KB。 2. 对每个小文件,统计文件中每个词的词频,并取出频率最大的 100 个词,并把 100 个词及其频率放入新文件,这样又得到了 5000 个文件。 3. 对这 5000 个记录了词频的文件进行归并。 \end{md}
Home Page