4. sample

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

履歴 編集

function template
<algorithm>

std::ranges::sample(C++20)

namespace std::ranges {
  // (1)
  template<input_iterator I, sentinel_for<I> S, weakly_incrementable O, class Gen>
    requires (forward_iterator<I> || random_access_iterator<O>) && indirectly_copyable<I, O> && uniform_random_bit_generator<remove_reference_t<Gen>>
  O sample(I first, S last, O out, iter_difference_t<I> n, Gen&& g);

  // (2)
  template<input_range R, weakly_incrementable O, class Gen>
    requires (forward_range<R> || random_access_iterator<O>) && indirectly_copyable<iterator_t<R>, O> && uniform_random_bit_generator<remove_reference_t<Gen>>
  O sample(R&& r, O out, range_difference_t<R> n, Gen&& g);
}

概要

範囲から指定された個数の要素をランダムに抽出する。

  • (1): イテレータペアで範囲を指定する
  • (2): 範囲を直接指定する

事前条件

  • outは範囲[first, last)に含まれてはならない

効果

範囲[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::ranges::sample(input, 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::ranges::sample(input, std::back_inserter(result), n, engine);

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

出力例

bcd
235

バージョン

言語

  • C++20

処理系

参照