寻找一个良好的空间划分数据结构,以快速生成数百万个原子键

Question

我正在进行一些涉及数百万个原子系统的MD模拟.

我写了一些代码来生成一个文件,它只是XYZ原子坐标列表.现在我需要在原子之间产生键.如果两个原子在彼此的一定距离内,则认为是一个键.

示例XYZ文件:

所以我有五个原子.如果我的距离阈值是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-tree,所以我真的不知道这个问题的最佳解决方案是什么.我敢肯定,那里可能有一些最适合这种情况的东西.

我还应该提到我的模拟框是周期性的,这意味着(0.5,0,0)处的原子将与(boxWidth - 0.5,0,0)处的原子结合,距离阈值如2.

Answer 1

简单的解决方案是第一个尝试.它们编码速度快,易于测试.如果这不能提供所需的性能,那么你可以尝试一些比较棘手的东西.

因此,您可以通过为原子指定网格坐标来严格修剪搜索空间.没什么技术性的.就像一个穷人的八角树......

您需要做的就是网格大小为2,并搜索本地网格和每个相邻网格中的所有原子.网格显然是3D.原子的网格位置并不比将每个坐标除以网格大小更复杂.

显然,你做了一个初步的传递,并创建属于每个单元格的原子列表(或矢量).您可以将列表存储在map由3D网格坐标索引的位置.然后对于每个原子,您可以只查找本地列表并进行键合测试.

另外,不要使用平方根作为距离.改为以距离平方运行.这样可以节省大量的处理负担.