C++1z ランダムサンプリングアルゴリズム

C++

C++1zでは<algorithm>ヘッダに、範囲の中から指定された個数の要素をランダムに抽出するsample()アルゴリズムが定義されます。

#include <iostream>
#include <string>
#include <iterator>
#include <random>
#include <algorithm>

int main()
{
    const std::string input = "abcdef";

    // inputから3要素を無作為抽出する。
    // デフォルトの乱数生成器を使用する
    {
        std::string result;
        std::sample(input.begin(),
                    input.end(),
                    std::back_inserter(result),
                    3);
        std::cout << result << std::endl;
    }

    // inputから3要素を無作為抽出する。
    // 乱数生成器を明示的に渡す
    {
        std::random_device seed_gen;
        std::mt19937 engine {seed_gen()};

        std::string result;
        std::sample(input.begin(),
                    input.end(),
                    std::back_inserter(result),
                    3,
                    engine);
        std::cout << result << std::endl;
    }
}

選ばれる確率は等確率になります。

範囲の要素数が、指定された抽出数よりも小さい場合、範囲の要素数だけ抽出されます。

乱数生成器を渡さない場合、スレッドローカルな乱数生成器が関数内で定義されます。この記事の執筆時点で実装がないので実際にどうなるかはわかりませんが、おそらくdefault_random_engineが使われることになるので、自分で乱数生成器を渡すのがよいと思います。

このアルゴリズムの最適化の余地として、以下の2つの実装がありえます：

  • 出力をランダムアクセスで行うバージョン : KnuthのAlgorithm R (Reservoir sampling)
  • 出力を前から順番に行うバージョン : KnuthのAlgorithm S (Selection sampling)

イテレータカテゴリによってこれらの実装が、コンパイル時に自動的に選択されるようになる可能性があります。

宣言

// <algorithm>
namespace std {
    template <class PopulationIterator, class SampleIterator, class Distance>
    SampleIterator sample(PopulationIterator first, PopulationIterator last,
                          SampleIterator out, Distance n);

    template <class PopulationIterator, class SampleIterator,
              class Distance, class UniformRandomNumberGenerator>
    SampleIterator sample(PopulationIterator first, PopulationIterator last,
                          SampleIterator out, Distance n,
                          UniformRandomNumberGenerator&& g);
}

参照

お断り

この記事の内容は、C++1zが正式リリースされる際には変更される可能性があります。正式リリース後には、C++日本語リファレンスサイトcpprefjpの以下の階層の下に解説ページを用意する予定です。