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

用 std::shuffle 做无放回随机采样最稳妥：先全局打乱再取前 k 个，避免误用不存在的 partial_shuffle；k≪n 时改用 uniform_int_distribution 配 unordered_set 拒绝采样；有放回直接生成索引；加权采样必用 discrete_distribution。

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

如果你要从数组中等概率抽取 k 个不重复元素（比如选 5 个用户做 A/B 测试），std::shuffle 配合 std::vector::begin() 截断是最直接、最不容易出错的方式。它底层用 Fisher–Yates 算法，时间复杂度 O(n)，且标准库已做优化，比手写循环更可靠。

常见错误是只 shuffle 前 k 位（误用 partial_shuffle）——C++ 标准库里根本没有 partial_shuffle，有人搜到的都是过时提案或第三方实现，强行用会导致未定义行为。

实操建议：

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

std::vector<int> 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<int> sample(data.begin(), data.begin() + 3); // 取前 3 个

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

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

立即学习“C++免费学习笔记（深入）”；

关键点在于：不能用 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<int> data = {/* ... large array ... */};std::mt19937 g{std::random_device{}()};std::uniform_int_distribution<size_t> dist(0, data.size()-1);std::unordered_set<size_t> chosen;std::vector<int> sample;<p>while (chosen.size() < k) {size_t idx = dist(g);if (chosen.insert(idx).second) { // insert 返回 pair<iter, bool>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<size_t> 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，它内部已优化为 O(1) 查表（Alias Method 或 Walker’s Method），比手动二分查找前缀和快得多，且数值更稳定。

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

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

std::vector<double> weights = {0.1, 0.6, 0.3};std::discrete_distribution<size_t> 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）有没有被测试覆盖。这些决策点一旦错，后面代码越“高效”越危险。