バケットキュー

バケットキュー
1 ～ 6 の範囲の優先度に適したバケットの配列。最小優先度の要素は、一番左の空でないバケットにあります。
タイプ	優先キュー
発明された	1969
発明者	ロバート・ダイアル
ビッグ O 記法による時間計算量 手術 平均 最悪の場合 入れる お(1) お(1) 最小値を検索 O (#優先順位) O (#優先順位) 削除最小値 O (#優先順位) O (#優先順位) 減少キー お(1) お(1) 空間の複雑さ

バケットキューは、優先度キュー抽象データ型を実装するデータ構造です。数値優先度を持つ要素の動的なコレクションを維持し、最小（または最大）優先度の要素にすばやくアクセスできます。バケットキューでは、優先度は整数である必要があり、優先度の範囲が狭いアプリケーションに特に適しています。^[1]バケットキューは、バケットの配列の形式を持ちます。つまり、優先度でインデックス付けされた配列データ構造で、セルには互いに同じ優先度を持つアイテムのコレクションが含まれます。このデータ構造では、要素の挿入と優先度の変更に一定の時間がかかります。最小優先度の要素を検索して削除するには、バケットの数に比例した時間がかかります。または、最後に見つかったバケットへのポインタを維持することにより、連続する操作間の優先度の差に比例した時間がかかります。

バケットキューは、ピジョンホールソート（バケットソートとも呼ばれる）の優先度キュー版です。ピジョンホールソートは、要素を優先度でインデックス付けされたバケットに配置し、バケットを連結するソートアルゴリズムです。選択ソートでバケットキューを優先度キューとして使用すると、ピジョンホールソートアルゴリズムの一種になります。^[2]バケットキューは、バケット優先度キュー^[3]または制限高さ優先度キューとも呼ばれます。^[1]実数優先度の量子化近似に使用する場合、乱雑優先度キュー^[4]または疑似優先度キューとも呼ばれます。^[5]これらは、実数による正確な優先順位付けのために同様のバケット配列を使用する構造である カレンダーキューと密接に関連しています。

バケットキューの応用としては、グラフの縮退の計算、重みが小さな整数またはすでにソートされているグラフの最短経路と最長経路の高速アルゴリズム、集合被覆問題に対する貪欲近似アルゴリズムなどがあります。この構造の量子化バージョンは、スケジューリング^[2]やコンピュータグラフィックスにおけるマーチングキューブ^[4]にも適用されています。バケットキュー^[6]が最初に使用されたのは、Dial (1969) による最短経路アルゴリズムでした。^[7]

バケットキューは、0または1から既知の上限Cまでの範囲の整数優先度を持つ要素と、要素の挿入、要素の優先度の変更、または最小（または最大）優先度を持つ要素の抽出（検索と削除）の操作を処理できます。バケットキューは、コンテナデータ構造の配列Aで構成されます。ほとんどのソースでは、これらのコンテナは二重リンクリストですが、動的配列^[3]または動的セットの場合もあります。p番目の配列セルA [ p ]のコンテナには、優先度がpである要素のコレクションが格納されます。

バケット キューは次の操作を処理できます。

• 優先度pの要素x を挿入するには、x をコンテナーA [ p ]に追加します。
• 要素の優先度を変更するには、古い優先度のコンテナから要素を削除し、新しい優先度のコンテナに再度挿入します。
• 最小または最大の優先度を持つ要素を抽出するには、配列内で順次検索を実行して、それぞれ最初または最後の空でないコンテナーを見つけ、このコンテナーから任意の要素を選択し、コンテナーから削除します。

このように、挿入と優先度の変更には一定の時間がかかり、最小または最大の優先度の要素の抽出にはO（C）の時間がかかります。^{[1] [6] [8]}

最適化として、データ構造は、空でないバケットの各シーケンシャル検索を、配列の先頭ではなく、最後に見つかった空でないバケットから開始することができます。これは、遅延 (これらのシーケンシャル検索を必要になるまで遅らせる) または積極的 (検索を事前に行う) の 2 つの異なる方法のいずれかで実行できます。検索をいつ行うかの選択は、これらの検索によってどのデータ構造操作が遅くなるかに影響します。Dial の元のバージョンの構造では、遅延検索が使用されていました。これは、現在キューにあるすべての要素の最小優先度の下限であるインデックスL を維持することで実現できます。新しい要素を挿入する場合、 L は古い値と新しい要素の優先度の最小値に更新する必要があります。最小優先度の要素を検索する場合、検索は0 ではなくLから開始でき、検索後にL は検索で見つかった優先度と同じままにする必要があります。^{[7] [9]}あるいは、この最適化の積極的バージョンでは、Lが常に最初の空でないバケットを指すように更新されます。Lより小さい優先度を持つ新しい要素を挿入する場合、データ構造はL を新しい優先度に設定し、優先度Lのバケットから最後の要素を削除する場合は、空でないバケットが見つかるまで、より大きなインデックスを順番に検索し、結果のバケットの優先度をLに設定します。 ^[1]

これら 2 つのバリエーションのいずれでも、各シーケンシャル検索には、 Lの古い値と新しい値の差に比例した時間がかかります。これは、データ構造の最適化されていないバージョンでの検索のO ( C )時間制限よりも大幅に高速になる可能性があります。ダイクストラのアルゴリズムなどの優先キューの多くのアプリケーションでは、最小の優先度が単調なシーケンスを形成するため、単調な優先キューを使用できます。これらのアプリケーションでは、最適化された構造の遅延および早期の両方のバリエーションについて、空でないバケットのシーケンシャル検索は、バケットの互いに重ならない範囲をカバーします。各バケットはこれらの範囲の 1 つにしか含まれないため、それらのステップ数は最大でCになります。したがって、これらのアプリケーションでは、 n操作のシーケンスの合計時間は、この最適化を行わない場合のより遅いO ( nC )時間制限ではなく、 O ( n + C )になります。^[9]バケットキューを使用して最大優先度の要素を検索するアプリケーションでは、同様の最適化を適用できますが、この場合は最大優先度の上限となるインデックスを維持し、空でないバケットの順次検索はこの上限から下方に進む必要があります。^[10]

別の最適化（Dial 1969 で既に提案）は、優先度が単調で、アルゴリズムの実行中、 0 からCまでの全範囲に及ぶのではなく、常にr値の範囲内に収まる場合に、スペースを節約するために使用できます。この場合、実際の値ではなく、優先度を法とするrで配列をインデックスできます。最小優先度要素の検索は、常に前の最小値から開始する必要があります。これにより、最小値よりも高いが法が低い優先度が回避されます。特に、このアイデアは、辺の長さが 1 からrまでの範囲の整数であるグラフのダイクストラのアルゴリズムに適用できます。^[8]

新しいバケット キューを作成するには、空のバケットの配列を初期化する必要があるため、この初期化手順には優先度の数に比例した時間がかかります。1981年にDonald B. Johnsonが説明したバケット キューのバリエーションでは、空でないバケットのみを優先度順に並べたリンク リストに格納し、補助検索ツリーを使用して、このリンク リスト内の新しいバケットの位置をすばやく見つけます。このバリアント構造を初期化するには時間O (log log C )、最小または最大の優先度を持つ要素を見つけるには定数時間、要素を挿入または削除するには時間O (log log D )かかります。ここで、D は、挿入または削除された要素の優先度に最も近い小さい優先度と大きい優先度の差です。^[11]

たとえば、0、1、2、3 の 4 つの優先順位を持つバケット キューを考えてみましょう。これは、4 つのセルにそれぞれ要素のコレクション (最初は空) が含まれる配列で構成されます。この例では、 は4 つのセットを括弧で囲んだシーケンスとして記述できます。同じ優先順位 1 を持つ 2 つの要素とを挿入し、優先順位 3 を持つ 3 番目の要素を挿入し、 の優先順位を 3 に変更し、次に優先順位が最小の要素を 2 回抽出するという一連の操作を考えてみましょう。 ${\displaystyle A}$${\displaystyle A}$${\displaystyle A=[\emptyset ,\emptyset ,\emptyset ,\emptyset ]}$${\displaystyle x}$${\displaystyle y}$${\displaystyle z}$${\displaystyle x}$

• 優先度1で挿入した後、 .${\displaystyle x}$${\displaystyle A=[\emptyset ,\{x\},\emptyset ,\emptyset ]}$
• 優先度1で挿入した後、 .${\displaystyle y}$${\displaystyle A=[\emptyset ,\{x,y\},\emptyset ,\emptyset ]}$
• 優先度3でzを挿入した後、.${\displaystyle A=[\emptyset ,\{x,y\},\emptyset ,\{z\}]}$
• x の優先度を 1 から 3 に変更するには、 から x を削除して に追加し、その後 を実行します。${\displaystyle A[1]}$${\displaystyle A[3]}$${\displaystyle A=[\emptyset ,\{y\},\emptyset ,\{x,z\}]}$
• バケット キューの基本バージョンで最低優先度の要素を抽出すると、 の先頭から最初の空でない要素が検索されます。は空ですが、空でないセット は空です。 このセットの任意の要素 (唯一の要素) が最低優先度の要素として選択されます。構造から を削除すると、 が残ります。${\displaystyle A}$${\displaystyle A[0]}$${\displaystyle A[1]=\{y\}}$${\displaystyle y}$${\displaystyle y}$${\displaystyle A=[\emptyset ,\emptyset ,\emptyset ,\{x,z\}]}$
• バケット キューの基本バージョンでは、2 番目の抽出操作で、配列の先頭から再度検索します: 、、、空ではありません。バケット キューの改良版では、この検索は代わりに空でないことがわかった最後の位置 から始まります。いずれの場合でも、は最初の空でないセットであることがわかります。その要素の 1 つが、最小優先度の要素として任意に選択されます。たとえば、が選択される場合があります。この要素は削除され、 が残ります。${\displaystyle A[0]=\emptyset }$${\displaystyle A[1]=\emptyset }$${\displaystyle A[2]=\emptyset }$${\displaystyle A[3]={}}$${\displaystyle A[1]}$${\displaystyle A[3]=\{x,z\}}$${\displaystyle z}$${\displaystyle A=[\emptyset ,\emptyset ,\emptyset ,\{x\}]}$

バケットキューは、無向グラフの頂点を次数で優先順位付けし、次数が最小の頂点を繰り返し見つけて削除するために使用できます。^[1]この貪欲アルゴリズムは、グラフの縮退度を計算するために使用できます。この縮退度は、削除時の任意の頂点の最大次数に等しくなります。このアルゴリズムは、最小優先順位の下限を維持する最適化の有無にかかわらず、線形時間かかります。これは、各頂点がその次数に比例した時間で見つかり、すべての頂点の次数の合計がグラフの辺の数に線形であるためです。^[12]

正の整数である辺の重みを持つ有向グラフの最短経路を求めるダイクストラのアルゴリズムでは、優先度は単調であり、 ^[13]単調なバケットキューを使用してO ( m + dc )の時間制限を取得できます。ここで、mは辺の数、dはネットワークの直径、cは最大 (整数) リンクコストです。^{[9] [14]}このダイクストラのアルゴリズムの変形は、 1969 年に発表した Robert B. Dial にちなんで、Dial のアルゴリズム^{[9]としても知られています。 [7]}同じアイデアは、最大重みと最小重みの比が最大でcである、正の実数辺重みを持つグラフに対して、量子化されたバケットキューを使用しても機能します。^[15]この量子化されたバージョンのアルゴリズムでは、^{[5]これらのアルゴリズムでは、優先順位は幅}c + 1の範囲にしか及ばないため、モジュラー最適化を使用してスペースをO（n + c）に削減できます。^{[8] [14]}

同じアルゴリズムの変形は、最広経路問題にも使用できます。非整数のエッジ重みを整数の優先順位を割り当てることができるサブセットに素早く分割する方法と組み合わせることで、最広経路問題の単一ソース単一宛先バージョンに対するほぼ線形時間のソリューションが得られます。^[16]

集合被覆問題は、入力として集合の族を持ちます。出力は、元の族と同じ和集合を持ち、できるだけ少ない集合を含むこれらの集合のサブ族である必要があります。これはNP 困難ですが、対数近似比を達成する貪欲近似アルゴリズムがあり、 P = NPでない限り、本質的に可能な限り最良です。^[17]この近似アルゴリズムは、残りの未被覆要素の最大数をカバーする集合を繰り返し選択することで、サブ族を選択します。^[18]アルゴリズム設計の標準的な演習では、このアルゴリズムを入力サイズ（すべての入力集合のサイズの合計）に線形時間で実装することが求められます。^[19]

これは、入力ファミリ内のセットのバケット キューを使用して解決できます。バケット キューは、カバーする残りの要素の数によって優先順位が付けられます。貪欲アルゴリズムが出力の一部としてセットを選択するたびに、新しくカバーされたセット要素は、それらをカバーする他のセットの優先順位から減算されます。アルゴリズムの過程で、これらの優先順位の変更の数は、入力セットのサイズの合計に相当します。優先順位は単調に減少する整数であり、上限はカバーされる要素の数です。貪欲アルゴリズムの各選択には、最大優先順位のセットの検索が含まれます。これは、バケット キューのバケットを下方向にスキャンすることで実行できます。これは、最新の最大値から開始します。合計時間は入力サイズに比例します。^[10]

バケットキューは、期限付きのタスクをスケジュールするために使用できます。たとえば、サービス品質が保証されたインターネットデータのパケット転送などです。このアプリケーションでは、期限は離散的な間隔に量子化される必要があり、期限が同じ間隔に該当するタスクは同等の優先度を持つと見なされます。^[2]

量子化バケット キュー データ構造のバリエーションであるカレンダー キューは、離散イベント シミュレーションのスケジュールに適用されています。このキューの要素は、シミュレーション内でイベントが発生する時間によって優先順位が付けられた将来のイベントです。このアプリケーションでは、イベントの順序が重要であるため、優先順位を概算することはできません。したがって、カレンダー キューは、バケット キューとは異なる方法で最小優先順位の要素を検索します。バケット キューでは、最初の空でないバケットの任意の要素が返される場合がありますが、カレンダー キューは、そのバケット内のすべての要素を検索して、量子化されていない優先順位が最も小さい要素を特定します。これらの検索を高速に保つために、このバリエーションは、量子化のスケールを調整し、バランスが崩れたときにデータ構造を再構築することで、バケットの数を要素の数に比例させようとします。カレンダー キューは、最悪の場合 (多くの要素がすべて同じ最小のバケットに入る場合) にはバケット キューよりも遅くなる可能性がありますが、要素がバケット間で均一に分散され、平均バケット サイズが一定である場合は高速になります。^{[20] [21]}

応用数学や微分方程式を解く数値計算法では、波動伝播をモデル化するために使用されるアイコナール方程式の境界値問題を解く高速マーチング法のステップに優先順位を付ける目的で、乱雑な優先キューが使用されてきた。この方法では、ダイクストラ法の連続バージョンに似た優先順位付け法を使用して、移動する境界が離散点の集合 (整数グリッドの点など) を横切る時間を見つけ、その実行時間はこれらの点の優先キューによって左右される。このアルゴリズムで使用される優先順位を整数に丸め、これらの整数にバケット キューを使用することで、線形時間まで高速化できる。ダイクストラ法やダイアル法と同様に、優先順位は単調であるため、高速マーチングではバケット キューの単調な最適化とその分析を使用できる。ただし、離散化によって結果の計算にいくらかの誤差が生じる。^[4]

• ソフトヒープ、近似優先度を使用して優先キューを高速化する別の方法