使用heapify
。
您必须牢记的重要一件事是,理论复杂性和性能是两个不同的事物(即使它们是相关的)。换句话说,实现也很重要。渐近复杂度为您提供了一些 下限 ,您可以将其视为保证,例如O(n)中的算法可确保在最坏的情况下,您将执行许多与输入大小成线性关系的指令。这里有两件重要的事情:
根据要考虑的主题/问题,第一点可能非常重要。在某些域中,隐藏在渐近复杂性中的常量是如此之大,以至于您甚至无法建立比常量大的输入(或者认为输入不现实)。这里不是这种情况,但是您始终必须记住这一点。
给出这两个结论,您不能真正说出: 实现B比A快,因为A源自O(n)算法,而B源自O(log n)算法 。即使从总体上来说这是一个很好的论据,但它并不总是足够的。当所有输入均等可能发生时,理论上的复杂性对于比较算法特别有用。换句话说,您的算法非常通用。
如果您知道用例和输入将是什么,则可以直接测试性能。同时使用测试和渐进复杂度,可以使您很好地了解算法的性能(在极端情况和任意实际情况下)。
话虽如此,让我们在下面的类上运行一些性能测试,这些测试将实现三种不同的策略(这里实际上有四种策略,但是Invalidate and Reinsert 在您的情况下似乎 不合适, 因为您将使每一项无效的时间为您会看到一个给定的单词)。我将包括我的大部分代码,以便您可以仔细检查我是否搞砸了(甚至可以检查完整的笔记本):
from heapq import _siftup, _siftdown, heapify, heappop
class Heap(list):
def __init__(self, values, sort=False, heap=False):
super().__init__(values)
heapify(self)
self._broken = False
self.sort = sort
self.heap = heap or not sort
# Solution 1) repair using the kNowledge we have after every update:
def update(self, key, value):
old, self[key] = self[key], value
if value > old:
_siftup(self, key)
else:
_siftdown(self, 0, key)
# Solution 2 and 3) repair using sort/heapify in a lazzy way:
def __setitem__(self, key, value):
super().__setitem__(key, value)
self._broken = True
def __getitem__(self, key):
if self._broken:
self._repair()
self._broken = False
return super().__getitem__(key)
def _repair(self):
if self.sort:
self.sort()
elif self.heap:
heapify(self)
# … you'll also need to delegate all other heap functions, for example:
def pop(self):
self._repair()
return heappop(self)
我们首先可以检查所有三种方法是否都有效:
data = [10, 5, 18, 2, 37, 3, 8, 7, 19, 1]
heap = Heap(data[:])
heap.update(8, 22)
heap.update(7, 4)
print(heap)
heap = Heap(data[:], sort_fix=True)
heap[8] = 22
heap[7] = 4
print(heap)
heap = Heap(data[:], heap_fix=True)
heap[8] = 22
heap[7] = 4
print(heap)
import time
import random
def rand_update(heap, lazzy_fix=False, **kwargs):
index = random.randint(0, len(heap)-1)
new_value = random.randint(max_int+1, max_int*2)
if lazzy_fix:
heap[index] = new_value
else:
heap.update(index, new_value)
def rand_updates(n, heap, lazzy_fix=False, **kwargs):
for _ in range(n):
rand_update(heap, lazzy_fix)
def run_perf_test(n, data, **kwargs):
test_heap = Heap(data[:], **kwargs)
t0 = time.time()
rand_updates(n, test_heap, **kwargs)
test_heap[0]
return (time.time() - t0)*1e3
results = []
max_int = 500
nb_updates = 1
for i in range(3, 7):
test_size = 10**i
test_data = [random.randint(0, max_int) for _ in range(test_size)]
perf = run_perf_test(nb_updates, test_data)
results.append((test_size, "update", perf))
perf = run_perf_test(nb_updates, test_data, lazzy_fix=True, heap_fix=True)
results.append((test_size, "heapify", perf))
perf = run_perf_test(nb_updates, test_data, lazzy_fix=True, sort_fix=True)
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",
)
从这些测试中我们可以看出,这heapify
似乎是最合理的选择,但在最坏的情况下它具有相当好的复杂度:O(n),并且在实践中表现更好。另一方面,研究其他选择(例如具有专用于该特定问题的数据结构,例如,使用bin将单词放入其中,然后将它们从bin移至下一个看起来像是一条可能的轨道),可能是个好主意。调查)。
重要说明:这种情况(更新与阅读比例为1:1)对heapify
和sort
解决方案均不利。所以,如果你管理有AK:1分的比例,这一结论将更加清晰(你可以替换nb_updates = 1
与nb_updates = k
上面的代码)。
数据框详细信息:
heap size method duration in ms
0 1000 update 0.435114
1 1000 heapify 0.073195
2 1000 sort 0.101089
3 10000 update 1.668930
4 10000 heapify 0.480175
5 10000 sort 1.151085
6 100000 update 13.194084
7 100000 heapify 4.875898
8 100000 sort 11.922121
9 1000000 update 153.587103
10 1000000 heapify 51.237106
11 1000000 sort 145.306110