CppCon 2016 學習:What C++ Programmers Need to Know about Header ＜random＞

隨機數生成的歷史背景

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() = 0
- std::mt19937::max() = 232 - 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";
}