python - 如何避免在 heapq 中使用 _siftup 或 _siftdown

Question

我不知道如何在不使用 _siftup 或 _siftdown 的情况下有效解决以下问题:

当一个元素乱序时，如何恢复堆不变量？

换句话说，将heap中的old_value更新为new_value，并保持heap工作。您可以假设堆中只有一个 old_value。函数定义如下:

def update_value_in_heap(heap, old_value, new_value):

这是我的真实场景，有兴趣的可以看看。

• 您可以想象它是一个小型自动完成系统。我需要数数单词的频率，并维护前k个最大计数单词，其中随时准备输出。所以我在这里使用堆。当一个字count++，如果它在堆中，我需要更新它。

• 所有单词和计数都存储在 trie 树的叶子和堆中
  存储在trie树的中间节点中。如果你关心这个词
  堆外，不用担心，我可以从 trie-tree 的叶子节点获取它。

• 当用户输入一个单词时，它会首先从堆中读取，然后更新
  它。为了获得更好的性能，我们可以考虑降低更新频率通过批量更新。

那么当某个特定字数增加时如何更新堆呢？

这是 _siftup 或 _siftdown 版本的简单示例(不是我的场景):

>>> from heapq import _siftup, _siftdown, heapify, heappop

>>> data = [10, 5, 18, 2, 37, 3, 8, 7, 19, 1]
>>> heapify(data)
>>> old, new = 8, 22              # increase the 8 to 22
>>> i = data.index(old)
>>> data[i] = new
>>> _siftup(data, i)
>>> [heappop(data) for i in range(len(data))]
[1, 2, 3, 5, 7, 10, 18, 19, 22, 37]

>>> data = [10, 5, 18, 2, 37, 3, 8, 7, 19, 1]
>>> heapify(data)
>>> old, new = 8, 4              # decrease the 8 to 4
>>> i = data.index(old)
>>> data[i] = new
>>> _siftdown(data, 0, i)
>>> [heappop(data) for i in range(len(data))]
[1, 2, 3, 4, 5, 7, 10, 18, 19, 37]

索引的成本为 O(n)，更新的成本为 O(logn)。 heapify 是另一种解决方案，但是效率低于 _siftup 或 _siftdown。

但是_siftup和_siftdown是heapq中的 protected 成员，因此不建议从外部访问。

那么有没有更好更高效的方法来解决这个问题呢？这种情况的最佳实践？

感谢您的阅读，我非常感谢它对我的帮助。 :)

已引用heapq python - how to modify values for which heap is sorted ，但没有回答我的问题

Answer 1

@cglacet 的答案是完全错误的，但看起来非常合法。他提供的代码片段完全被破坏了!它也很难阅读。_siftup() 在 heapify() 中被调用 n//2 次，因此它不可能比 _siftup() 本身更快。

要回答原来的问题，没有更好的办法了。如果您担心方法是私有(private)的，请创建自己的方法来执行相同的操作。

我唯一同意的是，如果你不需要长时间从堆中读取数据，那么惰性heapify()可能会有好处 当您需要它们时就可以使用它们。问题是您是否应该为此使用堆。

让我们回顾一下他的代码片段的问题:

heapify() 函数在“更新”运行中被多次调用。导致此问题的错误链如下:

• 他传递了 heap_fix，但期望 heap，对于 sort 也是如此
• 如果 self.sort 始终为 False，则 self.heap 始终为 True
• 他重新定义了__getitem__()和__setitem__()，每次_siftup()或_siftdown()时都会调用它们 code> 分配或读取某些内容(注意:这两个函数在 C 中未调用，因此它们使用 __getitem__() 和 __setitem__())
• 如果 self.heap 为 True 并且正在调用 __getitem__() 和 __setitem__()，则每次 _siftup() 或 siftdown() 交换元素时都会调用 _repair() 函数。但是对 heapify() 的调用是在 C 中完成的，因此 __getitem__() 不会被调用，并且不会陷入无限循环
• 他重新定义了 self.sort，因此像他尝试做的那样调用它会失败
• 他读了一次，但更新了一个项目 nb_updates 次，而不是他声称的 1:1

我修复了这个例子，我尽力验证它，但我们都会犯错误。请自行检查。

代码

import time
import random

from heapq import _siftup, _siftdown, heapify, heappop

class UpdateHeap(list):
    def __init__(self, values):
        super().__init__(values)
        heapify(self)

    def update(self, index, value):
        old, self[index] = self[index], value
        if value > old:
            _siftup(self, index)
        else:
            _siftdown(self, 0, index)

    def pop(self):
        return heappop(self)

class SlowHeap(list):
    def __init__(self, values):
        super().__init__(values)
        heapify(self)
        self._broken = False
        
    # Solution 2 and 3) repair using sort/heapify in a lazy way:
    def update(self, index, value):
        super().__setitem__(index, value)
        self._broken = True
    
    def __getitem__(self, index):
        if self._broken:
            self._repair()
            self._broken = False
        return super().__getitem__(index)

    def _repair(self):
        ...

    def pop(self):
        if self._broken:
            self._repair()
        return heappop(self)

class HeapifyHeap(SlowHeap):

    def _repair(self):
        heapify(self)


class SortHeap(SlowHeap):

    def _repair(self):
        self.sort()

def rand_update(heap):
    index = random.randint(0, len(heap)-1)
    new_value = random.randint(max_int+1, max_int*2)
    heap.update(index, new_value)
    
def rand_updates(update_count, heap):
    for i in range(update_count):
        rand_update(heap)
        heap[0]
        
def verify(heap):
    last = None
    while heap:
        item = heap.pop()
        if last is not None and item < last:
            raise RuntimeError(f"{item} was smaller than last {last}")
        last = item

def run_perf_test(update_count, data, heap_class):
    test_heap = heap_class(data)
    t0 = time.time()
    rand_updates(update_count, test_heap)
    perf = (time.time() - t0)*1e3
    verify(test_heap)
    return perf


results = []
max_int = 500
update_count = 100

for i in range(2, 7):
    test_size = 10**i
    test_data = [random.randint(0, max_int) for _ in range(test_size)]

    perf = run_perf_test(update_count, test_data, UpdateHeap)
    results.append((test_size, "update", perf))
    
    perf = run_perf_test(update_count, test_data, HeapifyHeap)
    results.append((test_size, "heapify", perf))

    perf = run_perf_test(update_count, test_data, SortHeap)
    results.append((test_size, "sort", perf))

import pandas as pd
import seaborn as sns

dtf = pd.DataFrame(results, columns=["heap size", "method", "duration (ms)"])
print(dtf)

sns.lineplot(
    data=dtf, 
    x="heap size", 
    y="duration (ms)", 
    hue="method",
)

结果

如您所见，使用 _siftdown() 和 _siftup() 的“更新”方法渐近更快。

您应该知道您的代码的作用以及运行需要多长时间。如果有疑问，您应该检查一下。 @cglaced 检查了执行需要多长时间，但他没有询问应该需要多长时间。如果他这样做了，他会发现两者不匹配。其他人也上当了。

    heap size   method  duration (ms)
0         100   update       0.219107
1         100  heapify       0.412703
2         100     sort       0.242710
3        1000   update       0.198841
4        1000  heapify       2.947330
5        1000     sort       0.605345
6       10000   update       0.203848
7       10000  heapify      32.759190
8       10000     sort       4.621506
9      100000   update       0.348568
10     100000  heapify     327.646971
11     100000     sort      49.481153
12    1000000   update       0.256062
13    1000000  heapify    3475.244761
14    1000000     sort    1106.570005