如何减少双层循环的迭代次数——圆集合圆心包含关系处理的性能优化问询

哥们，你这个问题太典型了——n=1e4时O(n²)的复杂度直接干到1亿次循环，再加上每次都算sqrt和pow这种耗时的浮点操作，慢是必然的。我之前做过类似的空间查询优化，给你几个实用的方向，从易到难，总能解决你的问题：

这部分不用改整体逻辑，就能立竿见影提升速度：

• 去掉sqrt和pow：比较c[i].r > 两点距离等价于c[i].r² > 两点距离平方，完全可以把pow换成乘法，同时省去sqrt——这俩都是浮点运算里的大户，省下来的时间非常可观。
• 预处理半径平方：提前把每个圆的半径平方算好存在结构体里，不用每次循环都重复计算。

改完之后内层循环的判断逻辑变成这样：

double dx = c[i].x - c[j].x;
double dy = c[i].y - c[j].y;
if (c[i].r_sq > dx*dx + dy*dy) {
    // 处理操作
}

光这一步就能把单次循环的耗时砍一半以上。

上面的小优化只是减少单次循环的时间，但总迭代次数还是1亿次，要本质提升得从减少遍历次数入手。这里推荐两个性价比最高的方案：

网格划分（Grid Partitioning） #

思路非常简单：把整个坐标空间切成一个个大小合适的网格，每个网格里存落在这个区域的圆的索引。然后对每个圆i，只需要检查它所在网格和周围相邻的几个网格里的圆——毕竟只有这些网格里的圆心才有可能在i的内部。

网格的大小建议设为所有圆里的最大半径，这样能保证任何可能被i包含的圆心，一定在i所在网格或相邻的8个网格里。

我给你写了个简化的实现示例（已经包含预处理和网格逻辑）：

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <float.h>

typedef struct Points {
    double x;
    double y;
    double r;
    double r_sq; // 预处理半径平方
} Points;

// 网格节点，存储该网格内的圆索引列表
typedef struct GridNode {
    int* indices;
    int count;
    int capacity;
} GridNode;

int main() {
    int num = 10000;
    Points* c = malloc(num * sizeof(Points));
    if (!c) { perror("malloc failed"); return 1; }

    // 假设这里已经完成所有圆的x/y/r初始化
    // 预处理：计算半径平方，同时找坐标范围和最大半径
    double max_r = 0.0;
    double min_x = DBL_MAX, max_x = -DBL_MAX;
    double min_y = DBL_MAX, max_y = -DBL_MAX;
    for (int i = 0; i < num; i++) {
        c[i].r_sq = c[i].r * c[i].r;
        if (c[i].r > max_r) max_r = c[i].r;
        if (c[i].x < min_x) min_x = c[i].x;
        if (c[i].x > max_x) max_x = c[i].x;
        if (c[i].y < min_y) min_y = c[i].y;
        if (c[i].y > max_y) max_y = c[i].y;
    }

    // 网格大小设为最大半径，确保覆盖所有可能的候选圆
    double grid_size = max_r;
    int grid_cols = ceil((max_x - min_x) / grid_size) + 1;
    int grid_rows = ceil((max_y - min_y) / grid_size) + 1;

    // 初始化网格
    GridNode* grid = malloc(grid_rows * grid_cols * sizeof(GridNode));
    if (!grid) { perror("malloc grid failed"); free(c); return 1; }
    for (int i = 0; i < grid_rows * grid_cols; i++) {
        grid[i].indices = NULL;
        grid[i].count = 0;
        grid[i].capacity = 0;
    }

    // 将圆分配到对应网格
    for (int i = 0; i < num; i++) {
        int col = floor((c[i].x - min_x) / grid_size);
        int row = floor((c[i].y - min_y) / grid_size);
        GridNode* node = &grid[row * grid_cols + col];
        // 动态扩容列表
        if (node->count >= node->capacity) {
            node->capacity = node->capacity == 0 ? 8 : node->capacity * 2;
            node->indices = realloc(node->indices, node->capacity * sizeof(int));
            if (!node->indices) {
                perror("realloc indices failed");
                // 简化内存清理，实际项目要处理更严谨
                free(c);
                for (int j = 0; j < grid_rows * grid_cols; j++) free(grid[j].indices);
                free(grid);
                return 1;
            }
        }
        node->indices[node->count++] = i;
    }

    // 处理每个圆，只遍历相邻网格的圆
    for (int i = 0; i < num; i++) {
        int col = floor((c[i].x - min_x) / grid_size);
        int row = floor((c[i].y - min_y) / grid_size);

        // 遍历当前网格+周围8个网格（边界判断越界）
        for (int dr = -1; dr <= 1; dr++) {
            for (int dc = -1; dc <= 1; dc++) {
                int curr_row = row + dr;
                int curr_col = col + dc;
                if (curr_row < 0 || curr_row >= grid_rows || curr_col <0 || curr_col >= grid_cols) continue;
                
                GridNode* node = &grid[curr_row * grid_cols + curr_col];
                for (int k = 0; k < node->count; k++) {
                    int j = node->indices[k];
                    double dx = c[i].x - c[j].x;
                    double dy = c[i].y - c[j].y;
                    double dist_sq = dx*dx + dy*dy;
                    if (c[i].r_sq > dist_sq) {
                        // 执行你的处理操作
                    }
                }
            }
        }
    }

    // 清理内存
    free(c);
    for (int i = 0; i < grid_rows * grid_cols; i++) free(grid[i].indices);
    free(grid);
    return 0;
}

这个实现里，每个圆只需要遍历周围最多9个网格里的圆，假设圆分布均匀的话，每个网格里的圆数量大概是num/(grid_rows*grid_cols)，总迭代次数会从1亿降到几万甚至几十万，速度提升几十到上百倍。

四叉树（Quadtree） #

如果你的圆分布非常不均匀（比如大部分圆集中在某一小块区域，其他地方很稀疏），网格划分的效率会打折扣，这时候可以用四叉树。它会递归地把空间分成四个象限，只在有圆的区域创建节点，查询的时候只遍历和当前圆范围重叠的节点。实现起来比网格复杂一点，但对稀疏分布的场景优化效果更好。

如果你的机器是多核CPU，还可以把外层循环并行化。比如用OpenMP，只需要在外层循环前加一行：

#pragma omp parallel for
for (int i = 0; i < num; i++) {
    // 原来的处理逻辑
}

前提是每个i的处理操作是独立的，不会有共享资源的竞争问题。这样可以直接把运行时间降到原来的1/4、1/8甚至更低，取决于你的CPU核心数。

最后说一句：如果遇到极端情况（比如所有圆的圆心都挤在同一个点），那任何空间索引的优化效果都有限，但这种场景在实际业务里非常少见，大部分情况下上面的优化方案都能解决你的性能问题。

内容的提问来源于stack exchange，提问作者Googlebot