私のシミュレーションに十分なアルゴリズムを見つけるためにいくつかアドバイスが必要です

Question

私はいくつかの粒子の粒子のMonte-Carlo simulationをやっています。私のコードにいくつかのボトルネックがありますが、主なものは私が試行したいくつかの中で、私はすべてのパーティクルプロパティを更新する必要があるということです。コードはC++で書かれており、現在はいくつかのループがあります。
1.すべてのパーティクルの古いプロパティを保存して新しいプロパティを更新するループ。
2.相互作用の2Dループ。
3.別の2次元相互作用ループ（最初のものと組み合わせることはできません）。
4.保存するループは、ステップを拒否するステップ/ループを受け入れます。

スワップを使用してステップ4を削除したいと考えていますが、その方法を見つけることができません。すべてのパーティクルは、propertiesとnextPropertiesまたはoldPropertiesという名前のいくつかの要素を持つクラスです。どのようにそれにアプローチしますか？

Answer 1

double bufferingのように聞こえます。基本的には、粒子オブジェクトの2つの配列—へのポインタを、例えばacceptedとtrialと呼びます。試行の初めに、acceptedアレイのパーティクルのプロパティをtrialのパーティクルのプロパティにコピーし、必要な変更を行います。試用が成功した場合は、ポインターをスワップするだけで、trialの配列はacceptedになり、逆も同様です。

また、のうちには費用のかかるアップデートが含まれているとします。もしそうなら、fast variable draggingやensemble updatingのようなテクニックに興味があるかもしれません。

Answer 2

ステップ＃2と＃3はO(N^2)になりますが、＃1と＃4はO(N)になるので、それらに焦点を当てる必要があります。

粒子の各ペアの間で計算を絶対に行う必要がある場合、あまりできることはありません。しかし、ほとんどの場合、特定の距離以上離れたパーティクルはお互いにほとんど影響を与えません。あるいは、最も近いkパーティクル（固定の場合はk）のみを処理する必要があります。この場合、オクトツリー（またはkdツリー、aabbツリーなど）は、ペアワイズ計算の数を減らすための最善の策です。

特に、重力計算の複雑さを軽減するために使用されるBarnes-Hutメソッドを調べるとよいでしょう。

Answer 3

私は主なボトルネックは、あなたの2Dインタラクションだと思います。 N^2のやりとりをしているのであれば、平均場近似、基本的にはセル内の計算領域の分割、各繰り返しの各セルの平均場の計算、そして同じ細胞内の粒子との相互作用、および周囲の細胞に対する平均場補正を含む。

Hereあなたはこの最適化に関する詳細を読むことができますし、それが