Использование поиска соседей и симметрии для производительности во время выполнения?

Question

Предположим, у меня есть набор 3D точек {x[i], i=1,...,n} и

У меня есть массив A, каждую запись A[i] массива соответствует некоторому измерению точки x[i]. Если две точки x[i] и x[j] находятся в фиксированном расстоянии d друг от друга, то мы добавим постоянную f(x[i],x[j]), вычисленный функцией f, чтобы оба их записей A[i] и A[j] в массиве.

Прямой способ вычисления записи массива A является (в псевдокоде)

for i = 1,...,n 
    A[i] = 0 

for i = 1,...,n 
    for j = i,...,n 
     if dist(x[i],x[j]) < d 
      tmp = f(x[i],x[j]) 
      A[i]+= tmp 
      A[j]+= tmp 

Если я также иметь функцию find_nb(x[i]), которая принимает точку x[i] в качестве аргумента и возвращает набор точек в пределах фиксированное расстояние d от x[i], включая точку x[i], и число из них, интересно, как эта функция может помочь улучшить производительность времени выполнения (например, время и/или пробел) вышеуказанного алгоритма?

После так я подумал:

for i = 1,...,n 
    A[i] = 0 

for i = 1,...,n 
    (nbs, num) = find_nb(x[i]) 
    for j = 1,...,num 
     A[i]+=f(x[i],x[nbs[j]]) 

Но это не делает использование симметрии между любыми двумя точками, то есть мы должны вычислить f(x[i],x[nbs[j]]) дважды, для A[i] и A[nbs[j]]. Это пустая трата. Так это можно улучшить?

Спасибо!

Answer 1

Во-первых, в вашем коде есть ошибка: когда i = j, вы добавляете tmp дважды, как к [i], так и к [j], которые являются одним и тем же элементом массива.

Совершенно очевидно, что функция не возвращает набор точек, а множество индексов точек, поэтому улучшение довольно просто:

for i = 1,...,n 
    (nbs, num) = find_nb(x[i]) 
    for k = 1,...,num 
     j = nbs [k] 
     if (j >= i) 
      tmp = f (x [i], x [j]) 
      A[i]+=tmp 
      if (j != i) 
       a [j] += tmp