C++14 Fundamentals TS ランダムサンプリング

N3925 A sample Proposal, v4

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)

参照