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

有一个1G大小的一个文件 , 里面每一行是一个英文单词 , 词的大小不超过16字节 , 内存限制是1M 。请设计一个算法思路 , 返回频数最高的100个词.
初步一看 , 要处理的文件大小1G , 可内存却只有1M 。我们知道1G的文件用1M的内存空间处理不太现实 。按照1M的上限来计算 , 假设每个单词都为16个字节 , 那么1M的内存可以处理多少个单词?
我们来计算下 , 1M = 1024 KB = 1024 * 1024 B。1M / 16B = 2^16个单词 , 那么1G大概有多少个单词呢?有2^26个单词 , 但是实际中应该不止 , 因为我们是按照最大单词长度来计算的 , 有可能有的单词只有两个字母 。
网速1m等于多少kb流量|浅析网速流量换算方法
文章图片

【网速1m等于多少kb流量|浅析网速流量换算方法】 方案1大概思路:

  1. 分而治之/hash映射:顺序读文件中 , 对于每个词x , 取hash(x)%5000 , 然后按照该值存到5000个小文件(记为x0,x1,…x4999)中 。这样每个文件大概是200k左右 。如果其中的有的文件超过了1M大小 , 还可以按照类似的方法继续往下分 , 直到分解得到的小文件的大小都不超过1M 。
  2. hash统计:对每个小文件 , 采用trie树/hash_map等统计每个文件中出现的词以及相应的频率 。
  3. 堆/归并排序:取出出现频率最大的100个词(可以用含100个结点的最小堆) , 并把100个词及相应的频率存入文件 , 这时我们又得到了5000个文件 。最后把这5000个文件进行归并(类似与归并排序)的过程 。