爲什麼在這種情況下，STL的priority_queue比multiset快不了多少？

Question

我正在比較STL（g ++）priority_queue的性能，發現push和pop沒有我期望的那麼快。見下面的代碼：

#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(); 
} 

我編譯這個-O3然後跑去的valgrind --tool = callgrind，KCachegrind testMap花費總CPU testPriorityQueue的54％需要CPU

的44％（無 - O3 testMap比testPriorityQueue） 似乎把大部分時間用於testPriorityQueue該功能被稱爲

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

這個功能似乎從彈出稱爲快得多（）打電話。

這個函數到底做了什麼？有沒有辦法通過使用不同的容器或分配器來避免它？

Answer 1

優先級隊列實現爲heap：必須每隔「重新平衡」時間刪除head元素。在鏈接描述中，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; 
} 

當G ++ 4.1.2標誌編譯：-O3在64位Linux這給了我：

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