爲什麼我的空間散列速度很慢？

爲什麼我的空間散列速度太慢？我正在研究一個使用光滑粒子流體動力學來模擬山體滑坡運動的代碼。在光滑的粒子流體動力學中，每個粒子都會影響3「平滑長度」範圍內的粒子。我試圖實現一個空間散列函數，以便快速查看相鄰的粒子。爲什麼我的空間散列速度很慢？

對於我的實現，我使用了stl中的「set」數據類型。在每個時間步驟，使用下面的函數將粒子散列到它們的桶中。「桶」是集合的向量，每個網格單元有一個集合（空間域是有限的）。每個粒子由一個整數標識。

要查找衝突功能下面題爲「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 
    } 
}

非常感謝！

來源

2013-12-20 user3100953

這些組合有多大？ 'boost :: flat_set'可能會更快，如果他們很小 –

感謝您的建議！集合是100-1500整數。我會試一試flat_set。 – user3100953

這比我期待的要大得多。那麼，給它一個鏡頭，不要忘記「保留」。 –

由於反覆創建和填充所有這些集合導致大量stl堆分配，您的性能正在被活着吃掉。如果您對代碼進行了剖析（例如使用像Sleepy這樣的快速簡單的非儀表工具），我確信您會發現這種情況。你正在使用Sets來避免讓一個給定的粒子不止一次添加到一個桶中 - 我明白了。如果Duck的建議沒有給你你需要的東西，我想你可以通過使用預先分配的數組或向量來顯着提高性能，並通過向添加項目時設置的粒子添加「添加」標誌來獲得這些容器的唯一性。然後只需在添加之前檢查該標誌，並確保在下一個循環之前清除標誌。（如果粒子的數量是恆定的，可以通過專用於存儲標誌的預分配陣列，然後在幀結束時將memsetting設置爲0來非常有效地執行此操作。）

這就是基本思想。如果你決定走這條路，並在某個地方卡住，我會幫你解決細節問題。

來源

2013-12-20 04:44:27 MikeD

是的，你是100％正確的。我在代碼上運行了一個分析器，這正是瓶頸所在。我轉而使用矢量，並且性能顯着提高。非常感謝你！ – user3100953

很高興爲你工作:) – MikeD

爲什麼我的空間散列速度很慢？

回答

相關問題