题目描述
假如有一个 1G 大小的文件，文件里每一行是一个词，每个词的大小不超过 16byte，要求返回出现频率最高的 100 个词。内存大小限制是 10M。
解决方案
方案一
- 分治处理：将大文件分割成多个小文件，确保每个小文件能被加载到 10M 内存中。可以根据单词的哈希值对文件进行划分，将相同哈希值范围的单词写入同一个小文件。
- 统计词频：依次处理每个小文件，使用哈希表（字典）统计每个小文件中单词的出现频率。
- 维护小顶堆：对于每个小文件的统计结果，使用一个大小为 100 的小顶堆来维护当前出现频率最高的 100 个单词。如果堆的大小小于 100，则直接将单词及其频率插入堆中；如果堆的大小已经达到 100，且当前单词的频率大于堆顶元素的频率，则替换堆顶元素并调整堆。
- 合并结果：处理完所有小文件后，堆中存储的就是整个大文件中出现频率最高的 100 个单词。
如果这个 1G 的大文件中有某个词词频过高，可能导致小文件大小超过 10m。这种情况下该怎么处理呢？
方案二
- 外部排序：使用多路归并排序对大文件进行排序，这样相同的单词肯定是紧挨着的。多路归并排序对大文件进行排序的步骤如下：
- 将文件按照顺序切分成大小不超过 2m 的小文件，总共 500 个小文件
- 使用 10MB 内存分别对 500 个小文件中的单词进行排序
- 使用一个大小为 500 大小的堆，对 500 个小文件进行多路排序，结果写到一个大文件中
- 其中第三步，对 500 个小文件进行多路排序的思路如下：
- 初始化一个最小堆，大小就是有序小文件的个数 500。堆中的每个节点存放每个有序小文件对应的输入流。
- 按照每个有序文件中的下一行数据对所有文件输入流进行排序，单词小的输入文件流放在堆顶。
- 拿出堆顶的输入流，并其下一行数据写入到最终排序的文件中，如果拿出来的输入流中还有数据的话，那么将这个输入流再一次添加到栈中。否则说明该文件输入流中没有数据了，那么可以关闭这个流。
- 循环这个过程，直到所有文件输入流都没有数据为止。
- 维护小顶堆：在合并统计结果的过程中，使用一个大小为 100 的小顶堆来维护当前出现频率最高的 100 个单词。