随机数生成的历史背景
Middle-Square 方法(中位平方法):
- 已知最早的随机算法之一
- 或由修道士 Brother Edvin 在 1245 年发明
- 由 John von Neumann 在 1949 年重新发现
- 缺点明显,但执行速度快
Monte Carlo 方法:
- 起初是机密代码名
- 由 Stanislaw Ulam 和 John von Neumann 在 1946 年为曼哈顿计划开发
- 在 ENIAC 上实现
- 通过大量模拟生成随机样本,再用统计方法分析其行为
- 直到今天仍广泛用于复杂系统模拟
随机数的现代用途
应用 | 示例 |
---|---|
模拟 | 蒙特卡洛方法、物理/金融模拟等 |
算法 | 遗传算法、随机算法、Zobrist 哈希 |
排列 | 洗牌、随机抽签、比赛排位、选举 |
选择 | 游戏抽奖、学生点名、艺术创作、快速排序 pivot |
抽样 | 医药实验、调查问卷、审计、生产质检 |
加密 | 需要额外强度,不适用 <random> |
注意:密码学需求远高于
<random>
能提供的强度,需使用操作系统安全 API 或专用库(如 OpenSSL、libsodium 等)
识别“随机”本身就是难题
“假设神谕者给了你十个连续的 0,你会觉得这是随机的吗?”
- 这是一个引发思考的问题:十个连续的零看起来像是非随机的,但事实上,在随机数序列中,这样的情况完全可能出现。
- Pete Becker 的观点是:十个数字太少了,无法判断一个随机数生成器的质量。
- 同样,Scott Adams(Dilbert漫画作者) 用讽刺幽默的方式表达了类似的观点 —— 我们人类对“看起来随机”的直觉,往往靠不住。
人类直觉在“随机性”问题上常常失灵
P. Diaconis 的研究:硬币落地后落在原来同一面朝上的概率其实略大于 50%(约 51%)。
- 表明真实世界中的“随机”也有物理偏差。
- 比如,头朝上的硬币更容易再次朝上朝上——这打破了我们对抛硬币“完美对半概率”的直觉认知。
Joe Peach 的故事:一个人在赌桌上用硬币决定是否要要牌,结果硬币立在了边上 —— 一种极小概率但确实可能发生的“随机事件”。
实现真正的随机行为非常困难
- Chris Wetzel 指出:统计意义上的“随机”意味着不可预测与无法发现模式。
- Jeff Atwood 和 Mads Haahr 都提到:计算机是“决定性”机器,本质上无法直接生成真正的随机数。
- 随机数相关的教材和论文中,充斥着最终被证明有缺陷或完全错误的算法,说明这确实是一个“看起来简单,实际上复杂”的问题领域。
培训严重不足
- 编程教育很少系统讲授随机性、概率分布、随机变量等知识。
- 一个看似简单的例子:
如果f()
是均匀分布的,那么2 * f()
也是均匀分布,
但f() + f()
却变成了接近正态分布(高斯分布) —— 并非均匀。这意味着我们即使对随机数做了很小的变换,也可能改变其分布性质!
挑战性问题(由 von Neumann 提出):
给定一个有偏的硬币(概率未知,0 < p < 1),
如何用它生成公平(等概率)的结果?
提示:Wikipedia 上“公平硬币”条目有解法(可查找 von Neumann extractor)
→ 但作者建议你先自己思考!
建议:务必极其小心!(
- Stephen K. Park 和 Keith W. Miller:大多数随机数生成器其实都存在非随机行为,有些甚至“糟糕透顶”。
- Brad Lucier:历史上确实有不少“非常糟糕的” RNG 算法被发表在权威期刊,并被广泛采用。
- detly 博客名言:对随机数做任意运算,并不意味着输出依然是随机的!
最后 —— 一点讽刺幽默
“你得到了你要求的,但不是你想要的。”
- 很多程序员写随机代码的时候“语法正确”,但输出的结果和预期完全不符。
- 在 RNG 上更容易出这种“技术上没错、但实际上错了”的情况。
用户分类:
- 初级用户:
- 一个默认引擎类型(
std::default_random_engine
) - 两个通用的均匀分布模板(整数、实数)
- 一个默认引擎类型(
- 中高级用户:
- 9 个预设引擎类型(如 Mersenne Twister)
- 18 个可配置的分布类型(如正态、泊松等)
- 一个系统随机源类(
std::random_device
) - 一个辅助种子类(
std::seed_seq
)
- 专家用户:
- 6 个可配置引擎模板(如线性同余、混合引擎等)
- 一个自定义分布模板工具
说明:<random>
设计为支持从简单用途到复杂科研级别的随机数生成。
C++ 中的术语(Slide 18)
术语混乱的历史:
传统术语“随机数生成器”太模糊了!
在 <random>
中,我们区分两个核心组件:
- Engine(引擎):
- 生成原始、均匀、伪随机的比特序列。
- 理想上是 不可预测 的(虽然计算机做不到真正随机)。
- 如
std::mt19937
、std::default_random_engine
等。
- Distribution(分布):
- 从 engine 的比特流中抽样,转换为特定分布的数值。
- 如:
std::uniform_int_distribution
std::normal_distribution
std::poisson_distribution
std::chi_squared_distribution
std::weibull_distribution
结论:引擎负责“比特”,分布负责“形状”。
引擎类型和用法
- 引擎对象
e
在每次调用e()
时返回一串伪随机的比特(长度为 n),以E::result_type
编码的整数形式返回。 - 比如:
std::mt19937::min()
= 0std::mt19937::max()
= 2³² - 1
- 每次调用返回的数是可预测的(伪随机),但难以预测(设计目标)。
- 一般不需要直接使用返回的比特串,而是通过分布对象来使用引擎。
分布类型和用法
- 分布对象
d
通过调用d(e)
获取一个符合分布的随机值。 - 示例 1:掷骰子函数
#include <random>
int roll_a_fair_die() {static std::default_random_engine e{};static std::uniform_int_distribution<int> d{1, 6};return d(e); // 返回 1 到 6 的伪随机整数
}
- 示例 2:生成长度为 N 的数组,填入掷骰子结果
constexpr std::size_t N = 1000;
int a[N];
std::generate(a, a + N, roll_a_fair_die); // 用骰子函数填数组
注意事项:
- 使用
static
是为了避免每次调用重新构建引擎,影响性能与随机性。 - 可将引擎设为全局、共享,便于多个模块使用同一随机序列。
小结这一部分的要点:
内容 | 要点 |
---|---|
rand() | 不可移植,质量差,应避免使用 |
<random> | 可扩展、高质量、现代化设计 |
Engine | 生成伪随机比特流 |
Distribution | 将比特流映射为具有特定统计特性的值 |
示例 | 使用引擎 + 分布组合获得掷骰子的整数 |
对C++ <random>
头文件中随机数引擎和分布的深入讲解,重点涵盖了以下几个方面:
1. random_device 作为 URBG(Uniform Random Bit Generator)
random_device
设计用来访问物理或环境随机源,比如/dev/random
、CPU 的 RDRAND 指令,或者大气噪声等。- 它的构造函数带一个实现定义的字符串,用来指定设备。
- 它有
entropy()
成员函数,用来估计该设备产生的随机性的熵值(信息量)。 - 这保证了你可以用它作为真正随机(或接近真实随机)的随机数生成器。
2. 提供的 20 种分布
- 包含五类:
- 均匀分布:
uniform_int_distribution
,uniform_real_distribution
- 伯努利及相关分布:
bernoulli_distribution
,binomial_distribution
,geometric_distribution
,negative_binomial_distribution
- 泊松及相关分布:
poisson_distribution
,exponential_distribution
,gamma_distribution
,weibull_distribution
,extreme_value_distribution
- 正态及相关分布:
normal_distribution
,lognormal_distribution
,chi_squared_distribution
,cauchy_distribution
,fisher_f_distribution
,student_t_distribution
- 采样分布:
discrete_distribution
,piecewise_constant_distribution
,piecewise_linear_distribution
- 均匀分布:
- 设计理由是这些分布是统计、工程和科学应用中最常见、最重要的。
3. 分布与引擎的互操作性
- 任何实现了 URBG 接口的引擎都可以和任意分布搭配使用。
- 这保证了扩展性,用户可以自定义新的引擎和分布,且和标准库无缝集成。
- 例如,PCG、Random123 是第三方扩展引擎,GCC 自带了一些额外的分布。
4. 自定义分布的辅助工具
generate_canonical<>()
是一个模板工具,能从 URBG 中产生一个在 [0,1) 均匀分布的浮点数,作为构造自定义分布的基础。
5. 分布的统计测试
- 通过均值、方差、卡方检验、Kolmogorov-Smirnov 检验等统计测试验证分布是否合理。
- 偶尔失败是正常的,失败太多才要怀疑随机数生成的质量。
6. 不要滥用 rand() % n
取模法
- 这个简单取余方法会导致偏差,因为
rand()
的范围通常不是n
的整数倍。 - 应该用标准库的分布,比如
std::uniform_int_distribution
,或者通过拒绝采样(rejection sampling)实现均匀分布。
7. 如何正确生成随机数
- 实例化一个引擎(如
std::default_random_engine
) - 实例化一个分布(如
std::uniform_int_distribution<int>
) - 每次生成随机数时通过
distribution(engine)
产生,确保满足所需分布。
8. 种子与可复现性
- 引擎种子很关键,单个整数种子对大型状态的引擎(如 Mersenne Twister)不足。
std::seed_seq
试图扩展种子,但不总是效果很好。- 种子来源可以是时间戳、进程ID等,但它们质量较低。
9. C++17 之后新增的随机数算法
std::sample
:可以从一个范围中采样固定大小的随机子集。std::shuffle
:随机打乱序列。- 不再推荐使用
random_shuffle
,它已被移除。
10. 迭代器接口(可选进阶)
- 设计了
variate_iterator
,可以把一个随机引擎 + 分布封装成输入迭代器,从而在标准算法中直接使用随机数。
总结起来,这些内容帮你深入理解<random>
设计理念、最佳实践、性能与质量权衡、以及如何用好它来写出健壮的随机数代码。
你这段内容介绍了 C++17 <random>
库中的一些高级用法,特别是 sample()
和 shuffle()
的用法,还有用迭代器接口封装随机数分布生成的思路。
1. sample()
用法
C++17 新增了 std::sample()
,功能是从一个区间(population)中随机采样固定数量元素。接口:
template<class PopulationIter, class SampleIter, class Size, class URBG>
SampleIter sample(PopulationIter first, PopulationIter last,SampleIter out, Size wanted_size, URBG&& g);
PopulationIter
是输入区间的迭代器。SampleIter
是输出区间迭代器。wanted_size
是采样元素数。URBG
是随机数生成器。
实现时,会根据输入迭代器能力,选择不同算法。
2. shuffle()
用法
用于将序列随机打乱。
示例:
using card_t = int;
using deck_t = std::array<card_t, 52>;
deck_t deck;
std::iota(deck.begin(), deck.end(), 0); // 生成0~51
using engine_t = std::default_random_engine;
engine_t e{ std::random_device{}() }; // 真随机种子
std::shuffle(deck.begin(), deck.end(), e);
// 输出花色和点数
auto suit = [](card_t c) { return "♠♥♦♣"[c / 13]; };
auto rank = [](card_t c) { return "A23456789TJQK"[c % 13]; };
for (auto c : deck)std::cout << rank(c) << suit(c) << ' ';
3. shuffle_sort
的“反直觉”示例
template<class RA, class Engine>
void shuffle_sort(RA b, RA e, Engine g)
{while (!std::is_sorted(b, e))std::shuffle(b, e, g);
}
- 这个算法随机打乱序列直到它排序好了,显然效率非常差,作为玩笑演示。
4. 自定义 shuffle
实现示例
这段代码体现了 Fisher–Yates 洗牌算法:
template<class RA, class URBG>
void shuffle(RA b, RA e, URBG&& g)
{using diff_t = decltype(e - b);using dist_t = std::uniform_int_distribution<diff_t>;using param_t = typename dist_t::param_type;static dist_t d; // 分布范围由调用时动态传入diff_t L = e - b - 1;for (diff_t m = 0; m < L; ++m)std::iter_swap(b + m, b + d(g, param_t{m, L}));
}
d(g, param_t{m, L})
生成[m, L]
范围内的随机数。- 逐步交换未洗牌部分的元素,保证均匀性。
5. 设计基于 <random>
的迭代器 variate_iterator
这是一个可用作输入迭代器的类,封装了随机数引擎和分布,使其可以像迭代器一样访问随机数流。
代码草图解析
template<class URBG, class Dist>
class variate_iterator : public std::iterator<std::input_iterator_tag, typename Dist::result_type>
{
private:using val_t = typename Dist::result_type;URBG* u{nullptr}; // 非拥有指针,指向随机数生成器Dist* d{nullptr}; // 非拥有指针,指向分布val_t v{}; // 最近一次生成的随机数值bool valid{false}; // 当前缓存的值是否有效void step() noexcept { valid = false; }val_t& deref() {if (!valid) {v = (*d)(*u); // 调用分布生成新的随机数valid = true;}return v;}
public:constexpr variate_iterator() noexcept = default;variate_iterator(URBG& u_, Dist& d_) : u(&u_), d(&d_) {}val_t& operator*() { return deref(); }val_t const* operator->() { return &deref(); }variate_iterator& operator++() { step(); return *this; }variate_iterator operator++(int) {variate_iterator tmp = *this;step();return tmp;}// TODO: 添加相等比较等必要接口,符合输入迭代器要求
};
用途示例
- 生成随机数序列并复制到容器:
std::default_random_engine engine{std::random_device{}()};
std::uniform_real_distribution<double> dist(0.0, 1.0);
variate_iterator<std::default_random_engine, decltype(dist)> it(engine, dist);
std::vector<double> v(100);
std::copy_n(it, 100, v.begin());
- 用于数学操作,如点积:
double prod = std::inner_product(v.begin(), v.end(), it, 0.0);
- 对已有向量加随机噪声:
std::transform(v.begin(), v.end(), v.begin(), [&](double x) { return x + *it++; });
总结
<random>
提供了强大的随机数工具,不光是生成单个随机数,也可以对序列做采样、洗牌。- 通过封装迭代器,可以让随机数生成器与 STL 算法更好地结合。
- 了解算法实现(如 Fisher-Yates shuffle)能帮助你理解随机过程的正确性。
sample()
函数允许随机采样,避免了先打乱再选取的低效方法。
几个简单实用的随机数小例子(小李子),用C++ <random>
写的,涵盖不同类型的随机数生成:
1. 生成 0 到 99 的随机整数
#include <iostream>
#include <random>
int main() {std::random_device rd; // 真随机种子std::mt19937 gen(rd()); // Mersenne Twister引擎std::uniform_int_distribution<> dist(0, 99); // 均匀分布 [0,99]for (int i = 0; i < 10; ++i) {std::cout << dist(gen) << " ";}std::cout << "\n";
}
2. 生成 0.0 到 1.0 之间的浮点数
#include <iostream>
#include <random>
int main() {std::random_device rd;std::mt19937 gen(rd());std::uniform_real_distribution<> dist(0.0, 1.0);for (int i = 0; i < 10; ++i) {std::cout << dist(gen) << " ";}std::cout << "\n";
}
3. 从容器中随机采样(使用 std::sample
)
#include <iostream>
#include <vector>
#include <random>
#include <algorithm>
int main() {std::vector<int> population{1,2,3,4,5,6,7,8,9,10};std::vector<int> sample_result;std::random_device rd;std::mt19937 gen(rd());std::sample(population.begin(), population.end(), std::back_inserter(sample_result),4, gen); // 从population随机采样4个元素for (int x : sample_result) {std::cout << x << " ";}std::cout << "\n";
}
4. 洗牌一副扑克牌(52张)
#include <iostream>
#include <array>
#include <algorithm>
#include <random>
int main() {using card_t = int;std::array<card_t, 52> deck;std::iota(deck.begin(), deck.end(), 0); // 0~51std::random_device rd;std::mt19937 gen(rd());std::shuffle(deck.begin(), deck.end(), gen);auto suit = [](card_t c) { return "♠♥♦♣"[c / 13]; };auto rank = [](card_t c) { return "A23456789TJQK"[c % 13]; };for (auto c : deck) {std::cout << rank(c) << suit(c) << " ";}std::cout << "\n";
}
5. 用随机数给数组元素加点噪声
#include <iostream>
#include <vector>
#include <random>
#include <algorithm>
int main() {std::vector<double> data = {1.0, 2.0, 3.0, 4.0, 5.0};std::random_device rd;std::mt19937 gen(rd());std::normal_distribution<> noise(0, 0.1); // 均值0,标准差0.1的高斯噪声std::transform(data.begin(), data.end(), data.begin(),[&](double x) { return x + noise(gen); });for (auto d : data) {std::cout << d << " ";}std::cout << "\n";
}