配對堆VS的std :: priority_queue

我特林在配對堆的C++實現，我從這裏開始了： http://home.fnal.gov/~stoughto/build/graphviz-2.22.2/lib/vpsc/pairingheap/PairingHeap.h http://home.fnal.gov/~stoughto/build/graphviz-2.22.2/lib/vpsc/pairingheap/PairingHeap.cpp 配對堆VS的std :: priority_queue

我比較這對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可以在很大程度上比它快嗎？

我只是沒有考慮到我使用的配對堆的實現只是廢話，但它似乎不是，因爲我嘗試過的其他實現更糟！想法？

來源

2013-07-04 Marco Pagliaricci

所以，我的問題是：漸近地更好的數據結構可以被更糟糕的數據結構（大部分）毆打，僅僅因爲它們更加緩存友好？

是的，這一直髮生。除緩存友好外，還有其他原因（恆定因素）。像其他使用同一個詞，漸近這裏指的是（通常，問題的大小）去無限。一個比B更接近漸近的人說，它最終會變得更好，而不是它對於某個給定的價值會更好（甚至相等）。請注意，對於較大的數據集，該比率確實有所提高，但還不夠。

請注意，即使二進制堆對於較大的數據集（例如您的）來說也不會對緩存很友好。節點的子節點和父節點可能位於完全不同的頁面上，因此只有在最後幾個級別才能真正從緩存中獲取某些內容（或者，如果訪問碰巧有相似路徑的元素，但這是給定的幾乎所有的數據結構）。有一個稱爲B-heap的變體，它在這方面有所改進，但是我一直沒能找到很多細節（只有兩個實現和關於RAM計算模型如何誤導的咆哮）。

您必須確定配置文件，但可能重複分配和釋放佔用大量時間。一個池分配器（boost），或者一個std :: vector頂層的手動滾動 - 允許用整數替換指針，這可以節省一些空間）可以大大降低成本。該實現也似乎使用鏈表來列表，這可能會更多地傷害緩存。一個數組需要一些額外的副本，但在實踐中可能會有所改進。

是否真的值得花太多的時間在一個更復雜的數據結構，如配對堆，當默認的std :: priority_queue可以在很大程度上是比它更快嗎？

有可能一個足夠大的數據集加上一些優化（例如專門的分配器和聰明的節點佈局）將有利於平衡。在任何情況下，這種說法都有點不妥：如果配對堆比預期用例的二進制堆快，那麼標準庫可能會使用配對堆！

此外，至少在純功能語言中，配對堆實現起來相當簡單（儘管效率不高）。這對你和C++來說可能沒有什麼用處，但它是對「更復雜」部分的挑戰和挑戰。

來源

2013-07-04 12:01:53 delnan

這裏的一個主要問題是內存分配和是緩存效率。

你可以嘗試什麼是實現一個固定大小的分配使用自定義operator new + operator delete爲PairNode類，以減少分配開銷（類似於一個在「更有效的C++」，第10項）。此外，這種方法最終可能更容易緩存，因爲元素更可能具有參考位置。

我已經做了這樣的QuadEdge結構（有類似的問題）的Delaunay三角測量之前，速度增加超過10-20x IIRC。如果你需要使分配器線程安全，那麼你將在性能方面付出高昂的代價。

至於實際回答一個案例或另一個案例的表現是否更好的問題，它不太可能是普遍性的，並且逐案分析是最容易知道的方法（任何其他方法會很複雜，因爲如果不實施它，你無法預測實施的質量）。不僅如此，而且不同的處理器會有所不同，結果可能取決於您傾向於獲得的數據。

來源

2013-07-04 11:54:11 Pete

配對堆VS的std :: priority_queue

回答

相關問題