c++ - 寻找一个好的空间划分数据结构来快速生成数百万个原子键

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-trees，所以我真的不知道这个问题的最佳解决方案是什么。我敢肯定，那里可能有一些最适合这个的东西。

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

score 7 · Accepted Answer

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

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

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

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

另外，不要使用平方根来计算距离。改为以距离平方操作。这将节省大量的处理。

1 回答 1