如何高效随机遍历二维数组中初始State为foo的元素？

针对性能问题，这里给出几个更高效的实现思路，核心是避免原方案中频繁删除vector元素带来的O(n²)开销：

方案一：Fisher-Yates洗牌（推荐） #

这是最直接的优化方式，先收集所有初始foo单元格的坐标，再原地打乱整个列表，最后按顺序遍历即可。洗牌操作是线性时间，遍历也是线性时间，整体复杂度O(n)，远低于原方案的O(n²)。

代码示例 #

#include <vector>
#include <random>
#include <algorithm>

// 定义坐标结构体存储单元格位置
struct Coord {
    int x;
    int y;
};

void processTimeStep(Cell field[57][57]) {
    std::vector<Coord> initialFooCells;

    // 第一步：收集当前时间步初始状态为foo的所有单元格坐标
    for (int i = 0; i < 57; ++i) {
        for (int j = 0; j < 57; ++j) {
            if (field[i][j].state == foo) {
                initialFooCells.push_back({i, j});
            }
        }
    }

    // 用Fisher-Yates算法原地打乱列表（std::shuffle内部实现就是该算法）
    std::random_device rd;
    std::mt19937 rng(rd());
    std::shuffle(initialFooCells.begin(), initialFooCells.end(), rng);

    // 遍历打乱后的列表执行操作
    for (const auto& coord : initialFooCells) {
        // 在这里编写你的单元格处理逻辑
        // 例如：field[coord.x][coord.y].temperature += 0.5f;
        // 注意：处理中新增的foo单元格不会被加入当前遍历，符合需求
    }
}

优势 #

• 无元素删除操作，避免了vector元素移动的额外开销
• 洗牌和遍历的时间复杂度都是O(n)，性能最优
• 代码简洁，依赖标准库实现，稳定性高

方案二：随机索引+标记已处理 #

如果需要保留初始foo单元格列表的顺序，可以用随机索引访问，同时标记已处理的元素，直到所有元素都被处理。

代码示例 #

#include <vector>
#include <random>

struct Coord {
    int x;
    int y;
};

void processTimeStepAlt(Cell field[57][57]) {
    std::vector<Coord> initialFooCells;
    for (int i = 0; i < 57; ++i) {
        for (int j = 0; j < 57; ++j) {
            if (field[i][j].state == foo) {
                initialFooCells.push_back({i, j});
            }
        }
    }

    int total = initialFooCells.size();
    std::vector<bool> processed(total, false);
    std::random_device rd;
    std::mt19937 rng(rd());
    std::uniform_int_distribution<> idxDist(0, total - 1);

    int remaining = total;
    while (remaining > 0) {
        int idx = idxDist(rng);
        if (!processed[idx]) {
            processed[idx] = true;
            remaining--;
            const auto& coord = initialFooCells[idx];
            // 执行单元格处理操作
        }
    }
}

优势 #

• 不修改原列表的顺序，适合需要保留初始foo单元格原始顺序的场景
• 实现逻辑直观，容易理解

补充说明 #

• 对于57x57的数组（共3249个元素），即使原方案也不会有特别大的性能问题，但如果后续数组维度扩大（比如到几百x几百），Fisher-Yates洗牌的性能优势会非常显著
• 使用std::mt19937随机数生成器比传统的rand()质量更高，能避免随机分布不均的问题
• 每个时间步必须重新收集初始foo单元格，确保只处理当前时间步开始时处于foo状态的单元格

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