使用heapify。
您必須記住的一件重要事情是理論復(fù)雜性和性能是兩個(gè)不同的東西（即使它們是相關(guān)的）。換句話說(shuō)，實(shí)施也很重要。漸近復(fù)雜性為您提供了一些下限，您可以將其視為保證，例如 O(n) 中的算法確保在最壞的情況下，您將執(zhí)行許多輸入大小線性的指令。這里有兩件重要的事情：
常量被忽略，但常量在現(xiàn)實(shí)生活中很重要；
最壞的情況取決于您考慮的算法，而不僅僅是輸入。
根據(jù)您考慮的主題/問(wèn)題，第一點(diǎn)可能非常重要。在某些域中，隱藏在漸近復(fù)雜性中的常量非常大，以至于您甚至無(wú)法構(gòu)建大于常量的輸入（或者考慮該輸入是不現(xiàn)實(shí)的）。情況并非如此，但這是您始終必須牢記的事情。
給出這兩個(gè)觀察結(jié)果，你真的不能說(shuō)：實(shí)現(xiàn) B 比 A 快，因?yàn)?A 派生自 O(n) 算法而 B 派生自 O(log n) 算法。即使這是一個(gè)很好的論據(jù)，但它并不總是足夠的。當(dāng)所有輸入發(fā)生的可能性相同時(shí)，理論復(fù)雜性特別適合比較算法。換句話說(shuō)，當(dāng)你的算法非常通用時(shí)。
如果您知道您的用例和輸入是什么，您可以直接測(cè)試性能。使用測(cè)試和漸近復(fù)雜度將使您對(duì)算法的執(zhí)行方式有一個(gè)很好的了解（在極端情況下和任意實(shí)際情況下）。
話雖如此，讓我們對(duì)以下將實(shí)施三種不同策略的類(lèi)運(yùn)行一些性能測(cè)試（這里實(shí)際上有四種策略，但Invalidate 和 Reinsert在您的情況下似乎不正確，因?yàn)槟鷷?huì)使每個(gè)項(xiàng)目無(wú)效的次數(shù)與你看到一個(gè)給定的詞）。我將包括我的大部分代碼，以便您可以仔細(xì)檢查我沒(méi)有搞砸（您甚至可以檢查完整的筆記本）：
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)
然后我們可以使用以下函數(shù)運(yùn)行一些性能測(cè)試：
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))
結(jié)果如下：
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",
)
從這些測(cè)試中我們可以看到，這heapify似乎是最合理的選擇，它在最壞的情況下具有相當(dāng)?shù)膹?fù)雜性：O(n) 并且在實(shí)踐中表現(xiàn)更好。另一方面，調(diào)查其他選項(xiàng)可能是個(gè)好主意（例如擁有專(zhuān)用于該特定問(wèn)題的數(shù)據(jù)結(jié)構(gòu)，例如使用垃圾箱將單詞放入其中，然后將它們從垃圾箱移動(dòng)到下一個(gè)看起來(lái)像可能的軌道調(diào)查）。
重要說(shuō)明：這種情況（更新與讀取比率為 1:1）對(duì)heapify和sort解決方案都不利。所以，如果你管理有AK：1分的比例，這一結(jié)論將更加清晰（你可以替換nb_updates = 1與nb_updates = k上面的代碼）。
數(shù)據(jù)框詳細(xì)信息：
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
