2

空間ハッシュが非常に遅いのはなぜですか? 滑らかな粒子の流体力学を使用して地滑りの動きをモデル化するコードに取り組んでいます。滑らかな粒子の流体力学では、各粒子は 3 つの「平滑化長さ」の距離内にある粒子に影響を与えます。隣接する粒子をすばやく検索するために、空間ハッシュ関数を実装しようとしています。

私の実装では、stl の「set」データ型を使用しました。各時間ステップで、粒子は以下の関数を使用してバケットにハッシュされます。「bucket」はセットのベクトルで、グリッド セルごとに 1 つのセットがあります (空間ドメインは制限されています)。各粒子は整数で識別されます。

衝突を探すために、以下の「getSurroundingParticles」という名前の関数が使用されます。この関数は整数 (粒子に対応) を取り、粒子のサポート長の 3 倍以内にあるすべてのグリッド セルを含むセットを返します。

問題は、この実装が非常に遅く、粒子の数が 2000 の場合、各粒子を他のすべての粒子に対してチェックするよりも遅いことです。

//put each particle into its bucket(s)
void hashParticles()
{
    int grid_cell0;

    cellsWithParticles.clear();

    for(int i = 0; i<N; i++)
    {
        //determine the four grid cells that surround the particle, as well as the grid cell that the particle occupies
        //using the hash function int grid_cell = ( floor(x/cell size) ) + ( floor(y/cell size) )*width
        grid_cell0 = ( floor( (Xnew[i])/cell_spacing) ) + ( floor(Ynew[i]/cell_spacing) )*cell_width;

        //keep track of cells with particles, cellsWithParticles is an unordered set so duplicates will automatically be deleted
        cellsWithParticles.insert(grid_cell0);


        //since each of the hash buckets is an unordered set any duplicates will be deleted
        buckets[grid_cell0].insert(i); 

    }
}

set<int> getSurroundingParticles(int particleOfInterest)
{
     set<int> surroundingParticles;
     int numSurrounding;
     float divisor = (support_length/cell_spacing);
     numSurrounding = ceil( divisor );
     int grid_cell;

     for(int i = -numSurrounding; i <= numSurrounding; i++)
     {
         for(int j = -numSurrounding; j <= numSurrounding; j++)
         {
             grid_cell = (int)( floor( ((Xnew[particleOfInterest])+j*cell_spacing)/cell_spacing) ) + ( floor((Ynew[particleOfInterest]+i*cell_spacing)/cell_spacing) )*cell_width;
             surroundingParticles.insert(buckets[grid_cell].begin(),buckets[grid_cell].end());
         }
     }
    return surroundingParticles;
}

getSurroundingParticles を呼び出すように見えるコード:

set<int> nearbyParticles;
//for each bucket with particles in it
for ( int i = 0; i < N; i++ )
 {
     nearbyParticles = getSurroundingParticles(i);
    //for each particle in the bucket

    for ( std::set<int>::iterator ipoint = nearbyParticles.begin(); ipoint != nearbyParticles.end(); ++ipoint )
    {
        //do stuff to check if the smaller subset of particles collide
    }
}

どうもありがとう！

4

1 に答える 1

3

これらすべてのセットを繰り返し作成および設定することによって引き起こされる stl ヒープ割り当ての膨大な量によって、パフォーマンスが損なわれています。コードをプロファイリングした場合 (たとえば、Sleepy のような迅速で簡単な非計測ツールを使用して)、それが事実であることがわかると確信しています。セットを使用して、特定のパーティクルがバケットに複数回追加されるのを回避しています-わかりました。ダックの提案で必要なものが得られない場合は、事前に割り当てられた配列またはベクトルを使用し、アイテムが追加されたときに設定されるパーティクルに「追加された」フラグを追加することで、これらのコンテナーの一意性を取得することで、パフォーマンスを劇的に改善できると思います. 次に、追加する前にそのフラグを確認し、次のサイクルの前に必ずフラグをクリアしてください。(粒子数が一定の場合、

それが基本的な考え方です。もしあなたがこの道を行くことに決めて、どこかで行き詰まってしまったら、私はあなたが詳細を解決するのを手伝います.

于 2013-12-20T04:44:27.657 に答える