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

发布时间 2023-12-13 13:00:48作者: guoyu1

计算:
所以我们要按照1M的上限来计算,假设每个单词都为16个字节,那么1M的内存可以处理多少个单词呢?
1M = 1024 KB = 1024 * 1024 B 。然后1M / 16B = 2^16个单词
1G大概有多少个单词呢? 有2^26个单词
但是实际中远远不止这些,因为我们是按照最大单词长度算的。

我们需要把这1G的单词分批处理,根据上面的计算,可以分成大于2^10个文件。

索性就分成2000个文件吧,怎么分呢,不能随便分,不能简单的按照单词的顺序然后模2000划分,因为这样有可能相同的单词被划分到不同的文件中去了。

分而治之/hash映射:顺序读文件中,对于每个词x,取hash(x)%2000,然后按照该值存到2000个小文件(记为x0,x1,…x1999)中。这样每个文件大概是200k左右。如果其中的有的文件超过了1M大小,还可以按照类似的方法继续往下分,直到分解得到的小文件的大小都不超过1M。
hash_map统计:对每个小文件,采用trie树/hash_map等统计每个文件中出现的词以及相应的频率。
然后呢,我们对每个文件进行分别处理:按照key-value的方法处理每个单词,最终得出每个文件中包含每个单词和单词出现的次数。然后再建立大小为100的小根堆。一次遍历文件进行处理。