C++如何实现高效的数组元素随机采样(Sampling)

在C++里做随机采样，最稳妥的方案其实一句话就能说清：无放回用 std::shuffle 全局打乱后取前 k 个，别自己造 partial_shuffle（标准库里根本不存在）；如果 k 远小于 n，换 std::uniform_int_distribution 配合 std::unordered_set 做拒绝采样；有放回直接循环生成索引；加权采样必须用 std::discrete_distribution。下面拆开讲细节和坑。

用 std::shuffle 做无放回随机采样最稳妥

要从一个容器里等概率抽取 k 个不重复元素（比如从用户列表中选 5 个人做 A/B 测试），std::shuffle 加上 std::vector 截断是最直观也最不容易出错的做法。它底层用的是 Fisher–Yates 算法，时间复杂度 O(n)，标准库已经优化得相当好，比手写循环可靠得多。

一个常见的误解是“只打乱前 k 位”来省时间——有人会误以为标准库里有 partial_shuffle，但实际上 C++ 标准里根本没有这个函数。网上搜到的都是过时提案或者第三方实现，强行用会导致未定义行为。

实操建议：

• 容器必须支持随机访问（std::vector、原生数组都可以，std::list 不行）
• 用 std::shuffle(vec.begin(), vec.end(), rng) 全局打乱，再取前 k 个；不要试图只打乱前 k 位来优化——那会破坏均匀性
• 随机数引擎 rng 必须是可复制的，推荐用 std::mt19937 配合 std::random_device 初始化，别再用 rand()

std::vector data = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
std::mt19937 g{std::random_device{}()};
std::shuffle(data.begin(), data.end(), g);
std::vector sample(data.begin(), data.begin() + 3); // 取前 3 个

当 k << n 时，用 std::uniform_int_distribution + std::set 避免全量 shuffle

如果数组有 1000 万条记录，但只需要随机抽 10 个，全局 shuffle 就是巨大的浪费。这时候更适合用“拒绝采样 + 去重”策略，用空间换时间。

关键点在于：不能用 std::vector 存已选索引然后每次 std::find——那是 O(k²) 的灾难。用 std::unordered_set 或 std::set 查重，才能做到 O(log k) 甚至均摊 O(1)。

注意陷阱：

• 如果 k 接近 n（比如 n=100，k=95），拒绝采样可能反复碰撞，实际性能反而比 shuffle 差
• std::uniform_int_distribution 的上下界必须是闭区间 [0, n-1]，写成 (0, n) 会漏掉首尾
• 别在循环里反复构造 std::uniform_int_distribution 实例，它不是轻量对象

std::vector data = {/* ... large array ... */};
std::mt19937 g{std::random_device{}()};
std::uniform_int_distribution dist(0, data.size()-1);
std::unordered_set chosen;
std::vector sample;
while (chosen.size() < k) {
    size_t idx = dist(g);
    if (chosen.insert(idx).second) { // insert 返回 pair
        sample.push_back(data[idx]);
    }
}

有放回采样直接用 std::uniform_int_distribution 循环生成索引

如果允许重复（比如蒙特卡洛模拟中按权重重采样前一步结果），就不需要去重逻辑，也不用 shuffle，纯索引生成即可。

性能上这是最轻量的方式：O(k) 时间、O(1) 额外空间。但务必确认业务是否真的允许重复——很多场景表面说“随机选”，实际隐含“不重复”约束，混淆会导致数据偏差。

常见疏忽：

• 忘记把分布对象 dist 定义在循环外，导致每次调用都重新构造，开销陡增
• 用 rand() % n 替代 std::uniform_int_distribution，在 n 不是 2 的幂次时会产生偏置（低位周期短、高位未充分利用）
• 没检查 data 是否为空，data.size()-1 在空容器下会变成极大正数（size_t 下溢）

if (data.empty()) throw std::runtime_error("sampling from empty container");
std::uniform_int_distribution dist(0, data.size()-1);
for (int i = 0; i < k; ++i) {
    sample.push_back(data[dist(g)]);
}

自定义权重采样得用 std::discrete_distribution，别手算前缀和

如果每个元素被选中的概率不同（比如按 PV 加权抽用户），C++11 起就该用 std::discrete_distribution。它内部已经用 Alias Method 或 Walker's Method 优化为 O(1) 查表，比手动二分查找前缀和快得多，数值也更稳定。

容易踩的坑集中在权重输入：

• 权重必须是非负浮点数或整数，传负数会触发断言或未定义行为
• 权重为 0 是合法的，对应概率为 0，但所有权重全为 0 会导致构造失败
• 别把原始数据指针直接喂给构造函数——它只接受迭代器范围或初始化列表，比如 {w0, w1, w2}

std::vector weights = {0.1, 0.6, 0.3};
std::discrete_distribution dist(weights.begin(), weights.end());
for (int i = 0; i < k; ++i) {
    size_t idx = dist(g);
    sample.push_back(data[idx]);
}

真正麻烦的从来不是“怎么写”，而是判断该用哪种采样语义：无放回？有放回？等概？加权？边界条件（空容器、k=0、k>n）有没有被测试覆盖。这些决策点一旦错，后面代码越“高效”越危险。