C语言像素半径数组随机选择代码的优化问询

首先，咱们先聊聊你当前代码里的几个核心性能瓶颈——这也是为什么修改版只改循环方向没提速的根本原因：

• 重复遍历整个数组收集索引：每个半径值r都要完整遍历一次pix_r来收集对应的索引，直接导致时间复杂度飙升到O(maxRad * numEl)，当图像尺寸较大（比如128*512=65536元素）时，这个开销会非常惊人。
• 低效的不重复随机数生成：用do-while循环反复生成随机数并检查是否重复，当NumberOfRandomS接近该半径的元素数量时，冲突概率急剧上升，循环次数会爆炸式增长。
• 双重循环检查保留标记：对每个半径的元素，都要遍历NumberOfRandomS次来判断是否保留，又是一层O(lenShellR * NumberOfRandomS)的冗余开销。
• 内存泄漏风险：代码里malloc的RandomIndex、numPerShell1、currentR都没有对应free，长期调用会导致内存耗尽。

接下来是优化后的完整代码，彻底解决了这些问题：

#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <string.h>

const int NumberOfRandomS = 5;

// 注意：请在调用此函数前调用一次srand(time(NULL))，避免每次调用重置随机种子
void OptimizedRandomSelected(size_t numEl, int maxRad, int *pix_r) {
    // 第一步：预处理每个半径对应的所有索引，仅遍历原数组两次
    // 先统计每个半径的元素数量
    int *numPerShell = malloc(maxRad * sizeof(int));
    if (!numPerShell) {
        fprintf(stderr, "Memory allocation failed for numPerShell\n");
        return;
    }
    memset(numPerShell, 0, maxRad * sizeof(int));
    for (size_t i = 0; i < numEl; ++i) {
        int r = pix_r[i];
        if (r >= 0 && r < maxRad) { // 确保半径值合法，避免越界
            numPerShell[r]++;
        }
    }

    // 为每个半径分配索引数组
    int **shellIndexes = malloc(maxRad * sizeof(int*));
    if (!shellIndexes) {
        fprintf(stderr, "Memory allocation failed for shellIndexes\n");
        free(numPerShell);
        return;
    }
    memset(shellIndexes, 0, maxRad * sizeof(int*));
    for (int r = 0; r < maxRad; ++r) {
        if (numPerShell[r] > 0) {
            shellIndexes[r] = malloc(numPerShell[r] * sizeof(int));
            if (!shellIndexes[r]) {
                fprintf(stderr, "Memory allocation failed for shell %d\n", r);
                // 分配失败时释放已分配的内存
                for (int j = 0; j < r; ++j) {
                    free(shellIndexes[j]);
                }
                free(shellIndexes);
                free(numPerShell);
                return;
            }
        }
    }

    // 填充每个半径的索引数组（仅遍历原数组一次）
    int *counts = malloc(maxRad * sizeof(int));
    if (!counts) {
        fprintf(stderr, "Memory allocation failed for counts\n");
        // 释放已分配内存
        for (int r = 0; r < maxRad; ++r) {
            free(shellIndexes[r]);
        }
        free(shellIndexes);
        free(numPerShell);
        return;
    }
    memset(counts, 0, maxRad * sizeof(int));
    for (size_t i = 0; i < numEl; ++i) {
        int r = pix_r[i];
        if (r >= 0 && r < maxRad && numPerShell[r] > 0) {
            shellIndexes[r][counts[r]++] = i;
        }
    }
    free(counts); // 用完即释放临时内存

    // 第二步：处理每个半径的随机选择
    for (int r = 0; r < maxRad; ++r) {
        int lenShellR = numPerShell[r];
        if (lenShellR <= NumberOfRandomS) {
            continue; // 元素数量不足，全部保留
        }
        int *indexes = shellIndexes[r];
        if (!indexes) continue;

        // 使用Fisher-Yates洗牌变种，高效生成不重复随机索引
        for (int i = 0; i < NumberOfRandomS; ++i) {
            // 从i到末尾随机选一个元素
            size_t randIdx = i + rand() % (lenShellR - i);
            // 交换当前i位置和随机选中的位置
            int temp = indexes[i];
            indexes[i] = indexes[randIdx];
            indexes[randIdx] = temp;
        }

        // 第三步：批量设置值，避免双重循环检查
        // 先把该半径的所有元素设为-1
        for (int i = 0; i < lenShellR; ++i) {
            pix_r[indexes[i]] = -1;
        }
        // 再把选中的几个恢复原值
        for (int i = 0; i < NumberOfRandomS; ++i) {
            pix_r[indexes[i]] = r;
        }
    }

    // 释放所有分配的内存，避免泄漏
    for (int r = 0; r < maxRad; ++r) {
        free(shellIndexes[r]);
    }
    free(shellIndexes);
    free(numPerShell);
}

关键改进点说明： #

1. 一次性遍历收集索引：仅遍历原数组pix_r两次（一次统计数量，一次填充索引），时间复杂度降到O(numEl + maxRad)，这是最大的性能提升点，尤其是当maxRad远小于numEl时效果显著。

2. 高效生成不重复随机数：用Fisher-Yates洗牌算法的变种，不需要重复检查随机数是否重复，时间复杂度为O(NumberOfRandomS)，比原来的do-while循环高效得多，尤其是当NumberOfRandomS较大时。

3. 简化保留标记逻辑：先把该半径的所有元素设为-1，再把选中的几个恢复原值，避免了原来的双重循环检查，把这部分的时间复杂度从O(lenShellR * NumberOfRandomS)降到O(lenShellR + NumberOfRandomS)。

4. 完善内存管理：所有malloc的内存都对应了free，并且添加了内存分配失败的错误处理，避免内存泄漏和程序崩溃。

5. 随机种子优化：把srand(time(NULL))移到函数外部，避免每次调用函数都重置随机种子，导致短时间内多次调用时生成的随机数序列重复。

额外小建议： #

• 如果maxRad的值很大或内存紧张，可以考虑用链表存储每个半径的索引，但数组的访问速度更快，内存允许时优先用数组。
• 可以把NumberOfRandomS改成函数参数，让函数更灵活。
• 持续对pix_r的半径值做合法性检查，避免数组越界访问。

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