求遍历位图所有像素无重复的随机算法（Swift/类C语法均可）

嘿，我太懂你说的这种需求了！当年做分形渲染的时候，也折腾过好久才找到合适的方法——你要的就是那种无重复、视觉上随机遍历所有像素的算法，既能避免逐行渲染的生硬感，又不用提前把所有索引都打乱（省内存），对吧？

下面给你两种适配Swift开发的方案，附伪代码/类C实现，刚好对应不同规模的像素列表：

方案1：在线Fisher-Yates洗牌（适合中等规模像素集合） #

如果你的像素列表是常规分辨率（比如1080P、2K），可以用这种“边遍历边洗牌”的方式，不用提前存储所有打乱后的索引，内存开销极小。核心思路是维护一个待选索引的映射，每次随机选出一个未访问的索引，然后用最后一个未访问的索引填充它的位置，避免数组移动。

Swift 实现示例 #

class PixelRandomIterator {
    private var remainingIndices: [Int]
    private let count: Int
    
    init(totalPixels: Int) {
        self.count = totalPixels
        self.remainingIndices = Array(0..<totalPixels)
    }
    
    func nextPixelIndex() -> Int? {
        guard !remainingIndices.isEmpty else { return nil }
        
        // 随机选一个未访问的索引位置
        let randomPos = Int.random(in: 0..<remainingIndices.count)
        let selectedIndex = remainingIndices[randomPos]
        
        // 用最后一个元素填充被选中的位置，减少数组操作开销
        remainingIndices[randomPos] = remainingIndices.last!
        remainingIndices.removeLast()
        
        return selectedIndex
    }
}

// 使用方式
let iterator = PixelRandomIterator(totalPixels: 1920*1080)
while let index = iterator.nextPixelIndex() {
    let x = index % 1920
    let y = index / 1920
    // 渲染(x,y)位置的像素
}

类C伪代码 #

typedef struct {
    int* remainingIndices;
    int count;
} PixelIterator;

PixelIterator* createPixelIterator(int totalPixels) {
    PixelIterator* iter = malloc(sizeof(PixelIterator));
    iter->count = totalPixels;
    iter->remainingIndices = malloc(totalPixels * sizeof(int));
    for (int i = 0; i < totalPixels; i++) {
        iter->remainingIndices[i] = i;
    }
    return iter;
}

int nextPixelIndex(PixelIterator* iter) {
    if (iter->count == 0) return -1;
    
    int randomPos = rand() % iter->count;
    int selectedIndex = iter->remainingIndices[randomPos];
    
    // 替换并减少计数
    iter->remainingIndices[randomPos] = iter->remainingIndices[iter->count - 1];
    iter->count--;
    
    return selectedIndex;
}

// 使用示例
PixelIterator* iter = createPixelIterator(1920*1080);
int index;
while ((index = nextPixelIndex(iter)) != -1) {
    int x = index % 1920;
    int y = index / 1920;
    // render pixel at (x,y)
}

方案2：线性同余生成器（LCG）完美遍历（适合超大规模像素集合） #

如果是4K、8K甚至更大的像素画布，上面的方案内存开销会有点高（要存所有索引）——这时候LCG就是你的救星！它能生成一个周期等于像素总数的伪随机序列，只要参数选得对，就能保证每个索引只出现一次，而且视觉上完全是随机跳跃的，和你当年在Java Applet分形里用的应该是同一种思路。

核心是选择合适的LCG参数：

• 模数m：等于像素总数（最好是2的幂，比如width*height是2^n，参数更容易选）
• 乘数a：满足a ≡ 1 mod 4（如果m是2的幂），且a和m互质
• 增量c：必须是奇数，且和m互质

Swift 实现示例 #

class LCGPixelIterator {
    private let m: Int // 像素总数
    private let a: Int // 乘数
    private let c: Int // 增量
    private var current: Int
    
    init(width: Int, height: Int) {
        self.m = width * height
        // 针对2的幂模数的最优参数（保证周期为m）
        self.a = 1664525
        self.c = 1013904223
        self.current = Int.random(in: 0..<m) // 随机起始点
    }
    
    func nextPixelIndex() -> Int? {
        let result = current
        // 计算下一个索引：current = (a*current + c) mod m
        current = (a &* current &+ c) % m
        // 避免重复遍历（当回到起始点时停止）
        return result == current - 1 ? nil : result
    }
}

// 使用方式
let iterator = LCGPixelIterator(width: 3840, height: 2160)
while let index = iterator.nextPixelIndex() {
    let x = index % 3840
    let y = index / 3840
    // 渲染(x,y)位置的像素
}

类C伪代码 #

typedef struct {
    int m;
    long long a;
    long long c;
    long long current;
} LCGIterator;

LCGIterator* createLCGIterator(int width, int height) {
    LCGIterator* iter = malloc(sizeof(LCGIterator));
    iter->m = width * height;
    iter->a = 1664525LL;
    iter->c = 1013904223LL;
    iter->current = rand() % iter->m; // 随机起始点
    return iter;
}

int nextLCGPixelIndex(LCGIterator* iter) {
    static long long start = -1;
    if (start == -1) start = iter->current;
    
    int result = (int)iter->current;
    // 计算下一个值，用long long避免溢出
    iter->current = (iter->a * iter->current + iter->c) % iter->m;
    
    // 当回到起始点时，停止遍历
    if (iter->current == start) {
        return -1;
    }
    return result;
}

// 使用示例
LCGIterator* iter = createLCGIterator(3840, 2160);
int index;
while ((index = nextLCGPixelIndex(iter)) != -1) {
    int x = index % 3840;
    int y = index / 3840;
    // render pixel at (x,y)
}

为什么选LCG？ #

它的内存开销是O(1)，完全不用存储索引数组，而且生成的序列视觉上非常“随机”，不会有逐行或空间填充曲线的连续块感，完美适配分形这类需要渐进式随机渲染的场景。

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