バケットキュー

Bucket_queue

バケットキューがあるデータ構造を実装することをプライオリティキュー 抽象データ型は、それが数値の優先順位を持つ要素の動的なコレクションを維持し、最小（または最大）の優先度を持つ要素への迅速なアクセスを可能にします：。バケットキューでは、優先度は整数である必要があり、優先度の範囲が狭いアプリケーションに特に適しています。 Aバケットキューのアレイの形有するバケット：配列、その細胞が含まれている優先順位によってインデックスアイテムのコレクションを互いに同じ優先順位で。このデータ構造では、要素の挿入と優先順位の変更に一定の時間がかかります。最小優先度要素の検索と削除には、バケットの数に比例する時間、または最後に見つかったバケットへのポインターを維持することにより、連続する操作間の優先度の違いに比例する時間がかかります。
バケットキュー
1から6の範囲の優先度に適したバケットの配列。最小優先度要素は、左端の空でないバケットに
タイプ
優先キュー
発明された 1969年 によって発明された
ロバート・ダイアル
時間複雑で大きなO記法
アルゴリズム
平均
最悪の場合
入れる
O（1）
O（1）
検索分
O（#priorities）
O（#priorities）
削除分
O（#priorities）
O（#priorities）
減少キー
O（1）
O（1）
バケットキューは、鳩の巣ソート（バケットソートとも呼ばれます）の優先度キューの類似物です。これは、要素を優先度でインデックス付けされたバケットに配置し、バケットを連結するソートアルゴリズムです。選択ソートの優先キューとしてバケットキューを使用すると、鳩の巣ソートアルゴリズムの形式が得られます。バケットキューは、バケット優先キューまたは制限付き高さ優先キューとも呼ばれます。実数の優先度の量子化された近似に使用される場合、それらは乱雑な優先度付きキューまたは疑似優先度付きキューとも呼ばれます。これらは、実数による正確な優先順位付けのために同様のバケット配列を使用する構造であるカレンダーキューと密接に関連しています。
バケットキューのアプリケーションは、の計算含むグラフの縮重、高速アルゴリズムのための最短経路と最も広い経路小さな整数または既にソートされ、そして貪欲である重み付きグラフの近似アルゴリズムのための集合被覆問題を。構造の量子化バージョンは、スケジューリングやコンピューターグラフィックスのマーチングキューブにも適用されています。バケットキューの最初の使用は、Dial（1969）による最短経路アルゴリズムでした。

コンテンツ
1 手術
1.1 基本的なデータ構造 1.2 最適化 1.3 例
2 アプリケーション
2.1 グラフの縮退 2.2 最短経路のダイヤルのアルゴリズム 2.3 貪欲なセットカバー 2.4 スケジューリング 2.5 速い行進
3 も参照してください
4 参考文献

手術

基本的なデータ構造
バケットキューは、0または1から既知の境界Cまでの範囲の整数の優先度を持つ要素、および要素の挿入、要素の優先度の変更、または最小の要素の抽出（検索と削除）を行う操作を処理できます（または最大）優先度。これは、コンテナデータ構造の配列Aで構成されています。ほとんどのソースでは、これらのコンテナは二重にリンクされたリストですが、代わりに動的配列または動的セットである可能性がp番目の配列セルA のコンテナには、優先度がpである要素のコレクションが格納されます。
バケットキューは、次の操作を処理できます。
優先度pの要素xを挿入するには、コンテナのA にxを追加します。
要素の優先度を変更するには、古い優先度のコンテナから要素を削除し、新しい優先度のコンテナに再挿入します。
最小または最大の優先度で要素を抽出するには、配列内で順次検索を実行して、それぞれ最初または最後の空でないコンテナーを見つけ、このコンテナーから任意の要素を選択して、コンテナーから削除します。
このように、挿入と優先度の変更には一定の時間がかかり、最小または最大の優先度要素の抽出には時間O（C）がかかります。

最適化
最適化として、データ構造は、配列の開始時ではなく、最後に検出された空でないバケットで、空でないバケットの各順次検索を開始できます。これは、遅延（これらの順次検索を必要になるまで遅らせる）または熱心（事前に検索を実行する）の2つの異なる方法のいずれかで実行できます。検索を実行するタイミングの選択は、これらの検索によってどのデータ構造操作が遅くなるかに影響します。Dialの元のバージョンの構造では、遅延検索が使用されていました。これは、現在キューにある要素の最小優先度の下限であるインデックスLを維持することによって実行できます。新しい要素を挿入するときは、Lを古い値と新しい要素の優先度の最小値に更新する必要が最小優先度要素を検索する場合、検索はゼロではなくLから開始できます。検索後、Lは検索で見つかった優先度と同じままにする必要が あるいは、この最適化の熱心なバージョンは、常に最初の空でないバケットを指すようにLを更新し続けます。優先度がLより小さい新しい要素を挿入すると、データ構造はLを新しい優先度に設定し、優先度Lのバケットから最後の要素を削除すると、空でないバケットが見つかるまで、より大きなインデックスを順次検索します。Lを結果のバケットの優先度に設定します。
これらの2つのバリエーションのいずれにおいても、各順次検索には、Lの古い値と新しい値の差に比例した時間がかかります。これは、最適化されていないバージョンのデータ構造での検索のO（C）時間よりも大幅に高速になる可能性が以下のようなプライオリティキューの多くのアプリケーションではダイクストラ法、最小優先順位が形成単調なシーケンスを許可する、モノトーンのプライオリティキューを使用すること。これらのアプリケーションでは、最適化された構造の怠惰なバリエーションと熱心なバリエーションの両方について、空でないバケットの順次検索は、バケットの互いに素な範囲をカバーします。各バケットはこれらの範囲の最大で1つにあるため、それらのステップ数は最大でCに追加されます。したがって、これらのアプリケーションでは、一連のn回の操作の合計時間はO（n + C）であり、この最適化なしで生じるより遅いO（nC）の時間制限ではありません。対応する最適化は、バケットキューを使用して最大優先度の要素を見つけるアプリケーションに適用できますが、この場合、最大優先度の上限となるインデックスを維持し、空でないものを順次検索する必要がバケットは、この上限から下に進む必要が
別の最適化（Dial 1969ですでに提供されている）を使用して、優先順位が単調であり、アルゴリズムの過程全体で、0からCまでの範囲全体に及ぶのではなく、常にr値の範囲内にある場合にスペースを節約できます。この場合、実際の値ではなく、rを法とする優先度によって配列にインデックスを付けることができます。最小優先度要素の検索は、最小値よりも高いが係数が低い優先度を回避するために、常に前の最小値から開始する必要が特に、このアイデアは、エッジの長さが1からrの範囲の整数であるグラフのダイクストラのアルゴリズムに適用できます。
新しいバケットキューの作成には空のバケットの配列の初期化が含まれるため、この初期化手順には優先順位の数に比例した時間がかかります。1981年にDonaldB。Johnsonによって記述されたバケットキューのバリエーションは、代わりに、空でないバケットのみをリンクリストに格納し、優先度で並べ替え、補助検索ツリーを使用して、このリンクリスト内の新しいバケットの位置をすばやく見つけます。バケツ。このバリアント構造を初期化するのに時間O（log log C）、最小または最大の優先度を持つ要素を見つけるのに一定の時間、要素を挿入または削除するのに時間O（log log D）がかかります。ここで、Dは最も近いものとの差です。挿入または削除された要素の優先度に対する優先度はますます小さくなります。

例
たとえば、0、1、2、3の4つの優先順位を持つバケットキューについて考えてみます。これは配列で構成されています。 {A}

 その4つのセルにはそれぞれ要素のコレクションが含まれており、最初は空です。この例では、 {A}

  4セットの括弧で囲まれたシーケンスとして書くことができます： =
[ ∅ ∅ ∅ ∅ ] {A = [ emptyset、 emptyset、 emptyset、 emptyset]}

 。2つの要素を挿入する一連の操作について考えてみます。 {x}

  と y {y}

  同じ優先度1で、3番目の要素を挿入します z {z}

  優先度3で、の優先度を変更します {x}

  3に設定してから、最小優先度要素の2つの抽出を実行します。
挿入後 {x}

  優先度1 =
[ ∅ {{ } ∅ ∅ ] {A = [ emptyset、 {x }、 emptyset、 emptyset]}

 。
挿入後 y {y}

  優先度1 =
[ ∅ {{ 、 y } ∅ ∅ ] {A = [ emptyset、 {x、y }、 emptyset、 emptyset]}

 。
優先度3でzを挿入した後 =
[ ∅ {{ 、 y } ∅ {{z } ]
{A = [ emptyset、 {x、y }、 emptyset、 {z }]}

 。
xの優先度を1から3に変更するには、から削除する必要が [ 1 ] {A }

  に追加します [ 3 ] {A }

 、その後 =
[ ∅ {{ y } ∅ {{ 、z } ]
{A = [ emptyset、 {y }、 emptyset、 {x、z }]}

 。
バケットキューの基本バージョンで最小優先度要素を抽出すると、 {A}

  最初の空でない要素を見つけるには： [ 0 ] {A }

  空ですが [ 1] =
{{y }
{A = {y }}

 、空でないセット。このセットの任意の要素（唯一の要素、 y {y}

 ）最小優先度要素として。削除 y {y}

  構造の葉から =
[ ∅ ∅ ∅ {{ 、z } ]
{A = [ emptyset、 emptyset、 emptyset、 {x、z }]}

 。
バケットキューの基本バージョンでの2番目の抽出操作は、配列の先頭から再度検索します。 [ 0] = ∅
{A = emptyset}

 、 [ 1] = ∅
{A = emptyset}

 、 [ 2] = ∅
{A = emptyset}

 、 [ 3] =
{A = {}}

 空ではありません。バケットキューの改良されたバリアントでは、この検索は、空ではないことが判明した最後の位置から代わりに開始されます。 [ 1 ] {A }

 。どちらの場合にも、 [ 3] =
{{ 、z }
{A = {x、z }}

 空でない最初のセットであることがわかります。その要素の1つは、最小優先度要素として任意に選択されます。例えば、 z {z}

 選ばれるかもしれません。この要素は削除され、残ります =
[ ∅ ∅ ∅ {{ } ] {A = [ emptyset、 emptyset、 emptyset、 {x }]}

 。
アプリケーション編集

グラフの縮退
バケットキューが維持するために使用することができる頂点の無向グラフそれらによって優先順位、度、繰り返し検索し、最小程度の頂点を削除します。この欲張りアルゴリズムを使用して、特定のグラフの縮退を計算できます。これは、削除時の頂点の最大次数に等しくなります。各頂点はその次数に比例する時間で検出され、すべての頂点の次数の合計はグラフのエッジの数で線形であるため、アルゴリズムは、最小優先度の下限を維持する最適化の有無にかかわらず、線形時間を要します。

最短経路のダイヤルのアルゴリズム
ためのダイクストラ法で最短経路で有向グラフ正の整数であるエッジ重みと、優先度が単調であると単調バケットキューの結合時得るために使用することができるO（M + DC）、mはですエッジの数、dはネットワークの直径、cは最大（整数）リンクコストです。 ダイクストラのアルゴリズムのこの変形は、1969年に公開したRobert B. Dialにちなんで、Dialのアルゴリズムとしても知られています。量子化されたバケットキューを使用して、グラフに同じアイデアが機能します。最大重みと最小重みの比率が最大でcの場合、正の実エッジ重みを使用します。この量子化バージョンのアルゴリズムでは、量子化されていない優先度付きキューの結果と比較して、頂点が順不同で処理されますが、正しい最短パスが引き続き検出されます。これらのアルゴリズムでは、優先順位は幅c + 1の範囲にのみ及ぶため、モジュラー最適化を使用してスペースをO（n + c）に減らすことができます。
同じアルゴリズムの変形を最大経路問題に使用できます。整数以外のエッジの重みを整数の優先順位を割り当てることができるサブセットにすばやく分割する方法と組み合わせることで、最大経路問題の単一ソース単一宛先バージョンに対するほぼ線形時間のソリューションにつながります。

貪欲なセットカバー
集合カバー問題は、その入力として持つ集合族を。出力は、これらのセットのサブファミリーであり、元のファミリーと同じユニオンで、可能な限り少ないセットを含む必要がこれはNP困難ですが、対数近似比を達成する欲張り近似アルゴリズムを備えており、P = NPでない限り本質的に最良です。この近似アルゴリズムは、カバーされていない残りの要素の可能な最大数をカバーするセットを繰り返し選択することにより、そのサブファミリーを選択します。アルゴリズム設計の標準的な演習では、すべての入力セットのサイズの合計である入力サイズで線形時間を要するこのアルゴリズムの実装が求められます。
これは、入力ファミリのセットのバケットキューを使用して解決でき、それらがカバーする残りの要素の数によって優先順位が付けられます。欲張りアルゴリズムがその出力の一部としてセットを選択するたびに、新しくカバーされたセット要素は、それらをカバーする他のセットの優先順位から差し引かれるべきです。アルゴリズムの過程で、これらの優先順位の変更の数は、入力セットのサイズの合計にすぎません。優先順位は単調に減少する整数であり、カバーされる要素の数によって上限が定められます。欲張りアルゴリズムの各選択には、最大優先度のセットを見つけることが含まれます。これは、最新の前の最大値から開始して、バケットキューのバケットを下方向にスキャンすることで実行できます。合計時間は、入力サイズに対して線形です。

スケジューリング
バケットキューは、たとえば、サービス品質が保証されたインターネットデータのパケット転送など、期限付きのタスクをスケジュールするために使用できます。このアプリケーションでは、期限を個別の間隔に量子化する必要があり、期限が同じ間隔に該当するタスクは同等の優先度であると見なされます。
量子化バケットキューデータ構造のバリエーションであるカレンダーキューは、離散イベントシミュレーションのスケジューリングに適用されています。キュー内の要素は、シミュレーション内でイベントが発生する時間によって優先される将来のイベントです。このアプリケーションでは、イベントの順序が重要であるため、優先順位を概算することはできません。したがって、カレンダーキューは、バケットキューとは異なる方法で最小優先度要素の検索を実行します。バケットキューでは、最初の空でないバケットの任意の要素が返される可能性がありますが、代わりにカレンダーキューはそのバケットは、量子化されていない優先度が最も小さいものを判別します。これらの検索を高速に保つために、このバリエーションでは、量子化のスケールを調整し、バランスが崩れたときにデータ構造を再構築することにより、バケットの数を要素の数に比例させようとします。最悪の場合（多くの要素がすべて同じ最小バケットに収まる場合）、カレンダーキューはバケットキューよりも遅くなる可能性がありますが、要素がバケット間で均一に分散されている場合は高速であり、平均バケットサイズが一定になります。

速い行進
応用数学と数値法の解の微分方程式、乱雑プライオリティキューは、以下の工程優先順位付けするために使用されている高速前進法を解決するための境界値問題のアイコナール方程式モデルを用い、波の伝播を。この方法は、ダイクストラのアルゴリズムの連続バージョンに似た優先順位付け方法を使用して、移動する境界が一連の離散点（整数グリッドの点など）と交差する時間を検出し、その実行時間は優先度付きキューによって支配されますこれらのポイントの。このアルゴリズムで使用される優先順位を整数に丸め、これらの整数にバケットキューを使用することで、線形時間まで高速化できます。ダイクストラおよびダイヤルのアルゴリズムと同様に、優先順位は単調であるため、高速マーチングでは、バケットキューの単調最適化とその分析を使用できます。ただし、離散化により、結果の計算にエラーが発生します。

も参照してください
ソフトヒープ、おおよその優先度を使用して優先度キューを高速化する別の方法

参考文献
^ Skiena、Steven S.（1998）、アルゴリズム設計マニュアル、Springer、p。181、ISBN 9780387948607。 ^ Figueira、NR（1997）、「締め切り順のサービス分野の優先キュー問題の解決策」、第6回コンピュータ通信およびネットワークに関する国際会議の議事録、IEEE Computer Society Press、pp。320–325、doi：10.1109 / icccn.1997.623330
^ ヘンジンガー、モニカ; ノエ、アレクサンダー; Schulz、Christian（2019）、「共有メモリの正確な最小カット」、2019 IEEE International Parallel and Distributed Processing Symposium、IPDPS 2019、リオデジャネイロ、ブラジル、2019年5月20〜24日、pp。13〜22、arXiv：1808.05458、doi：10.1109 / IPDPS.2019.00013
^ ラッシュ、クリスチャン; Satzger、Thomas（2009）、「高速マーチング法のO（N）実装に関する注意」（PDF）、IMA Journal of Numerical Analysis、29（3）：806–813、doi：10.1093 / imanum / drm028、MR 2520171
  ^ Robledo、Alicia; Guivant、JoséE。（2010）、「パスプランニングに適用される動的プログラミングプロセスでのリアルタイムパフォーマンスのための疑似優先度付きキュー」（PDF）、Wyeth、Gordon; Upcroft、Ben（eds。）、Australasian Conference on Robotics and Automation
^ Edelkamp、Stefan; Schroedl、Stefan（2011）、「3.1.1バケットデータ構造」、ヒューリスティック検索：理論とアプリケーション、Elsevier、pp。90–92、ISBN  9780080919737。p。も参照してこの構造の歴史と命名については157。 ^ Dial、Robert B.（1969）、「Algorithm 360：Topological ordering 」、Communications of the ACM、12（11）：632–633、doi：10.1145 / 363269.363610 。 ^ メールホルン、カート; Sanders、Peter（2008）、「10.5.1バケットキュー」、アルゴリズムとデータ構造：基本ツールボックス、Springer、p。201、ISBN  9783540779773。 ^ Bertsekas、Dimitri P.（1991）、「ダイヤルのアルゴリズム」、線形ネットワーク最適化：アルゴリズムとコード、ケンブリッジ、マサチューセッツ：MIT Press、pp。72–75、ISBN  0-262-02334-2、MR  1201582 ^ Lim、CL; モファット、アリスター; Wirth、Anthony Ian（2014）、「集合被覆問題に対する怠惰で熱心なアプローチ」、Thomas、Bruce; Parry、Dave（eds。）、37th Australasian Computer Science Conference、ACSC 2014、Auckland、New Zealand、January 2014、CRPIT、147、Australian Computer Society、pp。19–27 。特にセクション2.4「優先キュー」を参照して22。 ^ Johnson、Donald B.（1981）、「初期化とキュー操作にO（log log D）時間がかかる優先キュー」、数学システム理論、15（4）：295–309、doi：10.1007 / BF01786986、MR 0683047   ^ Matula、David W .; Beck、LL（1983）、「最小-最後の順序付けとクラスタリングおよびグラフ彩色アルゴリズム」、Journal of the ACM、30（3）：417–427、doi：10.1145 / 2402.322385、MR 0709826  。 ^ Varghese、George（2005）、Network Algorithmics：Interdisciplinary Approach to Designing Fast Networked Devices、Morgan Kaufmann、pp。78–80、ISBN  9780120884773。 ^ Festa、Paola（2006）、「最短経路アルゴリズム」、Resende、Mauricio GC; Pardalos、Panos M.（eds。）、Handbook of Optimization in Telecommunications、Boston：Springer、pp。185–210、doi：10.1007 / 978-0-387-30165-5_8 ; 特に、セクション8.3.3.6「ダイヤルの実装」の194〜195ページを参照して ^ Mehlhorn＆Sanders（2008）（Exercise 10.11、p。201）は、このアイデアをEA Dinic（Yefim Dinitz）の1978年の論文の功績によるものです。 ^ ガボウ、ハロルドN。; Tarjan、Robert E.（1988）、「2つのボトルネック最適化問題のアルゴリズム」、Journal of Algorithms、9（3）：411–417、doi：10.1016 / 0196-6774（88）90031-4、MR 0955149   ^ Dinur、Irit ; Steurer、David（2014）、「並列反復への分析的アプローチ」、Shmoys、David B.（ed。）、Symposium on Theory of Computing、STOC 2014、ニューヨーク、ニューヨーク、米国、2014年5月31日〜6月3日、 ACM、pp。624–633、arXiv：1305.1979、doi：10.1145 / 2591796.2591884、MR 3238990   ^ Johnson、David S.（1974）、「組み合わせ問題の近似アルゴリズム」、Journal of Computer and System Sciences、9：256–278、doi：10.1016 / S0022-0000（74）80044-9、MR 0449012   ^ コーメン、トーマスH。; レイザーソン、チャールズE。; リベスト、ロナルドL。; Stein、Clifford（2009）、 “”Exercise 35.3-3″”、Introduction to Algorithms（3rd ed。）、MIT Press and McGraw-Hill、p。1122、ISBN  0-262-03384-4 ^ Brown、R。（1988年10月）、「カレンダーキュー：高速 O （（ 1 ）。 {O（1）}

 シミュレーションイベントセット問題の優先キューの実装」、Communications of the ACM、31（10）：1220–1227、doi：10.1145 / 63039.63045 ^ エリクソン、K。ブルース; ラドナー、リチャードE。; LaMarca、Anthony（2000）、「静的カレンダーキューの最適化」、モデリングとコンピューターシミュレーションに関するACMトランザクション、10（3）：179–214、doi：10.1145 / 361062.361028

「https://en.wikipedia.org/w/index.php?title=Bucket_queue&oldid=1037626528」
から取得”