c -我可以使用什么样的索引方法来存储数组中X^2个向量之间的距离而没有冗余?

Question

我正在做一个需要大量向量数学的演示，在分析中，我发现它花费了最多的时间来寻找给定向量之间的距离。

现在，它循环遍历X^2个向量的数组，并找到每个向量之间的距离，这意味着它运行了X^4次距离函数，尽管(我认为)只有(X^2)/2个唯一的距离。

它的工作原理如下:(pseudo c)

#define MATRIX_WIDTH 8
typedef float vec2_t[2];
vec2_t matrix[MATRIX_WIDTH * MATRIX_WIDTH];
...
for(int i = 0; i < MATRIX_WIDTH; i++)
{
    for(int j = 0; j < MATRIX_WIDTH; j++)
    {
        float xd, yd;
        float distance;
        for(int k = 0; k < MATRIX_WIDTH; k++)
        {
            for(int l = 0; l < MATRIX_WIDTH; l++)
            {
                int index_a = (i * MATRIX_LENGTH) + j;
                int index_b = (k * MATRIX_LENGTH) + l;
                xd = matrix[index_a][0] - matrix[index_b][0];
                yd = matrix[index_a][1] - matrix[index_b][1];
                distance = sqrtf(powf(xd, 2) + powf(yd, 2));
            }
        }
        // More code that uses the distances between each vector
    }
}

我想做的是创建和填充(X^2)/2距离的数组没有冗余，然后引用该数组当我最终需要它。但是，对于如何以一种有效的方式索引这个数组，我还是一片空白。哈希表可以做到这一点，但我认为对于一个似乎可以通过聪明的索引方法解决的问题来说，它太复杂和太慢了。

编辑:这是一个群集模拟。

Answer 1

表现思路:A)尽可能用平方距离工作，避免根计算B)永远不要用pow表示常数、整数幂，而是用xd*xd

我会考虑改变你的算法- O(n^4)真的很糟糕。当处理物理中的相互作用时(对于2d场中的距离也是O(n^4))，人们会执行b树等并忽略具有低影响的粒子相互作用。但这取决于"更多使用距离的代码"到底是什么。

只是做了一些考虑:唯一距离的数量是0.5*n*n(+1)，其中n = w*h。如果您写下出现唯一距离的时间，您将看到两个内循环都可以减少，从i和j开始。

另外，如果你只需要通过矩阵索引访问这些距离，你可以建立一个4d距离矩阵。

如果内存有限，我们可以节省近50%，如上所述，使用查找函数访问三角形矩阵，如Code-Guru所说。我们可能会预先计算行索引，以避免在访问

时求和。

float distanceArray[(H*W+1)*H*W/2];
int lineIndices[H];
searchDistance(int i, int j)
{
    return i<j?distanceArray[i+lineIndices[j]]:distanceArray[j+lineIndices[i]];
}