[算法] Python 计算出现最多的前100个单词
有一个1G大小的一个文件, 里面每一行是一个词, 词的大小不超过16字节, 内存限制大小是1M. 返回频数最高的100个词.
方案1: 顺序读文件中, 对于每个词x, 取hash(x)%5000，然后按照该值存到5000个小文件(记为x0, x1, ..., x4999)中。这样每个文件大概是200k左右. 如果其中有的文件超过了1M大小, 还可以按照类似的方法继续往下分, 直到分解得到的小文件的大小都不超过1M. 对每个小文件, 统计每个文件中出现的词以及相应的频率(可以采用trie树/hash_map等), 并取出出现频率最大的100个词(可以用含100个结点的最小堆), 并把100词及相应的频率存入文件, 这样又得到了5000个文件. 下一步就是把这5000个文件进行归并(类似于归并排序)的过程了.
在Python下限制内存大小1M, 不容易的感觉.
测试了一下计算一个不到1M的文件所使用的内存大小. 下面的代码也得用15M左右. 跟使用的数据结构有关吧.
可以使用内置的堆和计数器, 比较了一下速度上没有多大差别.
from heapq import nlargest
from memory_profiler import profile
from collections import Counter
def use_heapq():
data = {}
with open('words', 'rb') as words:
for w in words:
w = w[:-1]
# data[w] = data.get(w, 0)+1
data[w] = 1 if w not in data else (data[w]+1)
top100 = nlargest(100, data, key=lambda x:data[x])
for w in top100:
print(w, data[w])
def use_counter():
with open('words', 'rb') as words:
cnt = Counter(words)
print(cnt.most_common(100))
import cProfile
cProfile.run('use_heapq()')
cProfile.run('use_counter()')
查看源码发现, 其实Counter的monst_common也是使用的heapq
def most_common(self, n=None):
'''List the n most common elements and their counts from the most
common to the least. If n is None, then list all element counts.
>>> Counter('abcdeabcdabcaba').most_common(3)
[('a', 5), ('b', 4), ('c', 3)]
'''
# Emulate Bag.sortedByCount from Smalltalk
if n is None:
return sorted(self.items(), key=_itemgetter(1), reverse=True)
return _heapq.nlargest(n, self.items(), key=_itemgetter(1))
