12

私は最近、バーナード・チャゼルの論文「ソフト・ヒープ、バーナード・チャゼルによる最適なエラー率を持つおおよその優先度キュー」( http://www.link.cs.cmu.edu/15859-f07/papers/chazelle-soft-heap. pdf )

この論文は「腐敗」について多くのことを語っています。破損とは何ですか?要素はどのように破損するのですか?また、どのように役立ちますか?

私は論文とグーグルを読むのに多くの時間を費やしましたが、これはまだ意味がありません.

4

2 に答える 2

27

優先度キューに関するほとんどの研究論文では、キュー内の各要素には、要素が挿入されるときに設定される優先度と呼ばれる関連番号があります。次に、要素は優先度の高い順にキューから取り出されます。優先度キューをサポートする最近のほとんどのプログラミング言語は、実際には明示的な優先度を使用せず、代わりに比較関数に依存して要素をランク付けしますが、ソフトヒープは「関連付けられた数値優先度」モデルを使用します。

プライオリティ キューは優先度の高い順に要素をデキューするため、一連の値を並べ替えるために使用できます。まず、すべての要素を優先度キューに挿入し、その優先度をシーケンス内のランクと等しくしてから、優先度キューからすべての要素をデキューします。 . これにより、要素がソートされた順序で引き出されます。

ただし、プライオリティ キューと並べ替えの間の接続には代償が伴います。比較ソート アルゴリズムには既知の下限があります (O(n log n) よりも優れたランタイムを持つ比較ソート アルゴリズムはありません)。したがって、比較ベースの優先度キューの実行時間には下限があります。具体的には、n 個のエンキューと n 個のデキューの合計コストが O(n log n) を超えないようにする必要があります。ほとんどの場合、これで問題ありませんが、場合によっては十分な速度が得られません。

プライオリティ キューを使用して入力シーケンスを並べ替えることができる限り、n 回のエンキューと n 回のデキューの実行時間は O(n log n) に勝ることはありません。しかし、プライオリティ キューが入力をソートしない場合はどうなるでしょうか。極端に言えば、プライオリティ キューが完全に任意の順序で要素を返す場合、時間 O(n) で n 個のエンキューと n 個のデキューを実装できます。たとえば、スタックまたはキューを使用するだけです。

直感的には、ソフト ヒープは、「常に並べ替えられる」という両極端と「順序がまったく保証されない」という両極端の間の架け橋と考えることができます。各ソート ヒープは、「破損パラメータ」と呼ばれる量 ε でパラメータ化されます。これは、ソフト ヒープから出力される値がどれだけソートされているかを決定します。具体的には、ε が 0 に近づくにつれて、出力は徐々にソートされ、ε が 1 に近づくにつれて、出力はより恣意的になります。適切には、ソフト ヒープ操作の実行時間は O(log ε -1 )の関数として決定されるため、操作の実行時間は ε が上がるにつれてどんどん安くなります (したがって、出力のソートが少なくなります)。演算は ε が下がるにつれてコストが高くなります (この場合、出力はますますソートされます)。

ソフト ヒープは、「破損」という新しい概念を使用して、出力がどの程度ソートされていないかを正確に定量化します。通常のプライオリティ キューでは、エレメントとプライオリティのペアを挿入すると、エレメントのプライオリティは変更されません。ソフト ヒープでは、要素がソフト ヒープ内にあるときに、優先度に関連付けられた要素が破損する可能性があります。要素の優先度が壊れている場合、その優先度はある程度上がります。(ソフト ヒープは優先度の高い順に要素をデキューするため、要素の優先度が上がるということは、通常よりも遅くキューから出てくることを意味します)。言い換えると、要素がデキューされるときの要素の優先度は、エンキューされるときと必ずしも同じではないため、破損によって要素がソートされた順序で出てこなくなります。

ε の選択によって、いくつの異なる要素の優先度が損なわれるかが調整されます。ε が小さいと、優先順位が壊れる要素が少なくなり、ε が大きいと、優先順位が壊れる要素が多くなります。

さて、具体的な質問ですが、要素の優先度はどのように壊れてしまいますか?それはどのように役立ちますか? あなたの最初の質問は良い質問です - データ構造はどのようにして優先順位を壊すかを決定しますか? これを表示するには 2 つの方法があります。まず、ソフト ヒープをデータ構造と考えることができます。このデータ構造では、どの程度の破損を許容できるか (ε パラメーター) を事前に指定します。データ構造は、破損しない限り、いつ、どのように優先度を破損するかを内部的に決定します。総破損レベルを超えています。データ構造がこのような決定を下すのが奇妙に思える場合は、データ構造の観察可能な動作に影響を与える可能性がある内部で実際にランダムな選択が行われているブルーム フィルターやスキップリストのようなものを考えてみてください。

内部的には、ソフト ヒープの 2 つの既知の実装 (チャゼルの元の論文からの実装と、バイナリ ツリーを使用したその後のクリーンアップ)は、要素がグループ化され、すべてが共通の優先順位を共有する、相乗りと呼ばれる手法を使用して破損を実装します。この破損は、各グループ内のすべての要素の元の優先順位が忘れられ、代わりに新しい優先順位が使用されるために発生します。要素がどのようにグループ化されるかの実際の詳細は恐ろしく複雑であり、実際に調べる価値はありません。そのため、「データ構造は、より多くの要素を破損しない限り、必要に応じて破損することを選択します。 εを選んだときに指定したよりも。」

次に、なぜこれが役立つのでしょうか。実際にはそうではありません。ソフト ヒープは、ほとんど理論上の関心のみを対象としています。理論的に優れている理由は、ε が正しく選択されている場合、ソフト ヒープからの n 回の挿入と n 回の削除の実行時間が O(n) - O(n log n) よりも高速になる可能性があるためです。当初、ソフト ヒープは、最小スパニング ツリーを構築するための高速アルゴリズムのビルディング ブロックとして使用されていました。これらは、線形時間選択の新しいアルゴリズムでも使用されます。これは、有名な中央値の中央値アルゴリズム以来、線形時間で実行される最初の決定論的アルゴリズムです。どちらの場合も、アルゴリズムがソートされたシーケンスの大まかな概算を取得できるように、入力要素を「ほぼ」ソートするためにソフト ヒープが使用されます。完璧。

要約する：

  • 優先順位の破損は、完全な並べ替え (正確だが遅い) と任意の並べ替え (不正確だが非常に高速) の間のトレードオフを行う方法です。パラメータ ε は、スペクトル上のどこに破損の量があるかを決定します。
  • 破損は、ソフト ヒープ内の既存の要素の優先度を変更することによって機能します。特に、一部の要素の優先度を上げることによって機能します。低破損はほぼソートされたシーケンスに対応し、高破損はより任意のシーケンスに対応します。
  • 破損が実行される方法は、データ構造に固有であり、理解するのが非常に困難です。ソフト ヒープは、必要なときに破損を実行するものと考えるのが最善ですが、ε の選択によって課される制限を超える方法ではありません。
  • 破損は、並べ替えが遅すぎる理論的な設定では役立ちますが、実際には、ほぼ正しく並べ替えられたシーケンスで十分です。実務で役に立たない可能性が高いです。

お役に立てれば！

于 2014-09-30T17:36:33.340 に答える