为什么我的空间哈希这么慢？我正在编写一个代码，该代码使用光滑粒子流体动力学来模拟滑坡的运动。在光滑粒子流体力学中，每个粒子都会影响距离为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
}
}
非常感谢！
由于重复创建和填充所有这些集而导致的stl堆分配数量之多，使您的性能大打折扣。如果你对代码进行了分析(比如说用Sleepy这样快速简单的非工具化工具)，我相信你会发现情况确实如此。使用"集"可以避免将给定粒子多次添加到桶中——我明白了。如果Duck的建议不能满足您的需求，我认为您可以通过使用预分配的数组或向量来显著提高性能，并通过向添加项目时设置的粒子添加"已添加"标志来获得这些容器中的唯一性。然后在添加之前只需检查该标志，并确保在下一个周期之前清除这些标志。(如果粒子数是恒定的，那么使用一个专门用于存储标志的预分配阵列，然后在帧结束时将内存设置为0，就可以非常有效地做到这一点。)
这是基本的想法。如果你决定走这条路，却被困在某个地方，我会帮你解决细节。