algorithm - 利用邻居发现和对称性提高运行时性能？

假设我有一组3d点{x[i], i=1,...,n}，并且
我有一个数组，数组的每个条目对应于一个点的测量值如果两个点A和A[i]彼此之间在固定距离内，则我们将一些由函数x[i]计算的常数x[i]添加到它们在数组中的项x[j]和d中。
计算数组f(x[i],x[j])项的直接方法是（伪代码）

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

如果我还有一个函数f，它将一个点A[i]作为参数，并返回一组从点A[j]到固定距离A内的点，包括点find_nb(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]])

但它并没有利用每两点之间的对称性，也就是说，对于x[i]和d，我们必须计算两次x[i]。这是浪费。所以这能改进吗？
谢谢！

最佳答案

首先，您的代码中有一个bug：当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

关于algorithm - 利用邻居发现和对称性提高运行时性能？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/22898345/