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

Question

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

我已经编写了一些代码来生成一个文件，该文件只是XYZ原子坐标的列表。 现在我需要在原子之间产生键。 如果两个原子彼此相距一定距离，则被认为是键。

示例 XYZ 文件：

1 0 0
2 0 0
7 0 0
10 0 0
9 0 0

所以我有五个原子。 如果我的距离阈值是 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）。

Answer 1

首先尝试简单的解决方案。 它们编码速度快，易于测试。 如果这不能为您提供所需的性能，那么您可以尝试一些更棘手的方法。

因此，您可以通过为原子分配网格坐标来认真修剪搜索空间。 没什么技术性的。 就像穷人的八叉树...

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

显然，您进行初步传递并创建属于每个单元格的原子列表（或向量）。 您可以将列表存储在由 3D 网格坐标编制索引的map中。 然后对于每个原子，您可以查找本地列表并进行键测试。

另外，不要使用平方根作为您的距离。 改为使用距离平方进行操作。 这将节省处理的桶负载。