提高 C 中嵌套循环的性能

Question

给出由 (x_i, y_i,r_i),表示球心i在点(x_i, y_i, 0) 在三维space中，它的半径是r_i，我想要计算所有 z_i 其中 z_i = max { z | (x_i,y_i, z)是任意球体上的一个点}。换句话说，z_i是球心上方的最高点 i 位于任何球体中。

我有两个数组

int **vs = (int **)malloc(num * sizeof(int *));
double **vh = (double **)malloc(num * sizeof(double *));
for (int i = 0; i < num; i++){
    vs[i] = (int *)malloc(2 * sizeof(int)); // x,y
    vh[i] = (double *)malloc(2 * sizeof(double)); r,z
}

objective是计算每个点的最大值z。因此，我们应该检查每个 x,y 点上是否有更大的球体。最初我们看到所有点都是 vh[i][1]=vh[i][0]，这意味着 z 是每个球体的 r。然后，我们检查这些 z 值是否在较大的球体内以最大化 z 值。

for (int i = 0; i < v; i++) {
    double a = vh[i][0] * vh[i][0]; // power of the radius of sphere #1

    for (int j = 0; j < v; j++) {
        if (vh[i][0] > vh[j][1]) { // check only if r of sphere #1 is larger than the current z of #2

            double b = a - (vs[j][0] - vs[i][0]) * (vs[j][0] - vs[i][0])
                         - (vs[j][1] - vs[i][1]) * (vs[j][1] - vs[i][1]);
            // calculating the maximum z value of sphere #2 crossing sphere #1 
            // (r of sphere #1)**2 = (z of x_j,y_j)**2 + (distance of two centers)**2

            if (b > vh[j][1] * vh[j][1]) {
                vh[j][1] = sqrt(b);// update the z value if it is larger than the current value
            }
        }
    }
}

它完美运行，但是当点数增加时嵌套循环非常慢。我正在寻找一种方法来加快这个过程。

阐明任务的插图

Answer 1

当你说

The objective is to calculate the maximum z for each point.

我理解你的意思是，对于每个球体的中心C，任何球体上位于C正上方（沿z轴）的所有点中的最大z坐标。这基本上是一个 O(n²) 问题——您无法采取任何措施来防止计算费用随球体数量的平方缩放。

但是您可以采取一些措施来降低缩放系数。这里有一些可能性：

使用真正的二维数组（==数组的数组）而不是指针数组。它更容易实现，更多 memory-efficient，并且对于参考位置更好：
```
int (*vs)[2] = malloc(num * sizeof(*vs));
double (*vh)[2] = malloc(num * sizeof(*h));
// no other allocations needed
```
或者，它可能有助于使用一组结构，每个球体一个，而不是两个二维数字数组。它肯定会使您的代码 更清晰 ，但它也可能通过改进引用的位置来帮助略微提高速度：
```
struct sphere {
    int x, y;
    double r, z;
};
struct sphere *spheres = malloc(num * sizeof(*spheres));
```
存储z²而不是z，至少在计算期间是这样。这将减少从 O(v²) 到 O(v) 的 somewhat-expensive sqrt 调用的次数，假设你在最后进行一次转换以进行转换所有结果到 zs，它也会为您节省 O(v²) 次乘法。（如果你不用 ever 从 z² 转换成 z 就可以逃脱。）
Pre-initialize 每个 vh[i][1] 值到球体 i 的半径（或者半径的平方，如果你也使用前一个选项），然后添加 j != i 到 inner-loop 周围的条件 body.
按半径降序排列球体可以帮助您更早地找到更大的临时 z 值，从而使内循环中的半径测试更有效地剔除不必要的计算。
您可能会通过只检查每个不同的对一次来获得一些改进。也就是说，对于每个无序对 i、j，您可以只计算一次 inter-center 距离，根据相对半径确定要检查可能更新的高度，然后从那里开始.所涉及的额外逻辑可能会或可能不会通过减少其他计算得到回报。

此外，如果您对足够大的输入执行此操作，那么您可能能够通过并行计算来减少消耗的时间。

请注意，顺便说一下，这条评论是不正确的：

            // (r of sphere #1)**2 = (r of sphere #2)**2 + (distance of two centers)**2

。但是，它也不是您所依赖的。你所依赖的是，如果球体 1 完全覆盖球体 2 的中心，那么它在球体 2 中心上方的高度 z 满足关系

r₁² = z² + d_{1, 2}²

。也就是说，您在评论中写 r of sphere #2 的地方，您的意思似乎是 z.

提高 C 中嵌套循环的性能

Improving the performance of nested loops in C

c

loops

math

geometry

trigonometry