时间戳

首页 > 解决方案 > 如何避免在 heapq 中使用 _siftup 或 _siftdown

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

问题描述

我不知道如何在不使用_siftupor的情况下有效地解决以下问题_siftdown：

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

换句话说，更新old_value到heap，new_value并继续heap工作。您可以假设堆中只有一个old_value。函数定义如下：

def update_value_in_heap(heap, old_value, new_value):

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

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

这是 _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是另一种解决方案，但效率低于_siftupor _siftdown。

但是_siftupand_siftdown是 heapq 中的受保护成员，因此不建议从外部访问它们。

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

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

已经参考heapq python - 如何修改堆排序的值，但没有回答我的问题

标签： pythonheap

解决方案

@cglacet 的答案是完全错误的，但看起来非常合法。他提供的代码片段完全被破坏了！它也很难阅读。 _siftup()被调用 n//2 次，heapify()所以它不能比_siftup()自己快。

要回答原始问题，没有更好的方法。如果您担心方法是私有的，请创建自己的方法来做同样的事情。

我唯一同意的是，如果您不需要长时间从堆中读取，那么在需要它们时将其懒惰可能是有益的。heapify()问题是您是否应该为此使用堆。

让我们来看看他的片段的问题：

该heapify()函数被多次调用以进行“更新”运行。导致这种情况的错误链如下：

  • 他通过了heap_fix，但是期待heap，对于sort
  • 如果self.sort总是False，self.heap则总是True
  • 他重新定义了__getitem__()and__setitem__()每次分配或读取某些东西时都会调用_siftup()它们_siftdown()（注意：这两个在 C 中没有调用，所以它们使用__getitem__()and __setitem__()）
  • 如果self.heapis Trueand are 被调用，则每次调用该__getitem__()函数或交换元素。但是调用是在 C 中完成的，所以不会被调用，也不会进入无限循环__setitem__()_repair()_siftup()siftdown()heapify()__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

在此处输入图像描述

推荐阅读