6

バイナリ ヒープは、プライオリティ キューなどでよく使用されます。基本的な考え方は、不完全なヒープ ソートの考え方です。トップ要素をすばやく取り出すために、データを「十分に」ソートしたままにします。

4-ary ヒープは理論的にはバイナリ ヒープより劣りますが、いくつかの利点もあります。たとえば、必要なヒープの再構築操作は少なくなりますが (ヒープがはるかに浅いため)、明らかに各レベルでより多くの比較が必要になります。しかし (そしておそらくそれが彼らの主な利点でしょうか?) CPU キャッシュの局所性が向上している可能性があります。そのため、一部の情報源は、実際には 3 項ヒープと 4 項ヒープがフィボナッチ ヒープとバイナリ ヒープの両方よりも優れていると述べています。実装がそれほど難しくないはずです。追加のケースは単なる追加のifケースです。

プライオリティ キューの 4-ary ヒープ (および 3-ary) を試して、ベンチマークを行った人はいますか? Java では、広範囲にベンチマークを行うまで、速度が速いか遅いかはわかりません。そして、私がGoogleで見つけたすべてのものから、それは言語とユースケースにかなり依存している可能性があります. 一部の情報源は、3-ary が彼らにとって最高のパフォーマンスを発揮することを発見したと言っています。

さらにいくつかのポイント：

  • PriorityQueue明らかにバイナリヒープです。しかし、たとえばクラスには、一括読み込みと一括修復のサポートが欠けているかreplaceTopElement、大きな違いを生む可能性があります。たとえば、一括読み込みは;O(n)の代わりです。O(n log n)一括修復は、より大きな候補セットを追加した後も基本的に同じです。ヒープのどの部分が無効かを追跡するには、単一の整数を使用します。+replaceTopElementよりもはるかに安価です(ポーリングがどのように実装されているかを考えてみてください: 一番上の要素を最後の要素に置き換えてください)polladd
  • もちろんヒープは複雑なオブジェクトに人気がありますが、優先順位は倍精度の整数であることがよくあります。ここで文字列を比較しているわけではありません。通常は（基本的な）優先度です
  • PQ は、上位 k 個の要素を取得するためだけによく使用されます。たとえば、A*-search は、ゴールに到達したときに終了できます。その後、あまり良くないパスはすべて破棄されます。したがって、キューが完全に空になることはありません。4 ウェイ ヒープでは、順序が少なくなり、約半分 (親ノード数の半分) になります。したがって、必要のないこれらの要素に課される順序が少なくなります。(ヒープソートを行っているなどの理由で、ヒープを完全に空にする場合はもちろん異なります。)
4

3 に答える 3

2

@ErichSchubert の提案に従って、ELKIから実装を取得し、それらを 4 配列ヒープに変更しました。4-ary ヒープに関する多くの出版物が 1 インデックス配列の数式を使用しているため、インデックスを正しく取得するのはちょっとしたトリックでした?!?

ELKI 単体テストに基づく初期のベンチマーク結果を次に示します。200000Double個のオブジェクトが事前に割り当てられ (メモリ管理が過度に測定されるのを避けるため)、シャッフルされます。

ウォームアップとして、100 回の反復をベンチマークするために、ヒープごとに 10 回の反復が実行されますが、おそらくこれをさらにスケールアップしてみます。10 ～ 30 秒というのは、まだベンチマークにはそれほど現実的ではありません。OTOH も標準偏差を測定する必要があります。各反復で、200000 個の要素がヒープに追加され、その半分が再度ポーリングされます。はい、ワークロードをより複雑にすることもできます。

結果は次のとおりです。

  • 私の 4-ary DoubleMinHeap: 10.371
  • ELKI DoubleMinHeap: 12.356
  • ELKI Heap<Double>: 37.458
  • ジャワPriorityQueue<Double>：45.875

したがって、4-ary ヒープ (おそらくまだ L1 キャッシュにアラインされていない!) とプリミティブdouble の ELKI ヒープの違いはそれほど大きくありません。まあ、10% から 20% くらいです。それはもっと悪いかもしれません。

doubleプリミティブのヒープとオブジェクトのヒープの違いDoubleははるかに大きいです。そして、ELKIHeapは確かに Java よりも明らかに高速ですPriorityQueue(ただし、Java は分散が大きいようです)。ただし、ELKI にはわずかな「バグ」がありました。少なくとも、プリミティブ ヒープはまだ一括読み込みコードを使用していませんでした。それはそこにあり、使用されていないだけです。すべての要素が次のpoll(). 基本的に、数行を削除して1つのensureValid();呼び出しを追加することにより、実験用にこれを修正しました。さらに、私はまだ 4-ary オブジェクト ヒープも持っておらず、ELKIDoubleObjectMinHeapもまだ含めていません... ベンチマークするのはかなり多いので、おそらく caliper を試してみます。

于 2013-01-04T01:00:34.113 に答える
1

自分でベンチマークを行ったわけではありませんが、関連性を持たせるためのいくつかのポイントがあります。

まず、PriorityQueueの標準Java実装はバイナリヒープを使用することに注意してください。

n-aryヒープのキャッシュ局所性の利点にもかかわらず、平均してバイナリヒープが依然として最良のソリューションであるというのはもっともらしいケースです。以下は、これが当てはまる可能性がある、少し手が波打つ理由です。

  • 最も興味深いオブジェクトの場合、比較コストは、ヒープデータ構造自体のキャッシュの局所性の影響よりもおそらくはるかに重要です。n-aryヒープには、さらに多くの比較が必要です。これはおそらく、ヒープ自体のキャッシュ局所性の影響を上回るのに十分です。
  • 単に数値のヒープを配置している場合（つまり、intまたはdoubleの配列に裏打ちされている場合）、chacheの局所性は価値のある利点であることがわかります。しかし、そうではありません。通常、オブジェクト参照のヒープがあります。各比較では、参照されるオブジェクトとそのフィールドを調べるために少なくとも1つの追加の参照に従う必要があるため、オブジェクト参照自体のキャッシュの局所性はあまり役に立ちません。
  • 優先ヒープの一般的なケースは、おそらく非常に小さなヒープです。パフォーマンスの観点から気にするほど十分にヒットしている場合は、とにかくすべてがL1キャッシュにある可能性があります。したがって、とにかくn-aryヒープのキャッシュ局所性の利点はありません。
  • ビット単位の演算でバイナリヒープを処理する方が簡単です。確かにそれは大きな利点ではありませんが、少しでも役に立ちます。
  • 単純なアルゴリズムは、一般に、より複雑なアルゴリズムよりも高速です。他のすべてのアルゴリズムは同じですが、これは、一定のオーバーヘッドが低いためです。命令キャッシュの使用量が少ない、コンパイラがスマートな最適化を見つける可能性が高いなどの利点があります。これも、バイナリヒープに有利に働きます。

もちろん、どちらが最高のパフォーマンスを発揮するかについて実際の結論に達する前に、独自のデータに対して独自のベンチマークを実行する必要があります（そして、違いが気になるほど十分であるかどうか、私は個人的に疑っています...）。

編集

また、以下のコメントで元の投稿者がプリミティブキーについて言及していることを考えると、興味深いプリミティブキーの配列を使用して優先ヒープの実装を作成しました。

誰かがテストの実行に興味を持っていれば、これはおそらくベンチマークの目的で比較的簡単にn-aryバージョンにハッキングされる可能性があります。

于 2012-12-24T12:00:28.537 に答える
1

4 配列ヒープのベンチマークはまだ行っていません。私は現在、独自のヒープ実装を最適化しようとしています。そこでも 4 配列ヒープを試しています。その通りです。実装の違いによって誤解を招きやすく、ホットスポットの最適化が結果に大きく影響するため、これを慎重にベンチマークする必要があります。さらに、小さなヒープは、おそらく大きなヒープとは異なるパフォーマンス特性を示します。

JavaPriorityQueueは非常に単純なヒープ実装ですが、それは Hotspot がそれを適切に最適化することを意味します。まったく悪くありません。ほとんどの人は、もっと悪いヒープを実装するでしょう。ただし、たとえば、効率的な一括読み込みや一括追加 (一括修復) は実際には行われません。ただし、私の実験では、非常に大きなヒープを使用しない限り、挿入を繰り返すシミュレーションでも、この実装を一貫して打ち負かすことは困難でした。poll()さらに、多くの場合、 +の代わりにヒープの一番上の要素を置き換えると効果がありますadd()。これは Java ではサポートされていませんPriorityQueue。

バージョン間の ELKI のパフォーマンスの向上 (および ELKI ユーザーであることがわかりました) の一部は、実際には改善されたヒープ実装によるものです。しかし、これは浮き沈みがあるため、実際のワークロードでどのヒープ バリエーションが最も優れたパフォーマンスを発揮するかを予測することは困難です。私たちの実装の主な利点は、おそらく「replaceTopElement」関数を持つことです。ここでコードを調べることができます：

SVN de.lmu.ifi.dbs.elki.utilities.heap パッケージ

そこに一連のヒープがあることに気付くでしょう。それらはさまざまなものに最適化されており、さらにリファクタリングが必要になります。これらのクラスの多くは、 GNU Troveと同様に、実際にはテンプレートから生成されます。その理由は、ボックス化されたプリミティブを管理する場合、Java は非常にコストがかかる可能性があるためです。(はい、これを別のライブラリに分割する計画があります。優先度が高くないだけです。)

ELKI は意図的にjava.util.CollectionsAPI を推奨していないことに注意してください。特にjava.util.Iteratorクラスが非常にコストがかかることがわかったので、ELKI 全体でC++ スタイルの反復子を使用するよう人々に奨励しようとしています。

for (Iter iter = ids.iter(); iter.valid(); iter.advance()) {

java.util.Iterator多くの場合、 APIを介して多くの不要なオブジェクトの作成を節約できます。さらに、これらの反復子は複数の(そしてプリミティブな) 値ゲッターを持つことができます。ここIterator.next()で、ゲッターと事前演算子の混合です。

さて、話が逸れすぎて、4 配列ヒープの話題に戻ります。

4 配列ヒープを試してみたい場合は、ObjectHeapそこのクラスから始めることをお勧めします。

更新: 私はマイクロベンチマークを行ってきましたが、これまでの結果は決定的ではありません. 連続で倒すのは難しいPriorityQueue。特に、一括読み込みと一括修復は、私のベンチマークでは何もカットしていないようです。おそらく、これらにより、HotSpot の最適化が低下したり、ある時点で最適化が解除されたりする可能性があります。多くの場合、単純な Java コードは複雑なロジックよりも高速です。これまでのところ、一括読み込みのない 4 配列ヒープが最適に機能しているようです。私はまだ5-aryを試していません。3-ary は 4-ary ヒープとほぼ同じです。4-ary のメモリ レイアウトは少し優れています。安全な配列のサイズ変更にヒープオブヒープアプローチを試すことも検討しています。しかし、コードの複雑さが増すということは、実際には実行速度が遅くなることを意味すると思います。

于 2012-12-31T14:42:17.767 に答える