heapq —ヒープキューアルゴリズム
ソースコード： ：source： `Lib / heapq.py`
このモジュールは、優先キューアルゴリズムとも呼ばれるヒープキューアルゴリズムの実装を提供します。
ヒープは、すべての親ノードの値がその子のいずれか以下である二分木です。 この実装では、すべての k に対してheap[k] <= heap[2*k+1]およびheap[k] <= heap[2*k+2]の配列を使用し、要素をゼロから数えます。 比較のために、存在しない要素は無限であると見なされます。 ヒープの興味深い特性は、その最小要素が常にルートheap[0]であるということです。
以下のAPIは、2つの点で教科書ヒープアルゴリズムとは異なります。（a）ゼロベースのインデックスを使用します。 これにより、ノードのインデックスとその子のインデックスの関係が少しわかりにくくなりますが、Pythonはゼロベースのインデックスを使用するため、より適切です。 （b）popメソッドは、最大ではなく最小のアイテムを返します（教科書では「最小ヒープ」と呼ばれます。「最大ヒープ」は、インプレースソートに適しているため、テキストではより一般的です）。
これらの2つにより、ヒープを通常のPythonリストとして驚くことなく表示できます。heap[0]は最小のアイテムであり、heap.sort()はヒープを不変に維持します。
ヒープを作成するには、[]に初期化されたリストを使用するか、関数 heapify（）を使用して入力済みリストをヒープに変換できます。
以下の機能が提供されています。
- heapq.heappush(heap, item)
- ヒープを不変に保ちながら、値 item を heap にプッシュします。
- heapq.heappop(heap)
- ヒープから最小のアイテムをポップして返し、ヒープを不変に保ちます。 ヒープが空の場合、 IndexError が発生します。 ポップせずに最小のアイテムにアクセスするには、
heap[0]を使用します。
- heapq.heappushpop(heap, item)
- ヒープ上の item を押してから、 heap から最小のアイテムをポップして返します。 組み合わされたアクションは、 heappush（）の後に heappop（）を個別に呼び出すよりも効率的に実行されます。
- heapq.heapify(x)
- リスト x を、線形時間でインプレースのヒープに変換します。
- heapq.heapreplace(heap, item)
ヒープから最小のアイテムをポップして返し、新しいアイテムもプッシュします。 ヒープサイズは変わりません。 ヒープが空の場合、 IndexError が発生します。
このワンステップ操作は、 heappop（）の後に heappush（）が続くよりも効率的であり、固定サイズのヒープを使用する場合により適切です。 ポップ/プッシュの組み合わせは、常にヒープから要素を返し、それを item に置き換えます。
返される値は、追加された item よりも大きい場合があります。 それが望ましくない場合は、代わりに heappushpop（）の使用を検討してください。 そのプッシュ/ポップの組み合わせは、2つの値のうち小さい方を返し、ヒープに大きい方の値を残します。
このモジュールは、ヒープに基づく3つの汎用関数も提供します。
- heapq.merge(*iterables, key=None, reverse=False)
複数のソートされた入力を単一のソートされた出力にマージします（たとえば、複数のログファイルからのタイムスタンプ付きエントリをマージします）。 ソートされた値に対してイテレータを返します。
sorted(itertools.chain(*iterables))に似ていますが、反復可能を返し、データを一度にメモリにプルせず、各入力ストリームがすでにソートされている（最小から最大）と想定します。キーワード引数として指定する必要がある2つのオプションの引数があります。
key は、各入力要素から比較キーを抽出するために使用される1つの引数の key関数を指定します。 デフォルト値は
Noneです（要素を直接比較してください）。reverse はブール値です。
Trueに設定すると、入力要素は、各比較が逆にされたかのようにマージされます。sorted(itertools.chain(*iterables), reverse=True)と同様の動作を実現するには、すべての反復可能オブジェクトを最大から最小にソートする必要があります。バージョン3.5で変更：オプションのキーおよびリバースパラメーターが追加されました。
- heapq.nlargest(n, iterable, key=None)
- iterable で定義されたデータセットから n の最大要素を含むリストを返します。 key は、指定されている場合、 iterable の各要素から比較キーを抽出するために使用される1つの引数の関数を指定します（たとえば、
key=str.lower）。sorted(iterable, key=key, reverse=True)[:n]と同等です。
- heapq.nsmallest(n, iterable, key=None)
- iterable で定義されたデータセットから n の最小要素を含むリストを返します。 key は、指定されている場合、 iterable の各要素から比較キーを抽出するために使用される1つの引数の関数を指定します（たとえば、
key=str.lower）。sorted(iterable, key=key)[:n]と同等です。
後者の2つの関数は、 n の値が小さい場合に最適に機能します。 値が大きい場合は、 sorted（）関数を使用する方が効率的です。 また、n==1の場合、組み込みの min（）および max（）関数を使用する方が効率的です。 これらの関数を繰り返し使用する必要がある場合は、iterableを実際のヒープに変換することを検討してください。
基本的な例
ヒープソートは、すべての値をヒープにプッシュしてから、最小値を一度に1つずつポップオフすることで実装できます。
>>> def heapsort(iterable):
... h = []
... for value in iterable:
... heappush(h, value)
... return [heappop(h) for i in range(len(h))]
...
>>> heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0])
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]これはsorted(iterable)に似ていますが、 sorted（）とは異なり、この実装は安定していません。
ヒープ要素はタプルにすることができます。 これは、追跡されるメインレコードと一緒に比較値（タスクの優先順位など）を割り当てるのに役立ちます。
>>> h = []
>>> heappush(h, (5, 'write code'))
>>> heappush(h, (7, 'release product'))
>>> heappush(h, (1, 'write spec'))
>>> heappush(h, (3, 'create tests'))
>>> heappop(h)
(1, 'write spec')プライオリティキューの実装に関する注意事項
優先キューはヒープの一般的な使用法であり、いくつかの実装上の課題があります。
- 並べ替えの安定性：優先度が等しい2つのタスクを、最初に追加された順序で返すにはどうすればよいですか？
- 優先度が等しく、タスクにデフォルトの比較順序がない場合、タプル比較は（priority、task）ペアに対して中断されます。
- タスクの優先度が変更された場合、ヒープ内の新しい位置にタスクをどのように移動しますか？
- または、保留中のタスクを削除する必要がある場合、どのようにしてそれを見つけてキューから削除しますか？
最初の2つの課題の解決策は、優先度、エントリ数、およびタスクを含む3要素リストとしてエントリを保存することです。 エントリ数はタイブレーカーとして機能するため、同じ優先度の2つのタスクが追加された順序で返されます。 また、2つのエントリ数が同じではないため、タプル比較で2つのタスクを直接比較しようとすることはありません。
比較できないタスクの問題に対する別の解決策は、タスクアイテムを無視し、優先度フィールドのみを比較するラッパークラスを作成することです。
from dataclasses import dataclass, field
from typing import Any
@dataclass(order=True)
class PrioritizedItem:
priority: int
item: Any=field(compare=False)残りの課題は、保留中のタスクを見つけてその優先度を変更するか、完全に削除することを中心に展開します。 タスクの検索は、キュー内のエントリを指す辞書を使用して実行できます。
エントリを削除したり、優先度を変更したりすると、ヒープ構造の不変条件が壊れるため、より困難になります。 したがって、考えられる解決策は、エントリを削除済みとしてマークし、変更された優先度で新しいエントリを追加することです。
pq = [] # list of entries arranged in a heap
entry_finder = {} # mapping of tasks to entries
REMOVED = '<removed-task>' # placeholder for a removed task
counter = itertools.count() # unique sequence count
def add_task(task, priority=0):
'Add a new task or update the priority of an existing task'
if task in entry_finder:
remove_task(task)
count = next(counter)
entry = [priority, count, task]
entry_finder[task] = entry
heappush(pq, entry)
def remove_task(task):
'Mark an existing task as REMOVED. Raise KeyError if not found.'
entry = entry_finder.pop(task)
entry[-1] = REMOVED
def pop_task():
'Remove and return the lowest priority task. Raise KeyError if empty.'
while pq:
priority, count, task = heappop(pq)
if task is not REMOVED:
del entry_finder[task]
return task
raise KeyError('pop from an empty priority queue')仮説
ヒープは、すべての k に対してa[k] <= a[2*k+1]およびa[k] <= a[2*k+2]の配列であり、0から要素を数えます。 比較のために、存在しない要素は無限であると見なされます。 ヒープの興味深い特性は、a[0]が常に最小の要素であるということです。
上記の奇妙な不変条件は、トーナメントの効率的なメモリ表現を意味します。 以下の番号は k であり、a[k]ではありません。
0
1 2
3 4 5 6
7 8 9 10 11 12 13 14
15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30上のツリーでは、各セル k が2*k+1と2*k+2を上回っています。 スポーツで見られる通常のバイナリトーナメントでは、各セルが上位の2つのセルの勝者であり、ツリーを下って勝者を追跡して、すべての対戦相手を確認できます。 ただし、このようなトーナメントの多くのコンピューターアプリケーションでは、勝者の履歴を追跡する必要はありません。 メモリ効率を高めるために、勝者が昇格すると、それを下位レベルの別のセルに置き換えようとします。ルールでは、セルとその上位の2つのセルには、3つの異なるアイテムが含まれますが、上位のセルは「勝ち」ます。 2つのトッピングされたセルの上。
このヒープ不変条件が常に保護されている場合、インデックス0が明らかに全体的な勝者です。 それを削除して「次の」勝者を見つける最も簡単なアルゴリズムの方法は、敗者（上の図のセル30など）を0の位置に移動し、この新しい0をツリーの下に浸透させ、不変になるまで値を交換することです。再確立されます。 これは明らかに、ツリー内のアイテムの総数の対数です。 すべてのアイテムを反復処理することにより、O（n log n）ソートを取得します。
このソートの優れた機能は、挿入されたアイテムが最後に抽出した0番目の要素よりも「優れている」場合を除き、ソートの実行中に新しいアイテムを効率的に挿入できることです。 これは、ツリーがすべての着信イベントを保持し、「win」条件が最小のスケジュールされた時間を意味するシミュレーションコンテキストで特に役立ちます。 イベントが他のイベントの実行をスケジュールする場合、それらは将来にスケジュールされるため、ヒープに簡単に入ることができます。 したがって、ヒープはスケジューラーを実装するための優れた構造です（これは、MIDIシーケンサーに使用したものです:-)。
スケジューラーを実装するためのさまざまな構造が広く研究されており、ヒープは適度に高速で、速度はほぼ一定であり、最悪の場合は平均的な場合とそれほど変わらないため、これに適しています。 ただし、全体的に効率的な表現は他にもありますが、最悪の場合はひどい場合があります。
ヒープは、大きなディスクの種類でも非常に役立ちます。 おそらく、大きな並べ替えは「実行」（事前に並べ替えられたシーケンスであり、サイズは通常CPUメモリの量に関連します）を生成し、その後にこれらの実行のマージパスが続くことを意味することをご存知でしょう。マージは非常に巧妙であることがよくあります。整理された 1 。 最初のソートで可能な限り長い実行が生成されることが非常に重要です。 トーナメントはそれを達成するための良い方法です。 トーナメントを開催するために利用可能なすべてのメモリを使用して、現在のランに合うアイテムを置き換えて浸透させると、ランダム入力のメモリの2倍のサイズのランが生成され、あいまいに順序付けられた入力にはるかに適しています。
さらに、ディスクに0番目のアイテムを出力し、現在のトーナメントに収まらない可能性のある入力を取得した場合（値が最後の出力値に「勝つ」ため）、ヒープに収まらないため、サイズはヒープが減少します。 解放されたメモリは、最初のヒープが溶けるのとまったく同じ速度で成長する2番目のヒープを段階的に構築するために、すぐに巧妙に再利用できます。 最初のヒープが完全に消えたら、ヒープを切り替えて新しい実行を開始します。 賢くて非常に効果的です！
一言で言えば、ヒープは知っておくと便利なメモリ構造です。 私はいくつかのアプリケーションでそれらを使用していますが、「ヒープ」モジュールを維持するのは良いことだと思います。 :-)
脚注
- 1
- 現在のディスクバランシングアルゴリズムは、巧妙というよりも煩わしいものであり、これはディスクのシーク機能の結果です。 大きなテープドライブのようにシークできないデバイスでは、話はまったく異なり、各テープの動きが可能な限り最も効果的である（つまり、「マージの進行中」）。 一部のテープは逆方向に読み取ることもでき、これは巻き戻し時間を回避するためにも使用されました。 私を信じてください、本当に良いテープの種類は見るのがとても素晴らしかったです！ 常に、並べ替えは素晴らしい芸術でした！ :-)
