代码之家 › 专栏 › 技术社区 › jakogut

我可以使用什么样的索引方法在没有冗余的情况下存储数组中X^2向量之间的距离?

redundancy distance indexing vector c

jakogut · 技术社区 · 13 年前

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

现在,它循环遍历一个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距离的数组,而不需要冗余,然后在我最终需要时引用该数组。然而,我对如何以可行的方式索引该数组一无所知。哈希表可以做到这一点,但我认为对于一个似乎可以通过巧妙的索引方法解决的问题来说,它太复杂和太慢了。

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

1 回复 | 直到 13 年前

Zacharias 13 年前

性能理念: a) 如果可能的话,使用平方距离,以避免计算根 b) 永远不要将pow用于常量整数幂,而是使用xd*xd

我会考虑改变你的算法-O(n^4)真的很糟糕。当处理物理学中的相互作用时(也就是二维场中距离的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]];
}