2

为什么我的空间哈希这么慢？我正在编写一个使用平滑粒子流体动力学来模拟滑坡运动的代码。在光滑粒子流体动力学中，每个粒子都会影响 3 个“光滑长度”距离内的粒子。我正在尝试实现空间散列函数，以便快速查找相邻粒子。

对于我的实现，我使用了 stl 中的“set”数据类型。在每个时间步，使用下面的函数将粒子散列到它们的桶中。“bucket”是一个集合向量，每个网格单元有一个集合（空间域是有限的）。每个粒子由一个整数标识。

为了寻找碰撞，使用下面标题为“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

由于重复创建和填充所有这些 Set 导致的大量 stl 堆分配，您的性能正在被蚕食。如果您对代码进行了概要分析（比如使用像 Sleepy 这样的快速简单的非仪器工具），我敢肯定您会发现这种情况。您正在使用 Sets 来避免将给定的粒子多次添加到桶中 - 我明白了。如果 Duck 的建议没有给您所需的东西，我认为您可以通过使用预先分配的数组或向量来显着提高性能，并通过向添加项目时设置的粒子添加“添加”标志来获得这些容器中的唯一性. 然后在添加之前检查该标志，并确保在下一个循环之前清除标志。（如果粒子数不变，

这是基本的想法。如果你决定走这条路并在某个地方卡住了，我会帮你搞清楚细节。

于 2013-12-20T04:44:27.657 回答