9

STL (g++) の priority_queue のパフォーマンスを比較したところ、プッシュとポップが期待したほど速くないことがわかりました。次のコードを参照してください。

#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 の 54% を使用します

(-O3 を指定しない場合、testMap は testPriorityQueue よりもはるかに高速です) testPriorityQueue に最も時間がかかると思われる関数が呼び出されます

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

その関数は pop() 呼び出しから呼び出されるようです。

この関数は正確に何をしますか? 別のコンテナーまたはアロケーターを使用して回避する方法はありますか?

4

2 に答える 2

9

優先度キューはヒープとして実装されます。これは、ヘッド要素を削除するたびに「再調整」する必要があります。リンクされた説明でdelete-minは、 (またはヘッド) 要素がフラット化されたバイナリ ツリーのルートO(log n)であるため、操作です。min

セットは通常、赤黒のツリーとして実装され、min 要素は一番左のノードになります (つまり、リーフか、最大で右の子を持つノードのいずれかになります)。したがって、移動する子は最大で 1 つです。リバランスはpop、許容される不均衡度に基づいて、複数回の呼び出しで償却できます。

ヒープに利点がある場合は、参照の局所性にある可能性が高いことに注意してください (ノードベースではなく連続しているため)。これはまさに、callgrind が正確に測定するのが難しいかもしれない一種の利点であるため、この結果を受け入れる前に、経過リアルタイム ベンチマークも実行することをお勧めします。

于 2012-08-03T17:49:26.047 に答える
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フラグでコンパイルした場合：64ビットLinuxの-O3これにより、次のようになります。

fast_priority_queue: 260000
std::multiset: 620000
std::priority_queue: 490000
于 2012-08-03T20:00:37.843 に答える