0

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

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

它的工作原理是这样的：（伪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 距离的数组，没有冗余，然后在我最终需要它时引用该数组。但是，我对如何以可行的方式索引该数组持空白。哈希表可以做到这一点，但我认为对于一个似乎可以通过巧妙的索引方法解决的问题来说，它太复杂和太慢了。

编辑：这是一个植绒模拟。

4

1 回答 1

2

性能理念：a）如果可能的话，使用平方距离，以避免根计算 b）永远不要使用 pow 来表示常数，整数幂 - 而是使用 xd*xd

我会考虑改变你的算法 - O(n^4) 真的很糟糕。在处理物理中的相互作用时（对于 2d 场中的距离也是 O(n^4)），人们会实施 b-trees 等并忽略影响较小的粒子相互作用。但这将取决于“使用距离的更多代码......”的真正作用。

只是做了一些考虑：唯一距离的数量是 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]];
}
于 2013-03-18T00:18:47.310 回答