C++14後のLibrary Fundamentals TSでは、<algorithm>
ヘッダに、ランダムサンプリング(無作為抽出)の関数std::sample()
が追加される予定です。
template <class PopulationIterator, class SampleIterator, class Distance, class UniformRandomNumberGenerator> SampleIterator sample(PopulationIterator first, PopulationIterator last, SampleIterator out, Distance n, UniformRandomNumberGenerator&& g);
この関数を使用すると、入力のイテレータ範囲から、n
個の要素を等確率で取得できます。
const std::vector<int> v = {1, 2, 3, 4, 5}; std::random_device seed_gen; std::mt19937 engine(seed_gen()); // vから3要素を無作為に抽出 std::vector<int> result; sample(v.begin(), v.end(), std::back_inserter(result), 3, engine); for (int x : result) { std::cout << x << std::endl; }
出力例
1 3 4
このアルゴリズムの代表的な実装方式:
- 出力をランダムアクセスで行うバージョン : KnuthのAlgorithm R (Reservoir sampling)
- 出力を前から順番に行うバージョン : KnuthのAlgorithm S (Selection sampling)