基于valu的字典topk键的高效跟踪

Question

当字典的键更新时，如何有效地跟踪最大值字典的前k个键？在

我尝试过在每次更新后从字典中创建一个排序列表的天真方法（如Getting key with maximum value in dictionary?中所述），但是这非常昂贵，不能伸缩。在

真实世界示例：

计算来自无限数据流的词频。在任何给定的时刻，程序都可能被要求报告一个单词是否在当前最常出现的前k个值中。我们如何有效地实现这一目标？在

在集合。计数器速度太慢

>>> from itertools import permutations
>>> from collections import Counter
>>> from timeit import timeit
>>> c = Counter()
>>> for x in permutations(xrange(10), 10):
    c[x] += 1


>>> timeit('c.most_common(1)', 'from __main__ import c', number=1)
0.7442058258093311
>>> sum(c.values())
3628800

计算这个值需要将近一秒钟！在

我在寻找most_common()函数的O（1）时间。这应该可以通过另一个只在内部存储当前top-k项并跟踪当前最小值的数据结构来实现。在

Answer 1

我们可以实现一个跟踪top-k值的类，因为我不相信标准库有这个内置的。这将与主dictionary对象（可能是Counter）并行地保持最新的。您也可以将其用作主字典对象的子类的属性。在

实施

class MostCommon(object):
    """Keep track the top-k key-value pairs.

    Attributes:
        top: Integer representing the top-k items to keep track of.
        store: Dictionary of the top-k items.
        min: The current minimum of any top-k item.
        min_set: Set where keys are counts, and values are the set of
            keys with that count.
    """
    def __init__(self, top):
        """Create a new MostCommon object to track key-value paris.

        Args:
            top: Integer representing the top-k values to keep track of.
        """
        self.top = top
        self.store = dict()
        self.min = None
        self.min_set = defaultdict(set)

    def _update_existing(self, key, value):
        """Update an item that is already one of the top-k values."""
        # Currently handle values that are non-decreasing.
        assert value > self.store[key]
        self.min_set[self.store[key]].remove(key)
        if self.store[key] == self.min:  # Previously was the minimum.
            if not self.min_set[self.store[key]]:  # No more minimums.
                del self.min_set[self.store[key]]
                self.min_set[value].add(key)
                self.min = min(self.min_set.keys())
        self.min_set[value].add(key)
        self.store[key] = value

    def __contains__(self, key):
        """Boolean if the key is one of the top-k items."""
        return key in self.store

    def __setitem__(self, key, value):
        """Assign a value to a key.

        The item won't be stored if it is less than the minimum (and
        the store is already full). If the item is already in the store,
        the value will be updated along with the `min` if necessary.
        """
        # Store it if we aren't full yet.
        if len(self.store) < self.top:
            if key in self.store:  # We already have this item.
                self._update_existing(key, value)
            else:  # Brand new item.
                self.store[key] = value
                self.min_set[value].add(key)
                if value < self.min or self.min is None:
                    self.min = value
        else:  # We're full. The value must be greater minimum to be added.
            if value > self.min:  # New item must be larger than current min.
                if key in self.store:  # We already have this item.
                    self._update_existing(key, value)
                else:  # Brand new item.
                    # Make room by removing one of the current minimums.
                    old = self.min_set[self.min].pop()
                    del self.store[old]
                    # Delete the set if there are no old minimums left.
                    if not self.min_set[self.min]:
                        del self.min_set[self.min]
                    # Add the new item.
                    self.min_set[value].add(key)
                    self.store[key] = value
                    self.min = min(self.min_set.keys())

    def __repr__(self):
        if len(self.store) < 10:
            store = repr(self.store)
        else:
            length = len(self.store)
            largest = max(self.store.itervalues())
            store = '<len={length}, max={largest}>'.format(length=length,
                                                           largest=largest)
        return ('{self.__class__.__name__}(top={self.top}, min={self.min}, '
                'store={store})'.format(self=self, store=store))

示例用法

^{pr2}$

更新值后的访问确实是O（1）

>>> counter = Counter()
>>> for x in permutations(xrange(10), 10):
        counter[x] += 1

>>> common = MostCommon(1)
>>> for key, value in counter.iteritems():
    common[key] = value

>>> common
MostCommon(top=1, min=1, store={(9, 7, 8, 0, 2, 6, 5, 4, 3, 1): 1})
>>> timeit('repr(common)', 'from __main__ import common', number=1)
1.3251570635475218e-05

Access是O（1），但是当在一个O（n）操作的set item调用期间最小值发生变化时，其中n是顶部值的数目。这仍然比Counter好，在每次访问过程中，n是整个词汇表的大小！在

Answer 2

collections.Counter.most_commondoes a pass over all the values, finding the N-th largest one by putting them in a heap as it goes（我认为，在O（M logn）时间中，M是字典元素的总数）。在

正如Wei Yen在评论中所建议的那样，heapq可能工作正常：与字典并行，维护N个最大值的heapq，当您修改dict时，检查该值是否在那里或者现在应该在那里。问题是，正如您所注意到的，接口实际上没有任何方法来修改已经存在的元素的“优先级”（在您的例子中，是[负数，因为这是最小堆数]计数）。在

您可以在适当的地方修改相关项，然后运行heapq.heapify来恢复heapiness。这需要一个堆大小（N）的线性传递来查找相关的项（除非您要做额外的簿记以将元素与位置关联起来；可能不值得），然后再进行一次线性传递以重新修复。如果某个元素不在列表中，而现在在列表中，则需要通过替换最小的元素（在线性时间内，除非有其他结构），将其添加到堆中。在

不过，heapq私有接口包含一个函数^{}，该函数有以下注释：

# 'heap' is a heap at all indices >= startpos, except possibly for pos.  pos
# is the index of a leaf with a possibly out-of-order value.  Restore the
# heap invariant.

听起来不错！调用heapq._siftdown(heap, 0, pos_of_relevant_idx)将在logn时间内修复堆。当然，你必须先找到你正在递增的索引的位置，这需要线性时间。您可能需要维护一个元素到索引的字典来避免这种情况（同时保持指向最小元素位置的指针），但是您要么必须复制出_siftdown的源代码，然后修改它以在字典交换内容时更新字典，或者执行一个线性时间传递来重建字典（但是您只是试图避免线性传递…）。在

小心点，这应该算到O（logn）时间了。不过，事实证明，有一种叫做Fibonacci heap的东西确实支持你所需要的所有操作，在（摊余）常量的时间内。不幸的是，这是其中一种情况，big-O不是全部；Fibonacci堆的复杂性意味着在实践中，除了非常大的堆之外，它们实际上并不比二进制堆快。另外，（也许“因此”），在快速Google中没有一个标准的Python实现，虽然Boost C++库确实包含了一个。在

我首先尝试使用heapq，对要更改的元素进行线性搜索，然后调用_siftdown；这是O（N）时间，与Counter方法的O（mlogn）相比。如果结果太慢，您可以维护额外的索引字典，并创建自己的版本_siftdown，更新dict，该版本应该结束于O（logn）时间。如果仍然太慢（我对此表示怀疑），您可以寻找一个Python包装器来Boost的Fibonacci堆（或另一个实现），但我真的怀疑这是否值得麻烦。在

Answer 3

使用collections.Counter它已经在这个真实世界的例子中这样做了。你还有其他的用例吗？在