python - 如何以最快的方式从 Python 中的计数器中删除频率最低的元素？

Question

我想实现一个计数器，当计数器的大小超过某个阈值时，它会丢弃频率最低的元素。为此，我需要删除出现频率最低的元素。

在 Python 中最快的方法是什么？

我知道 counter.most_common()[-1]，但它会创建一个完整的列表，并且在大量完成时看起来很慢？是否有更好的命令(或者可能是不同的数据结构)？

Answer 1

您可以通过借用 most_common 的实现并进行必要的更改来实现 least_common。

引用collections source in Py2.7 :

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))

要更改它以检索最不常见的，我们只需要进行一些调整。

import collections
from operator import itemgetter as _itemgetter
import heapq as _heapq


class MyCounter(collections.Counter):
    def least_common(self, n=None):
        if n is None:
            return sorted(self.iteritems(), key=_itemgetter(1), reverse=False)  # was: reverse=True
        return _heapq.nsmallest(n, self.iteritems(), key=_itemgetter(1))  # was _heapq.nlargest

测试:

c = MyCounter("abbcccddddeeeee")
assert c.most_common() == c.least_common()[::-1]
assert c.most_common()[-1:] == c.least_common(1)