1

一意の要素のインデックスを見つけるために、並べ替えられていない構造体のベクトルを何度も検索するプログラムを作成しました。この検索は for ループの反復ごとに複数回行われ、ベクトル内のデータは for ループの反復中に複数回変更されます (データは追加されるだけで、何も削除されません)。これで、プログラムはやりたいことを実行しますが、かなり遅いので、VS2012 にプログラムのパフォーマンスを分析させたところ、80% 以上の時間でプログラムがソートされていないベクトルを検索していることがわかりました。検索を最適化したい。O(n) はソートされていないベクトルであるため (すべての要素は一意であり、挿入された要素の順序は変更できません)、取得できる最善の方法はわかっていますが、何らかの方法でランタイムを短縮したいと考えています。

プログラムの実行時間を短縮するために並列処理を使用することを考えていましたが、Microsoft の AMP ライブラリが有望に見えます。一見すると、並列処理を使用して配列を反復処理し、配列内の要素を見つけることができます。しかし、ソートされていないベクター内のデータは大きく変化するため、ボトルネックをベクターの反復処理から CPU から GPU へのデータ転送に移動させたり、これに対処するために AMP 組み込みの最適化を行ったりしないのでしょうか? 覚えておいてください: ベクトル内のデータはベクトルの最後に追加されるだけで、何も削除されません。

念のため、私が使用するベクトルと検索関数を次に示します。

struct VertexData
{
    VertexData( unsigned int pos, unsigned int norm, unsigned int tex )
        : posIdx(pos), normIdx(norm), texIdx(tex) {}

    unsigned int posIdx;
    unsigned int normIdx;
    unsigned int texIdx;

    inline bool operator<( const VertexData &rhs ) const
    {
        return std::tie(posIdx, normIdx, texIdx) < std::tie(rhs.posIdx, rhs.normIdx, rhs.texIdx);
    }

    inline bool operator==( const VertexData &rhs ) const
    {
        return std::tie(posIdx, normIdx, texIdx) == std::tie(rhs.posIdx, rhs.normIdx, rhs.texIdx);
    }
};

std::vector<VertexData> verts;

int findIndex( const std::vector<VertexData> &vec, const VertexData &val ) const
{
    std::vector<VertexData>::const_iterator it;
    int idx = 0;
    for ( it = vec.begin(); it != vec.end(); ++it, ++idx )
        if ( *it == val )
            return idx;

    return -1;
}
4

1 に答える 1

2

並べ替えられた一意のインデックス セットを並べ替えられていないベクトルに保持するために、boost::multi-index 配列のようなものを使用できますか? そうすれば、毎回余分な作業を避けることができます。

原則として、アルゴリズムによる修正は常に力ずくよりも優れています。

于 2013-08-18T21:44:50.313 に答える