如何在CPU单线程下快速生成0~N-1的随机排列（N≤12）

核心需求 #

在CPU单线程环境（可使用SIMD指令）下，以最快方式生成0到N-1的随机排列，其中N通常不超过12，且N!可容纳于32位有符号整数。

原C++实现代码 #

#include <random>
#include <cstdint>
#include <iostream>

static inline uint64_t rotl(const uint64_t x, int k) {
    return (x << k) | (x >> (64 - k));
}


static uint64_t s[2];

uint64_t Next(void) {
    const uint64_t s0 = s[0];
    uint64_t s1 = s[1];
    const uint64_t result = rotl(s0 + s1, 17) + s0;

    s1 ^= s0;
    s[0] = rotl(s0, 49) ^ s1 ^ (s1 << 21); // a, b
    s[1] = rotl(s1, 28); // c

    return result;
}

// Assume the array |dest| must have enough space for N items
void GenPerm(int* dest, const int N) {
    for(int i=0; i<N; i++) {
        dest[i] = i;
    }
    uint64_t random = Next();
    for(int i=0; i+1<N; i++) {
        const int ring = (N-i);
        // I hope the compiler optimizes acquisition
        // of the quotient and modulo for the same
        // dividend and divisor pair into a single
        // CPU instruction, at least in Java it does
        const int pos = random % ring + i;
        random /= ring;
        const int t = dest[pos];
        dest[pos] = dest[i];
        dest[i] = t;
    }
}

int main() {
    std::random_device rd;
    uint32_t* seed = reinterpret_cast<uint32_t*>(s);
    for(int i=0; i<4; i++) {
        seed[i] = rd();
    }
    int dest[20];
    for(int i=0; i<10; i++) {
        GenPerm(dest, 12);
        for(int j=0; j<12; j++) {
            std::cout << dest[j] << ' ';
        }
        std::cout << std::endl;
    }
    return 0;
}

原实现的性能瓶颈 #

原代码的核心性能问题在于模运算（%）和除法（/）的开销——即使编译器可能将同组的商和模合并为单指令，对于小N（≤12）来说，循环中的多次模/除法依然是主要耗时点。

已构思的优化思路 #

• 生成0到N!-1范围内的随机数，减少模运算与Next()调用次数，但缺乏将该数转换为排列的具体方法；
• 用乘法逆元替代除法，但会引入微小偏差，且不确定性能提升效果。

实际生产场景代码 #

该逻辑用于从分组数组中随机挑选空闲Item，代码如下：

struct Item {
    uint8_t is_free_; // 0 or 1
    // ... other members ...
};

Item* PickItem(const int time) {
    // hash-map lookup, non-empty arrays
    std::vector<std::vector<Item*>> &arrays = GetArrays(time);
    Item* busy = nullptr;
    for(int i=0; i<arrays.size(); i++) {
        uint64_t random = Next();
        for(int j=0; j+1<arrays[i].size(); j++) {
            const int ring = (arrays[i].size()-j);
            const int pos = random % ring + j;
            random /= ring;
            Item *cur = arrays[i][pos];
            if(cur->is_free_) {
                // Return a random free item from the first array
                // where there is at least one free item
                return cur;
            }
            arrays[i][pos] = arrays[i][j];
            arrays[i][j] = cur;
        }
        Item* cur = arrays[i][arrays[i].size()-1];
        if(cur->is_free_) {
            return cur;
        } else {
            // Return the busy item in the last array if no free
            // items are found
            busy = cur;
        }
    }
    return busy;
}

具体优化方案 #

方案一：预计算阶乘+Lehmer码转换（彻底减少模运算次数） #

因为N≤12，12! = 479001600，刚好能放进32位有符号整数，所以可以通过以下步骤优化：

1. 预计算阶乘表：提前算出0!到12!的32位整数，编译期常量可让编译器做极致优化；
2. 单次生成随机数：调用一次Next()后，取低32位并对N!取模（仅一次模运算），得到k ∈ [0, N!-1]；
3. Lehmer码转排列：将k分解为Lehmer码，再映射为排列——由于阶乘是编译期常量，编译器会自动将除法转换为乘法+移位，完全消除运行时除法开销。

示例代码片段：

// 预计算阶乘表（0!到12!）
constexpr uint32_t factorials[] = {
    1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600
};

void GenPermLehmer(int* dest, const int N) {
    // 初始化数组
    for(int i=0; i<N; i++) dest[i] = i;
    // 生成0~N!-1的随机数
    uint64_t rand_val = Next();
    uint32_t k = static_cast<uint32_t>(rand_val) % factorials[N];
    // Lehmer码转排列
    for(int i=0; i<N-1; i++) {
        uint32_t fact = factorials[N-1-i];
        // 编译器会将常量除法优化为乘法+移位
        uint32_t q = k / fact;
        k = k % fact;
        // 交换对应位置元素
        std::swap(dest[i], dest[i+q]);
    }
}

方案二：针对PickItem场景的定向优化 #

在实际场景中，我们不需要生成完整排列，找到第一个空闲Item即可返回，因此可以进一步优化：

1. 复用随机数：一次Next()生成的64位随机数足够覆盖多个小长度数组的需求，避免频繁调用随机数生成函数；
2. 提前终止逻辑：找到空闲Item后立即返回，跳过后续不必要的计算；
3. 减少无效交换：仅当选中的Item忙碌时才交换到前面，避免重复检查同一忙碌Item。

优化后的PickItem示例：

// 复用预计算的阶乘表
constexpr uint32_t factorials[] = {
    1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600
};

Item* PickItemOpt(const int time) {
    std::vector<std::vector<Item*>> &arrays = GetArrays(time);
    Item* busy = nullptr;
    uint64_t rand_cache = Next(); // 预生成随机数，按需拆分使用

    for(int i=0; i<arrays.size(); i++) {
        auto &vec = arrays[i];
        int m = vec.size();
        if(m == 0) continue;

        // 从缓存中提取对应范围的随机数
        uint32_t k = static_cast<uint32_t>(rand_cache) % factorials[m];
        rand_cache >>= 32;
        if(rand_cache == 0) rand_cache = Next();

        int current_pos = 0;
        int remaining = m;
        while(remaining > 1) {
            uint32_t fact = factorials[remaining-1];
            uint32_t q = k / fact;
            k = k % fact;

            int pick_pos = current_pos + q;
            Item* cur = vec[pick_pos];
            if(cur->is_free_) {
                return cur;
            }
            // 交换到前面，避免后续重复检查
            std::swap(vec[pick_pos], vec[current_pos]);
            current_pos++;
            remaining--;
        }

        // 检查最后一个元素
        Item* cur = vec[current_pos];
        if(cur->is_free_) {
            return cur;
        } else {
            busy = cur;
        }
    }
    return busy;
}

方案三：SIMD辅助优化（补充项） #

对于N≤12的小范围场景，可以用SIMD指令做辅助优化：

• 批量初始化：用AVX2的128位寄存器一次性加载0~N-1的序列，替代循环初始化；
• 批量检查空闲状态：将多个is_free_位打包到SIMD寄存器中，快速定位空闲Item的位置，再结合随机数选择。
  该方案收益相对有限，但在极端性能需求下可作为补充。

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