[C++] 从 0 到 2 亿随机采样（300 个）的最佳实践？

[zynlp]

google 了给的结果：
1、先 shuffle 再取前 300 个
2、stl::sample （ only c++17 ）

有没有什么其他更好的方法？

[wutiantong]

从 2 亿个数里随机取一个(std::uniform_int_distribution)记为 a1
从(2 亿-1)个数里随机取一个记为 a2，if (a2 >= a1) then (a2 += 1)
从(2 亿-2)个数里随机取一个记为 a3，if (a3 >= max(a1, a2)) then (a3 += 2) elif (a3 >= min(a1, a2)) then (a3 += 1)
依次类推 300 次

[geelaw]

这个“随机采样”根本没说明白，根据心电感应做题法，你希望从 0 到 2 亿无放回抽样 300 个。

方法 1：你做 300 次有放回抽样，如果有重复就再来一次。这样做期望 1.00224502750272 次可以得到一个有效结果。这个东西的别名叫做 birthday attack。

方法 2：按照 #1 的方法挖洞。

[GeruzoniAnsasu]

不知道这“最佳实践”最佳在哪个方面

是效率还是随机性还是均匀度还是什么的

可以参考下这个，stl 默认的随机数引擎
https://zh.cppreference.com/w/cpp/numeric/random/mersenne_twister_engine

[Nirvanada]

参考下蓄水池采样

[ipwx]

我觉得 reject sampling 对这个场景其实还行。