跨平台64位整数区间伪随机重排的高效实现问询

需求说明 #

给定[a,b]的64位无符号整数索引区间，需快速生成该区间所有索引的伪随机排列数组，要求：

• 结果跨所有C++实现平台一致
• 分布均匀、外观随机
• 可使用Intel oneTBB的共享内存并行提升性能

现有方案的缺陷 #

• 基于unordered_set的方案依赖平台特定哈希函数，无法保证跨平台一致性，且效率低下；并行版本tbb::concurrent_unordered_set生成的分布有序而非随机。
• 部分哈希变换方案（如排序、模运算映射）存在非随机分布、非双射问题；线性同余生成器（LCG）通常不满足双射要求。

核心实现要求 #

• 提供特定哈希函数，说明其高效、均匀分布的原因，并用于实现distributeIndices(from, to)函数
• 代码严格遵循C++标准，保证跨平台一致性
• 支持返回std::vector、tbb::concurrent_vector或uint64_t动态数组
• 适配数十亿级索引的大区间场景
• 提供完整C/C++代码实现

测试标准 #

使用GCC 11.3 -O3在8线程i7-3610QM笔记本上测试1亿级索引场景，优先选择性能最优的正确方案；若实现无需构建向量、直接按伪随机顺序迭代索引的方案（可通过索引直接计算对应伪随机值），则按迭代1亿索引的耗时评估。

现有参考方案的问题 #

olegarch的LCG洗牌方案 #

性能较好，但部分区间分布不均匀：

// LCG params from: https://nuclear.llnl.gov/CNP/rng/rngman/node4.html
std::vector<uint64_t> distributeIndices(uint64_t lo, uint64_t hi) {
    uint64_t size = hi - lo + 1;
    std::vector<uint64_t> vec(size);
    for(uint64_t i = 0; i < size; i++)
        vec[i] = i + lo;
    uint64_t rnd = size ^ 0xBabeCafeFeedDad;
    for(uint64_t i = 0; i < size; i++) {
        rnd = rnd * 2862933555777941757ULL + 3037000493;
        uint64_t j = rnd % size;
        uint64_t tmp = vec[i]; vec[i] = vec[j]; vec[j] = tmp;
    }
    return std::move(vec);
}

Severin Pappadeux的并行LCG排序方案 #

分布均匀但外观有序，不符合随机要求：

uint64_t m = 0xd1342543de82ef95ULL; // taken from https://arxiv.org/pdf/2001.05304.pdf
uint64_t c = 0x1ULL;
inline auto lcg(uint64_t xi) -> uint64_t { // as LCG as it gets
    return m*xi + c;
}
inline auto cmp_lcg(uint64_t a, uint64_t b) -> bool {
    return lcg(a) < lcg(b);
}
auto distributeIndices(uint64_t from, uint64_t to) -> std::vector<uint64_t> {
    uint64_t size = to - from + 1;
    std::vector<uint64_t> z(size);
    tbb::parallel_for(uint64_t(0), size, [&](uint64_t i) {
        z[i] = from + i;
    }); // instead of std::iota(z.begin(), z.end(), from);
    tbb::parallel_sort(z.begin(), z.end(), cmp_lcg); // instead of std::sort(z.begin(), z.end(), cmp_lcg);
    return z;
}

满足要求的实现方案 #

选择的哈希函数：64位双射MurmurHash3 #

我们使用双射型64位MurmurHash3作为核心变换，原因如下：

• 双射保证：通过精心选择的置换参数，确保每个输入值对应唯一输出值，避免冲突，实现区间内索引的全排列
• 均匀分布：MurmurHash3的设计确保了输出的雪崩效应，输入的微小变化会导致输出的大幅变化，保证分布均匀
• 高效计算：仅包含位运算和乘法，无分支，可被编译器高度优化，适合并行计算

实现方案1：生成排列数组（支持并行） #

该方案使用oneTBB并行计算每个索引的哈希值，再按哈希值排序得到伪随机排列，既保证分布均匀，又解决了LCG排序方案外观有序的问题。

#include <vector>
#include <tbb/parallel_for.h>
#include <tbb/parallel_sort.h>

// 双射型64位MurmurHash3变换，输入输出一一对应
inline uint64_t bijective_murmur3(uint64_t x) {
    x ^= x >> 33;
    x *= 0xff51afd7ed558ccdULL;
    x ^= x >> 33;
    x *= 0xc4ceb9fe1a85ec53ULL;
    x ^= x >> 33;
    return x;
}

// 自定义比较器：按索引的哈希值排序
struct HashCompare {
    bool operator()(uint64_t a, uint64_t b) const {
        return bijective_murmur3(a) < bijective_murmur3(b);
    }
};

std::vector<uint64_t> distributeIndices(uint64_t from, uint64_t to) {
    uint64_t size = to - from + 1;
    std::vector<uint64_t> result(size);

    // 并行填充原始索引
    tbb::parallel_for(uint64_t(0), size, [&](uint64_t i) {
        result[i] = from + i;
    });

    // 并行按哈希值排序，得到伪随机排列
    tbb::parallel_sort(result.begin(), result.end(), HashCompare());

    return result;
}

实现方案2：无内存迭代器（最优性能） #

该方案无需构建数组，直接通过迭代器按伪随机顺序生成索引，适合超大区间场景：

#include <iterator>

// 双射哈希变换同上
inline uint64_t bijective_murmur3(uint64_t x) {
    x ^= x >> 33;
    x *= 0xff51afd7ed558ccdULL;
    x ^= x >> 33;
    x *= 0xc4ceb9fe1a85ec53ULL;
    x ^= x >> 33;
    return x;
}

// 伪随机排列迭代器
class RandomPermutationIterator : public std::iterator<std::input_iterator_tag, uint64_t> {
private:
    uint64_t current_;
    uint64_t from_;
    uint64_t size_;
    uint64_t offset_hash_;

public:
    RandomPermutationIterator(uint64_t from, uint64_t to, uint64_t pos = 0)
        : current_(pos), from_(from), size_(to - from + 1) {
        // 计算区间偏移的哈希值，确保不同区间的排列不同
        offset_hash_ = bijective_murmur3(from_);
    }

    uint64_t operator*() const {
        // 对当前迭代位置做哈希变换，映射到区间内的索引
        uint64_t hashed_pos = bijective_murmur3(current_) ^ offset_hash_;
        return from_ + (hashed_pos % size_);
    }

    RandomPermutationIterator& operator++() {
        ++current_;
        return *this;
    }

    RandomPermutationIterator operator++(int) {
        RandomPermutationIterator tmp = *this;
        ++current_;
        return tmp;
    }

    bool operator==(const RandomPermutationIterator& other) const {
        return current_ == other.current_ && from_ == other.from_ && size_ == other.size_;
    }

    bool operator!=(const RandomPermutationIterator& other) const {
        return !(*this == other);
    }
};

// 生成迭代器范围
std::pair<RandomPermutationIterator, RandomPermutationIterator> makeRandomPermutationRange(uint64_t from, uint64_t to) {
    return {RandomPermutationIterator(from, to), RandomPermutationIterator(from, to, to - from + 1)};
}

方案说明 #

1. 双射哈希的正确性：bijective_murmur3是经过验证的双射函数，每个64位输入对应唯一64位输出，保证了排列的完整性
2. 跨平台一致性：所有运算均为标准C++位运算和无符号整数运算，无平台依赖
3. 性能优化：
   • 数组生成方案使用oneTBB并行填充和排序，在8线程平台上可获得接近线性的加速比
   • 迭代器方案无需内存分配，直接计算每个索引，适合数十亿级区间，迭代1亿索引的耗时仅为哈希计算的时间，远低于数组生成方案
4. 外观随机：哈希变换的雪崩效应确保了排列的随机性，避免了LCG排序方案的有序外观

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