2

ここから取得したペアリングヒープの C++ での実装を試しています 。 ://home.fnal.gov/~stoughto/build/graphviz-2.22.2/lib/vpsc/pairingheap/PairingHeap.cpp

その PairingHeap を std::priority_queue と比較した結果は次のとおりです。

gcc 4.7 -O3、コア i7 2.4Ghz rdstc 命令でサイクルを測定

-------------------------------------------------------------------------------

for 100.000 elements:
o std::priority_queue<int>
    - insert:           9,800,415 cycles
    - extract:         29,712,818 cycles
    - total:           39,513,233 cycles       [0.031secs]
o PairingHeap<int>
    - insert:          34,381,467 cycles
    - extract:        259,986,113 cycles
    - total:          294,367,580 cycles       [0.125secs]


-------------------------------------------------------------------------------


for 1.000.000 elements:
o std::priority_queue<int>
    - insert:         95,954,533 cycles
    - extract:       518,546,747 cycles
    - total:         614,501,280 cycles       [0.296secs]
o PairingHeap<int>
    - insert:        344,453,782 cycles
    - extract:     3,856,344,199 cycles
    - total:       4,200,797,981 cycles       [1.593secs]

-------------------------------------------------------------------------------


for 10.000.000 elements:
o std::priority_queue<int>
    - insert:        999,836,450 cycles
    - extract:    10,634,407,049 cycles
    - total:      11,634,243,499 cycles       [4.390secs]
o PairingHeap<int>
    - insert:      3,441,903,781 cycles
    - extract:    61,166,421,272 cycles
    - total:      64,608,325,053 cycles       [24.187secs]

ペアリング ヒープは std::priority_queue よりも高速である必要があります。操作が漸近的に高速になるはずですが、代わりに、ここではペアリング ヒープが非常に遅くなります。これは、std::priority_queue が内部でベクトルを使用するためだと思います。これは、ペアリング ヒープのように、整数ごとにノードを割り当てるよりもはるかにキャッシュ フレンドリーです。

それで、私の質問は次のとおりです。キャッシュにはるかに適しているという理由だけで、漸近的に優れたデータ構造が悪いものに（大部分）打ち負かされる可能性がありますか？デフォルトの std::priority_queue がそれよりも大幅に高速になる可能性がある場合、ペアリング ヒープなどのより複雑なデータ構造に多くの時間を費やす価値はありますか?

私が使用した Pairing ヒープの実装がただのがらくただとは考えていませんでしたが、そうではないようです。私が試した他の実装はさらに悪いからです! 考え？

4

2 に答える 2

5

それで、私の質問は次のとおりです。キャッシュに適しているという理由だけで、漸近的に優れたデータ構造が悪いものに（大部分）打ち負かされることはありますか？

はい、それはいつも起こります。キャッシュの使いやすさ以外にも、他の原因 (一定の要因) があります。同じ単語の他の使用法と同様に、ここでの漸近性は、何か (通常は問題のサイズ) が無限大になることを指します。A が B よりも漸近的に優れているということは、それが最終的に良くなることを示しているだけであり、特定の値に対してより優れている (または等しい) ということではありません。この比率は、データセットが大きいほど少し改善されますが、十分ではありません。

バイナリ ヒープでさえ、ある程度大きなデータ セット (あなたのデータ セットなど) のキャッシュにはあまり適していないことに注意してください。ノードの子と親はまったく別のページにある可能性が高いため、最後の数レベルのキャッシュから実際に何かを取得するだけです (または、たまたま同様のパスを持つ要素にアクセスする場合、それはほとんど任意のデータ構造)。これを改善する B-heap と呼ばれるバリアントがありますが、詳細を見つけることができませんでした (2 つの実装と、計算の RAM モデルがどのように誤解を招くかについての怒り)。

確実にプロファイリングする必要がありますが、割り当てと割り当て解除の繰り返しにかなりの時間がかかる可能性があります。プール アロケータ (ブースト、または std::vector の上にハンドロールされたもの - ポインタを整数に置き換えることができ、スペースを節約できる可能性があります) は、このコストを大幅に削減できます。この実装では、子リストにリンクされたリストを使用しているようにも見えますが、これはおそらくキャッシュをさらに悪化させます。配列には追加のコピーが必要ですが、実際には改善される可能性があります。

デフォルトの std::priority_queue がそれよりも大幅に高速になる可能性がある場合、ペアリング ヒープなどのより複雑なデータ構造に多くの時間を費やす価値はありますか?

いくつかの最適化 (特殊なアロケーターや巧妙なノード レイアウトなど) と組み合わせた十分に大きなデータ セットは、バランスを有利に傾ける可能性があります。いずれにせよ、このステートメントは少し自滅的です: 予想されるユース ケースでペアリング ヒープがバイナリ ヒープよりも高速である場合、標準ライブラリがペアリング ヒープを使用する可能性があります。

また、少なくとも純粋な関数型言語では、ペアリング ヒープの実装は非常に簡単です (ただし、あまり効率的ではありません)。それはあなたと C++ にとってはほとんど役に立たないかもしれませんが、それは何かであり、「より複雑な」部分に挑戦しています。

于 2013-07-04T12:01:53.927 に答える