1

与えられた 3D メッシュがあり、同一の頂点を削除しようとしています。このために、頂点の座標と対応する法線を含む自己定義の構造体を使用しています。

    struct vertice
    {
        float p1,p2,p3,n1,n2,n3;

        bool operator == (const vertice& vert) const
        {
            return (p1 == vert.p1 && p2 == vert.p2 && p3 == vert.p3);
        }
    };

頂点をデータで満たした後、重複を削除するために unordered_set に追加されます。

    struct hashVertice
    {
        size_t operator () (const vertice& vert) const
        {
            return(7*vert.p1 + 13*vert.p2 + 11*vert.p3);
        }
    };

    std::unordered_set<vertice,hashVertice> verticesSet;

    vertice vert;

    while(i<(scene->mMeshes[0]->mNumVertices)){

            vert.p1 = (float)scene->mMeshes[0]->mVertices[i].x;
            vert.p2 = (float)scene->mMeshes[0]->mVertices[i].y;
            vert.p3 = (float)scene->mMeshes[0]->mVertices[i].z;

            vert.n1 = (float)scene->mMeshes[0]->mNormals[i].x;
            vert.n2 = (float)scene->mMeshes[0]->mNormals[i].y;
            vert.n3 = (float)scene->mMeshes[0]->mNormals[i].z;

            verticesSet.insert(vert);

            i = i+1;
    }

3.000.000 頂点のようなデータ量には遅すぎることがわかりました。プログラムを 15 分間実行した後でも、プログラムは終了しませんでした。見えないボトルネックはありますか、それともそのようなタスクに適した別のデータ構造はありますか?

4

3 に答える 3

6

verticesSet.insert(vert);ループから削除するとどうなりますか?

劇的に高速化する場合 (予想どおり)、ボトルネックはハッシュテーブルである の内部にありstd::unordered_set、ハッシュテーブルの主な潜在的なパフォーマンスの問題は、過度のハッシュ衝突がある場合です。

現在の実装ではp1、p2とp3がsmallの場合、個別のハッシュ コードの数は少なくなり (浮動小数点数を整数に「折りたたむ」ため)、多くの衝突が発生します。

上記の仮定が真であることが判明した場合、ハッシュ関数を別の方法で実装しようとします (たとえば、はるかに大きな係数で乗算します)。

それ以外は、他の人がすでに提案しているように、コードをプロファイリングします。

于 2013-07-10T09:15:58.363 に答える
1

浮動小数点のハッシュは難しい場合があります。特に、ハッシュ ルーチンはハッシュを浮動小数点値として計算し、それを符号なし整数型に変換します。頂点が小さい可能性がある場合、これには深刻な問題があり[0...1.0)ます。たとえば、すべての頂点が range 内にある場合、ハッシュ関数は 13 を超える値を返すことはありません。ハッシュコード。

浮動小数点をハッシュする通常の方法は、特殊なケースを最初にチェックして、バイナリ イメージをハッシュすることです。(0.0と-0.0 は異なるバイナリ イメージを持っていますが、同じものをハッシュする必要があります。また、 s をどうするかは未解決の問題ですNaN。)float通常は と同じサイズ intであり、次のことができるため、これは特に単純reinterpret_castです。

size_t
hash( float f )
{
    assert( /* not a NaN */ );
    return f == 0.0 ? 0.0 : reinterpret_cast( unsigned& )( f );
}

正式には、これは未定義の動作です。しかし、float と int が同じサイズで、unsigned にトラップ表現がない場合 (今日のほとんどの汎用マシンの場合)、これを間違えるコンパイラは意図的に鈍化しています。

次に、結合アルゴリズムを使用して 3 つの結果をマージします。使用するものは他のものと同じくらい優れています (この場合、それは優れた一般的なアルゴリズムではありません)。

いくつかのコメントはプロファイリングを主張していますが (これは一般的には良いアドバイスです)、300 万の値に 15 分かかる場合、問題は実際には貧弱なハッシュ関数である可能性があり、多くの衝突が発生します。 . それほどパフォーマンスが低下する原因は他にありません。また、 の内部実装に精通していない限りstd::unordered_set、通常のプロファイラーの出力からは多くの情報が得られないでしょう。一方、 にstd::unordered_setは や などの関数がbucket_countありbucket_size、ハッシュ関数の品質を分析できます。あなたの場合、unordered_set300 万のエントリで を作成できない場合、最初のステップは、はるかに小さいエントリを作成し、これらの関数を使用してハッシュ コードの品質を評価することです。

于 2013-07-10T09:14:25.183 に答える