最近我一直在玩Python的collections.Counter数据结构。该对象的规范用途是计算文本文件中单词出现的次数:
from collections import Counter
with open(r'filename') as f:
#create a list of all words in the file using a list comprehension
words = [word for line in f for word in line.split()]
c = Counter(words)
最酷的部分是如何使用此结构来找出最常见的单词:
for word, count in c.most_common():
print word, count
我不明白的部分是 most_common()
runs in O(n) time [编辑:这是不正确的。根据 Martijn 的回答,它实际上运行在 O(n log k)]。显然,这意味着它不能在幕后与字典进行比较排序,因为最快的比较排序是 O(nlogn)。
那么collections.Counter是如何实现快速排序的呢?
最佳答案
它不会在 O(n) 时间内运行。当您请求字典中的所有值时,将使用常规排序,即 O(NlogN) 算法。
当请求前 K 个结果时,使用 heapq.nlargest()
调用,这是一种在 O(NlogK) 时间内更有效的方法:
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.iteritems(), key=_itemgetter(1), reverse=True)
return _heapq.nlargest(n, self.iteritems(), key=_itemgetter(1))
答案谈到了在线性时间内完成的计数;构造 Counter
实例,基本上是输入迭代的循环:
for elem in iterable:
self[elem] = self_get(elem, 0) + 1
关于python - Collections.Counter 如何实现快速排序?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/21653996/