18

std::multisetをstd::priority_queueに置き換えようとしています。しかし、私はスピードの結果に失望しました。アルゴリズムの実行時間は50％増加します...

対応するコマンドは次のとおりです。

top() = begin();
pop() = erase(knn.begin());
push() = insert();

priority_queueの実装の速度に驚いています。異なる結果を期待していました（PQの方が良い）...概念的には、マルチセットが優先キューとして使用されています。優先キューとマルチセットのパフォーマンスが異なるのはなぜ-O2ですか？

10件の結果の平均、MSVS 2010、Win XP、32ビット、メソッドfindAllKNN2（）（以下を参照）

MS
N           time [s]
100 000     0.5
1 000 000   8

PQ
N           time [s]
100 000     0.8
1 000 000   12

これらの結果の原因は何ですか？ソースコードの他の変更は行われていません...あなたの助けに感謝します...

MSの実装：

template <typename Point>
struct TKDNodePriority
{
    KDNode <Point> *node;
    typename Point::Type priority;

    TKDNodePriority() : node ( NULL ), priority ( 0 ) {}
    TKDNodePriority ( KDNode <Point> *node_, typename Point::Type priority_ ) : node ( node_ ), priority ( priority_ ) {}

    bool operator < ( const TKDNodePriority <Point> &n1 ) const
    {
            return priority > n1.priority;
    }
};

template <typename Point>
struct TNNeighboursList
{
    typedef std::multiset < TKDNodePriority <Point> > Type;
};

方法：

template <typename Point>
template <typename Point2>
void KDTree2D <Point>::findAllKNN2 ( const Point2 * point, typename TNNeighboursList <Point>::Type & knn, unsigned int k, KDNode <Point> *node, const unsigned int depth ) const
{
    if ( node == NULL )
    {
            return;
    }

    if ( point->getCoordinate ( depth % 2 ) <= node->getData()->getCoordinate ( depth % 2 ) )
    {
    findAllKNN2 ( point, knn, k, node->getLeft(), depth + 1 );
    }

    else 
    {
            findAllKNN2 ( point, knn, k, node->getRight(), depth + 1 );
    }

typename Point::Type dist_q_node = ( node->getData()->getX() - point->getX() ) * ( node->getData()->getX() - point->getX() ) +
                             ( node->getData()->getY() - point->getY() ) * ( node->getData()->getY() - point->getY() );

if (knn.size() == k)
{
    if (dist_q_node < knn.begin()->priority )
    {
        knn.erase(knn.begin());
        knn.insert ( TKDNodePriority <Point> ( node,  dist_q_node ) );
    }
}

else
{
    knn.insert ( TKDNodePriority <Point> ( node,  dist_q_node ) );
}

typename Point::Type dist_q_node_straight = ( point->getCoordinate ( node->getDepth() % 2 ) - node->getData()->getCoordinate ( node->getDepth() % 2 ) ) *
                                                ( point->getCoordinate ( node->getDepth() % 2 ) - node->getData()->getCoordinate ( node->getDepth() % 2 ) ) ;

typename Point::Type top_priority =  knn.begin()->priority;
if ( knn.size() < k ||  dist_q_node_straight <  top_priority )
{
            if ( point->getCoordinate ( node->getDepth() % 2 ) < node->getData()->getCoordinate ( node->getDepth() % 2 ) )
            {
        findAllKNN2 ( point, knn, k, node->getRight(), depth + 1 );
    }

    else
    {
        findAllKNN2 ( point, knn, k, node->getLeft(), depth + 1 );
    }
}
}

PQの実装（遅い、なぜですか？）

template <typename Point>
struct TKDNodePriority
{
    KDNode <Point> *node;
    typename Point::Type priority;

    TKDNodePriority() : node ( NULL ), priority ( 0 ) {}
    TKDNodePriority ( KDNode <Point> *node_, typename Point::Type priority_ ) : node ( node_ ), priority ( priority_ ) {}

    bool operator < ( const TKDNodePriority <Point> &n1 ) const
    {
            return priority > n1.priority;
    }
};


template <typename Point>
struct TNNeighboursList
{ 
    typedef std::priority_queue< TKDNodePriority <Point> > Type;
};

方法：

template <typename Point>
template <typename Point2>
void KDTree2D <Point>::findAllKNN2 ( const Point2 * point, typename TNNeighboursList <Point>::Type & knn, unsigned int k, KDNode <Point> *node, const unsigned int depth ) const
{

    if ( node == NULL )
    {
            return;
    }

    if ( point->getCoordinate ( depth % 2 ) <= node->getData()->getCoordinate ( depth % 2 ) )
    {
    findAllKNN2 ( point, knn, k, node->getLeft(), depth + 1 );
    }

    else 
    {
            findAllKNN2 ( point, knn, k, node->getRight(), depth + 1 );
    }

typename Point::Type dist_q_node = ( node->getData()->getX() - point->getX() ) * ( node->getData()->getX() - point->getX() ) +
                             ( node->getData()->getY() - point->getY() ) * ( node->getData()->getY() - point->getY() );

if (knn.size() == k)
{
    if (dist_q_node < knn.top().priority )
    {
        knn.pop();

        knn.push ( TKDNodePriority <Point> ( node,  dist_q_node ) );
    }
}

else
{
    knn.push ( TKDNodePriority <Point> ( node,  dist_q_node ) );
}

typename Point::Type dist_q_node_straight = ( point->getCoordinate ( node->getDepth() % 2 ) - node->getData()->getCoordinate ( node->getDepth() % 2 ) ) *
                                                ( point->getCoordinate ( node->getDepth() % 2 ) - node->getData()->getCoordinate ( node->getDepth() % 2 ) ) ;

typename Point::Type top_priority =  knn.top().priority;
if ( knn.size() < k ||  dist_q_node_straight <  top_priority )
{
            if ( point->getCoordinate ( node->getDepth() % 2 ) < node->getData()->getCoordinate ( node->getDepth() % 2 ) )
            {
        findAllKNN2 ( point, knn, k, node->getRight(), depth + 1 );
    }

    else
    {
        findAllKNN2 ( point, knn, k, node->getLeft(), depth + 1 );
    }
}
}
4

4 に答える 4

8

コンパイラの最適化設定がパフォーマンスに大きな影響を与える可能性があるようです。以下のコードでは、最適化を行わなくても、multiset が vector ベースおよび deque ベースの priority_queue を簡単に打ち負かしています。ただし、「-O3」最適化を使用すると、ベクトルベースの優先キューがすべてを打ち負かします。さて、これらの実験は Linux と GCC で実行されたので、おそらく Windows では異なる結果が得られるでしょう。最適化を有効にすると、STL のベクター内の多くのエラー チェック動作が削除される可能性があると思います。

最適化なし:

pq-w-ベクトル: 79.2997ms

pq-w-deque: 362.366ms

pq-w-マルチセット: 34.649ms

-O2 最適化の場合:

pq-w-ベクトル: 8.88154ms

pq-w-deque: 17.5233ms

pq-w-マルチセット: 12.5539ms

-O3 最適化の場合:

pq-w-ベクトル: 7.92462ms

pq-w-deque: 16.8028ms

pq-w-マルチセット: 12.3208ms

テスト ハーネス (-lrt でリンクすることを忘れないでください):

#include <iostream>
#include <queue>
#include <deque>
#include <set>
#include <ctime>
#include <cstdlib>
#include <unistd.h>

using namespace std;

template <typename T>
double run_test(T& pq, int size, int iterations)
{
    struct timespec start, end;

    for(int i = 0; i < size; ++i)
        pq.push(rand());

    clock_gettime(CLOCK_THREAD_CPUTIME_ID, &start);
    for(int i = 0; i < iterations; ++i)
    {
        if(rand()%2)
            pq.pop();
        else
            pq.push(rand());

    }
    clock_gettime(CLOCK_THREAD_CPUTIME_ID, &end);

    end.tv_sec -= start.tv_sec;
    end.tv_nsec -= start.tv_nsec;
    if (end.tv_nsec < 0)
    {
        --end.tv_sec;
        end.tv_nsec += 1000000000ULL;
    }

    return (end.tv_sec*1e3 + end.tv_nsec/1e6);
}

template <class T>
class multiset_pq: public multiset<T>
{
public:
    multiset_pq(): multiset<T>() {};
    void push(T elm) { this->insert(elm); }
    void pop() { if(!this->empty()) this->erase(this->begin()); }
    const T& top() { return *this->begin(); }
};

int main(void)
{
    const int size = 5000;
    const int iterations = 100000;

    priority_queue<int, vector<int> > pqv;
    priority_queue<int, deque<int> > pqd;
    multiset_pq<int> pqms;

    srand(time(0));

    cout<<"pq-w-vector: "<<run_test(pqv, size, iterations)<<"ms"<<endl;
    cout<<"pq-w-deque: "<<run_test(pqd, size, iterations)<<"ms"<<endl;
    cout<<"pq-w-multiset: "<<run_test(pqms, size, iterations)<<"ms"<<endl;

    return 0;
}
于 2013-04-25T16:38:19.837 に答える
3

priority_queue私が理解していることによると、の実装が原因です。priority_queueは特殊なvectororとして (下に) 実装されていdequeます。priority_queue にはランダム アクセス イテレータが必要なためです。アイテムを にポップまたはプッシュする場合priority_queue、キュー内の残りのアイテムを空のスペースにコピーする必要があり、挿入でも同じことが起こります。multi_setキーに基づいています。

編集: 申し訳ありませんが、multi_set はハッシュ キーに基づいていません。何らかの理由で multi_map と混同しました。ただし、multi_set は複数の並べ替えられた連想コンテナーであり、値と同じであるキーに基づいて要素を格納します。要素が に格納される方法によりmulti_set、

...新しい要素をに挿入しても、 multi_set既存の要素を指すイテレータが無効にならないという重要なプロパティがあります。a から要素を消去して multi_setも、消去される要素を実際に指している反復子を除いて、反復子は無効になりません。

- SGI のドキュメントから引用。

これは、 a のストレージがmulti_set線形ではないため、パフォーマンスが向上することを意味します。

于 2011-05-05T10:25:13.353 に答える