4. sample

最終更新日時(UTC):
が更新

履歴 編集

function template
<algorithm>

std::sample(C++17)

namespace std {
  template <class PopulationIterator,
            class SampleIterator,
            class Distance,
            class UniformRandomBitGenerator>
  SampleIterator
    sample(PopulationIterator first,
           PopulationIterator last,
           SampleIterator out, Distance n,
           UniformRandomBitGenerator&& g);
}

概要

イテレータ範囲[first, last)から指定された個数の要素をランダムに抽出する。

テンプレートパラメータ制約

  • PopulationIterator は InputIterator の要件を満たしていること
  • SampleIterator は OutputIterator の要件を満たしていること
  • PopulationIteratorが ForwardIterator の要件を満たさない限り、SampleIteratorはRandomAccessIteratorの要件を満たさなければならない
  • PopulationIteratorの値型はoutに対して書き込めなければならない
  • Distanceは整数型であること
  • UniformRandomBitGenerator は uniform random bit generator の要件を満たさなければならず、その戻り値の型はDistance型へ変換可能でなければならない

事前条件

効果

イテレータ範囲[first, last)を母集団 (population) とし、そこからmin(last - first, n)個の要素を標本 (sample) として out にコピーする (nが入力範囲の要素数より大きい場合は、最大で入力範囲の要素数がコピーされる)。

戻り値

出力範囲の最後のイテレータが返る

計算量

範囲[first, last)の要素数に対して線形時間

備考

このアルゴリズムの実装には、以下の2つのバージョンが使用される：

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

これらのアルゴリズムは、イテレータカテゴリによって、コンパイル時に自動的に選択されることになる。

例

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

int main()
{
  // 乱数生成器を用意する
  std::random_device seed_gen;
  std::mt19937 engine {seed_gen()};

  // 文字列中から3文字をランダム抽出する
  {
    const std::string input = "abcdef";
    const int n = 3;

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

  // 配列から3要素をランダム抽出する
  {
    const std::vector<int> input = {0, 1, 2, 3, 4, 5};
    const int n = 3;

    std::vector<int> result;
    std::sample(input.begin(),
                input.end(),
                std::back_inserter(result),
                n,
                engine);

    for (int x : result) {
      std::cout << x;
    }
    std::cout << std::endl;
  }
}

出力例

bcd
235

バージョン

言語

  • C++17

処理系

参照