c++ - から数百万の原子結合をすばやく生成するための優れた空間分割データ構造を探しています

Question

私は数百万の原子のシステムを含むいくつかのMDシミュレーションを実行しています。

XYZ原子座標のリストであるファイルを生成するためのコードをいくつか作成しました。次に、原子間に結合を生成する必要があります。2つの原子が互いに一定の距離内にある場合、それは結合と見なされます。

XYZファイルの例：

だから私は5つの原子を持っています。距離のしきい値が2単位の場合、債券のリストは次のようになります。

1 2
3 5
4 5

（ここで、番号はXYZファイルの座標のインデックスに対応します）。

このリストを生成するための素朴なアプローチは次のとおりです。

for i = 1:numAtoms
    for j = i+1:numAtoms
        if distance(atom[i], atom[j]) < 2
            bonds.push [i, j]

ただし、これはすぐにアルゴリズムの限界に達し、数百万の原子に対して高度に最適化されたCでも、少なくともこのプロセスを実行するのと同じくらい頻繁に遅くなります。

スペースパーティションデータ構造で私が経験したのは、フォトンマッパーを一度作成したときのkdツリーでの経験だけなので、この問題の最善の解決策が何であるかはわかりません。しかし、これに最適なものがおそらくそこにあると確信しています。

また、シミュレーションボックスは周期的です。つまり、（0.5、0、0）の原子は、2などの距離しきい値で（boxWidth --0.5、0、0）の原子に結合します。

score 7 · Accepted Answer

簡単な解決策が最初に試みられます。コーディングが速く、テストも簡単です。それでも必要なパフォーマンスが得られない場合は、もっと難しいことを試すことができます。

したがって、原子にグリッド座標を割り当てることで、検索スペースを真剣に整理することができます。技術的なことは何もありません。貧乏人の八分木のように...

グリッドサイズを2にして、ローカルグリッドと隣接する各グリッド内のすべての原子を検索するだけです。明らかに、グリッドは3Dです。原子のグリッド位置は、各座標をグリッドサイズで割るよりも複雑です。

明らかに、予備パスを実行して、各セルに属する原子のリスト（またはベクトル）を作成します。map3Dグリッド座標によってインデックス付けされたインデックスにリストを保存できます。次に、各原子について、ローカルリストを検索し、結合テストを実行できます。

また、距離に平方根を使用しないでください。代わりに、距離の2乗で操作してください。これにより、処理のバケット負荷が節約されます。

1 に答える 1