В поисках хорошей структуры данных с пространственным разделением для быстрой генерации миллионов атомных связей из

Я выполняю некоторые МД симуляции с участием систем миллионов атомов.

Я написал некоторый код для генерации файла, который представляет собой просто список координат атома 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) будет связан с атомом в точке (boxWidth — 0,5, 0, 0) с пороговым расстоянием, например 2.