एसटीएल प्राथमिकता_क्यू इस मामले में मल्टीसेट से ज्यादा तेज क्यों नहीं है?

Question

मैं एक एसटीएल (जी ++) प्राथमिकता_क्यू के प्रदर्शन की तुलना कर रहा हूं और पाया कि पुश और पॉप उतनी तेज नहीं हैं जितनी मैं अपेक्षा करता हूं। निम्नलिखित कोड देखें:

#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 कुल सीपीयू testPriorityQueue का 54% लेता है सीपीयू

का 44% लेता है (बिना - ओ 3 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 के रूप में कार्यान्वित की गई है: इसे प्रत्येक "हेड एलिमेंट को हटाते समय" रीबैलेंस्ड "होना चाहिए। लिंक्ड विवरण में, delete-min एक O(log n) ऑपरेशन है, वास्तव में min (या सिर) तत्व रूट फ़्लैटेड बाइनरी पेड़ के रूट है।

सेट आमतौर पर red-black tree के रूप में लागू किया जाता है, और न्यूनतम तत्व बाएं नोड (इसलिए या तो एक पत्ता, या सबसे सही बच्चे होने पर) होगा। इसलिए इसमें 1 बच्चे को स्थानांतरित किया जाना है, और अनियंत्रित-नेस की स्वीकार्य डिग्री के आधार पर रीबैलेंसिंग को कई pop कॉलों पर मिश्रित किया जा सकता है।

ध्यान दें कि यदि ढेर का कोई फायदा होता है, तो यह इलाके के संदर्भ में होने की संभावना है (क्योंकि यह नोड-आधारित के बजाय संगत है)। यह बिल्कुल लाभ का प्रकार है कि कॉलग्रिंड को सटीक मापने के लिए कठिन हो सकता है, इसलिए मैं इस परिणाम को स्वीकार करने से पहले कुछ विलुप्त-वास्तविक समय बेंचमार्क चलाने का सुझाव दूंगा।

Answer 2

मैंने प्राथमिकता कतार लागू की है जो -O3 के साथ संकलित होने पर तेज़ी से चलती प्रतीत होती है। शायद इसलिए कि संकलक एसटीएल मामले में अधिक से अधिक इनलाइन करने में सक्षम था?

#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 बिट लिनक्स पर -O3 यह मेरे देता है:

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