この場合、STL priority_queueはマルチセットよりもあまり速くないのはなぜですか？

Question

私はSTL（g ++）priority_queueのパフォーマンスを比較しています。プッシュとポップは予想通り高速ではありません。以下のコードを参照してください。私はこの-O3をコンパイルした後、valgrindの--tool = callgrind、KCachegrind testMapを実行

#include <set> 
#include <queue> 

using namespace std; 

typedef multiset<int> IntSet; 

void testMap() 
{ 
    srand(0); 

    IntSet iSet; 

    for (size_t i = 0; i < 1000; ++i) 
    { 
     iSet.insert(rand()); 
    } 

    for (size_t i = 0; i < 100000; ++i) 
    { 
     int v = *(iSet.begin()); 
     iSet.erase(iSet.begin()); 
     v = rand(); 
     iSet.insert(v); 
    } 
} 

typedef priority_queue<int> IntQueue; 

void testPriorityQueue() 
{ 
    srand(0); 
    IntQueue q; 

    for (size_t i = 0; i < 1000; ++i) 
    { 
     q.push(rand()); 
    } 

    for (size_t i = 0; i < 100000; ++i) 
    { 
     int v = q.top(); 
     q.pop(); 
     v = rand(); 
     q.push(v); 
    } 
} 

int main(int,char**) 
{ 
    testMap(); 
    testPriorityQueue(); 
} 

は総CPUの54％を取る testPriorityQueueはなし（CPU

の44％を取ります - O3 testMapがtestPriorityQueue） popから呼ばれるように

void std::__adjust_heap<__gbe_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >, long, int, std::less<int> > 

この関数はそう

と呼ばれるtestPriorityQueueのためのほとんどの時間を取るように思われる機能よりもはるかに高速です（）コール。

この機能は何を正確に行いますか？別のコンテナやアロケータを使用して回避する方法はありますか？

Answer 1

プライオリティキューはheapとして実装されています。ヘッドエレメントを削除するたびにがリバースされる必要があります。リンクされた説明では、delete-minはO(log n)の操作です。実際にはmin（またはhead）要素が平滑化されたバイナリツリーのルートであるためです。

通常、セットはred-black treeとして実装され、min要素は左端のノードになります（したがって、リーフか、最大でも右の子を持つ）。したがって、最大で1人の子供を移動させることができ、平衡不一致の許容度に基づいて複数のpopコールでリバランスを償却することができます。

ヒープに利点がある場合は、参照ベース（ノードベースではなく隣接しているため）にある可能性が高いことに注意してください。これはちょうどが正確に測定するcallgrindのためにより困難である利点のようなものですので、私はこの結果を受け入れる前にいくつかの経過リアルタイムのベンチマークを実行することを提案したいと思います。

Answer 2

私は、-O3でコンパイルすると高速に実行されるように見える優先度キューを実装しました。 おそらく、コンパイラがSTLの場合よりもインライン化することができたからでしょうか？

#include <set> 
#include <queue> 
#include <vector> 
#include <iostream> 

using namespace std; 

typedef multiset<int> IntSet; 

#define TIMES 10000000 

void testMap() 
{ 
    srand(0); 

    IntSet iSet; 

    for (size_t i = 0; i < 1000; ++i) { 
     iSet.insert(rand()); 
    } 

    for (size_t i = 0; i < TIMES; ++i) { 
     int v = *(iSet.begin()); 
     iSet.erase(iSet.begin()); 
     v = rand(); 
     iSet.insert(v); 
    } 
} 

typedef priority_queue<int> IntQueue; 

void testPriorityQueue() 
{ 
    srand(0); 
    IntQueue q; 

    for (size_t i = 0; i < 1000; ++i) { 
     q.push(rand()); 
    } 

    for (size_t i = 0; i < TIMES; ++i) { 
     int v = q.top(); 
     q.pop(); 
     v = rand(); 
     q.push(v); 
    } 
} 


template <class T> 
class fast_priority_queue 
{ 
public: 
    fast_priority_queue() 
     :size(1) { 
     mVec.resize(1); // first element never used 
    } 
    void push(const T& rT) { 
     mVec.push_back(rT); 
     size_t s = size++; 
     while (s > 1) { 
      T* pTr = &mVec[s]; 
      s = s/2; 
      if (mVec[s] > *pTr) { 
       T tmp = mVec[s]; 
       mVec[s] = *pTr; 
       *pTr = tmp; 
      } else break; 
     } 
    } 
    const T& top() const { 
     return mVec[1]; 
    } 
    void pop() { 
     mVec[1] = mVec.back(); 
     mVec.pop_back(); 
     --size; 
     size_t s = 1; 
     size_t n = s*2; 
     T& rT = mVec[s]; 
     while (n < size) { 
      if (mVec[n] < rT) { 
       T tmp = mVec[n]; 
       mVec[n] = rT; 
       rT = tmp; 
       s = n; 
       n = 2 * s; 
       continue; 
      } 
      ++n; 
      if (mVec[n] < rT) { 
       T tmp = mVec[n]; 
       mVec[n] = rT; 
       rT = tmp; 
       s = n; 
       n = 2 * s; 
       continue; 
      } 
      break; 
     } 
    } 
    size_t size; 
    vector<T> mVec; 
}; 

typedef fast_priority_queue<int> MyQueue; 

void testMyPriorityQueue() 
{ 
    srand(0); 
    MyQueue q; 

    for (size_t i = 0; i < 1000; ++i) { 
     q.push(rand()); 
    } 

    for (size_t i = 0; i < TIMES; ++i) { 
     int v = q.top(); 
     q.pop(); 
     v = rand(); 
     q.push(v); 
    } 
} 


int main(int,char**) 
{ 
    clock_t t1 = clock(); 
    testMyPriorityQueue(); 
    clock_t t2 = clock(); 
    testMap(); 
    clock_t t3 = clock(); 
    testPriorityQueue(); 
    clock_t t4 = clock(); 

    cout << "fast_priority_queue: " << t2 - t1 << endl; 
    cout << "std::multiset: " << t3 - t2 << endl; 
    cout << "std::priority_queue: " << t4 - t3 << endl; 
} 

++ 4.1.2フラググラムを指定してコンパイル：64ビットLinux上-O3は、これは私を与える：

fast_priority_queue: 260000 
std::multiset: 620000 
std::priority_queue: 490000