网速1m等于多少kb流量（浅析网速流量换算方法）

“分而治之”（和）方法（也称为“分而治之”）是高效算法设计中常用的一种技术。

有一个1G大小的文件，里面每一行是一个英文单词，单词大小不超过16字节，内存限制为1M。请设计一个算法思路，返回频率最高的 100 个单词。

乍一看，要处理的文件大小是1G，但内存只有1M。我们知道用 1M 的内存空间来处理 1G 的文件是不现实的。按照1M的上限，假设每个字为16字节，那么1M的内存可以处理多少个字呢？

让我们计算一下， 1M = 1024 KB = 1024 * 1024 B 。1M / 16B = 2^16 个词，那么 1G 有多少个词？有2^26个字，但实际应该不止这个，因为我们是按照最大字长来计算的，有可能只有两个字母的字。

选项1粗略的想法：

分治/哈希映射：依次读取文件，对于每个单词x，取hash(x)%5000，然后将这个值存入5000个小文件中（记为x0,x1,...x4999）这样每个文件大概200k左右，如果有的文件超过1M，可以用类似的方法继续划分，直到分解后的小文件大小不超过1M。哈希统计：是的文件，使用trie tree/etc.统计每个文件中出现的词和对应的频率。堆/合并排序：取出出现频率最高的100个词（可以使用100个节点的最小堆），保存100个词和对应的频率放入文件，然后我们得到5000个文件，最后将5000个文件合并（类似于归并排序）。

郑重声明：本文版权归原作者所有，转载文章仅出于传播更多信息之目的。如作者信息标注有误，请尽快联系我们修改或删除，谢谢。