std::seed_seq:: generate

From cppreference.net

< cpp ‎ | numeric ‎ | random ‎ | seed seq

template < class RandomIt > void generate ( RandomIt begin, RandomIt end ) ;		(C++11以降)

偏りのある可能性があるシードを v に格納されている値に基づいて、出力範囲 [ begin , end ) を32ビット符号なし整数値で埋めることにより、不偏なシードを生成します。

begin == end が true の場合、何も行いません。
それ以外の場合、後述の生成アルゴリズムに従ってシードを生成します。

std:: iterator_traits < RandomIt > :: value_type が符号なし整数型でない場合、またはそのビット幅が32未満の場合、プログラムは不適格です。

RandomIt が LegacyRandomAccessIterator の要件を満たさない場合、または mutable でない場合、動作は未定義です。

翻訳の説明： - 「Contents」を「目次」に翻訳しました - C++関連の専門用語（Generation algorithm、Parameters、Exceptions、Notes、Example、Defect reports）は原文のまま保持しました - HTMLタグ、属性、クラス名、IDなどは一切変更していません - 数値、リンク、構造は完全に保持されています

生成アルゴリズム

以下の値と操作が与えられた場合：

値	定義
z	`v` . size ( )
n	end - begin
m	std:: max ( z + 1 , n )
t	( n >= 623 ) ? 11 : ( n >= 68 ) ? 7 : ( n >= 39 ) ? 5 : ( n >= 7 ) ? 3 : ( n - 1 ) / 2
p	( n - t ) / 2
q	p + t
操作	定義
$xor$	組み込みビット単位XOR
$rshift$	組み込みビット単位右シフト
$T(x)$	$x xor (x rshift 27)$

生成アルゴリズムは以下の手順から構成され、ここで $\scriptsize S_i $ $S i$ は begin [ i % n ] を、 $\scriptsize V_i $ $V i$ は v [ i ] をそれぞれ示します：

1) 出力範囲の各要素を値 0x8b8b8b8b に設定します。

2) 各整数 k に対して、

の範囲内で、以下の操作を順に実行します：

r 1

を

1664525\cdotT(S k xor S k+p xor S k-1)

と定義する。

r 2

を

r 1 +j

と定義する。ここで

j

は以下の通り：

$\scriptsize z $ $z$ （ $k=0$ の場合）
$(k mod n)+V k-1$ （ $0<k⩽z$ の場合）
$k mod n$ （ $z<k$ の場合）

S k+p

を

(S k+p +r 1) mod 2 32

に設定する。

S k+q

を

(S k+q +r 2) mod 2 32

に設定する。

S k

を

r 2 mod 2 32

に設定します。

3) 各整数 k に対して、

m + n

の範囲内で、以下の操作を順番に実行します：

r 3

を

1566083941\cdotT(S k +S k+p +S k-1)

とする。

r 4

を

r 3 -(k mod n)

と定義する。

S k+p

を

(S k+p xor r 3) mod 2 32

に設定する。

S k+q

を

(S k+q xor r 4) mod 2 32

に設定する。

S k

を

r 4 mod 2 32

に設定します。

パラメータ

begin, end

出力範囲を示すイテレータ

例外

RandomIt の操作が begin および end に対して投げる例外のみを投げる。

注記

生成アルゴリズムは、松本眞と西村拓士によるメルセンヌ・ツイスター生成器の初期化シーケンスを基に、齊藤睦夫が2007年に行った改良を組み込んで適応したものです。

例

このコードを実行

#include <algorithm>
#include <cassert>
#include <cstdint>
#include <iostream>
#include <random>
// std::seed_seqの主要部分のプロトタイプ...
struct seed_seq
{
    std::vector<std::uint32_t> v;
    seed_seq(std::initializer_list<std::uint32_t> const il) : v{il} {}
    template<typename RandomIt>
    void generate(RandomIt first, RandomIt last)
    {
        if (first == last)
            return;
        //
        // v = {1, 2, 3, 4, 5} および distance(first, last) == 10 と仮定。
        //
        // Step 1: 0x8b8b8b8bで埋める
        // seeds = {2341178251, 2341178251, 2341178251, 2341178251, 2341178251,
        //          2341178251, 2341178251, 2341178251, 2341178251, 2341178251}
        //
        std::fill(first, last, 0x8b8b8b8b);
        //
        // ステップ 2:
        // n = 10, s = 5, t = 3, p = 3, q = 6, m = 10
        //
        const std::uint32_t n = last - first;
        const std::uint32_t s = v.size();
        const std::uint32_t t = (n < 7) ? (n - 1) / 2
                              : (n < 39) ? 3
                              : (n < 68) ? 5
                              : (n < 623) ? 7
                              : 11;
        const std::uint32_t p = (n - t) / 2;
        const std::uint32_t q = p + t;
        const std::uint32_t m = std::max(s + 1, n);
        //
        // 最初の反復、k = 0; r1 = 1371501266, r2 = 1371501271
        //
        // seeds = {1371501271, 2341178251, 2341178251, 3712679517, 2341178251,
        //          2341178251, 3712679522, 2341178251, 2341178251, 2341178251}
        //
        // k = 1 から k = 5 までの反復処理 (r2 = r1 + k % n + v[k - 1])
        //
        // r1 = 2786190137, 3204727651, 4173325571, 1979226628, 401983366
        // r2 = 2786190139, 3204727655, 4173325577, 1979226636, 401983376
        //
        // seeds = {3350727907, 3188173515, 3204727655, 4173325577, 1979226636,
        //           401983376, 3591037797, 2811627722, 1652921976, 2219536532}
        //
        // k = 6 から k = 9 までの反復 (r2 = r1 + k % n)
        //
        // r1 = 2718637909, 1378394210, 2297813071, 1608643617
        // r2 = 2718637915, 1378394217, 2297813079, 1608643626
        //
        // seeds = { 434154821, 1191019290, 3237041891, 1256752498, 4277039715,
        //          2010627002, 2718637915, 1378394217, 2297813079, 1608643626}
        //
        auto begin_mod = [first, n](std::uint32_t u) -> decltype(*first)&
        {
            return first[u % n]; // すなわち、begin[x] は n を法として計算される
        };
        auto T = []
（注：元のテキストは閉じ括弧のみのため、日本語でも同じ記号を保持します）(std::uint32_t x) { return x ^ (x >> 27); };
        for (std::uint32_t k = 0, r1, r2; k < m; ++k)
        {
            r1 = 1664525 * T(begin_mod(k) ^ begin_mod(k + p) ^ begin_mod(k - 1));
            r2 = (k == 0) ? r1 + s
               : (k <= s) ? r1 + k % n + v[k - 1]
               :            r1 + k % n;
            begin_mod(k + p) += r1;
            begin_mod(k + q) += r2;
            begin_mod(k) = r2;
        }
        //
        // ステップ 3
        // k = 10 から k = 19 までの反復処理、^= を使用して出力を変更
        //
        // r1 = 1615303485, 3210438310, 893477041, 2884072672, 1918321961,
        // r2 = 1615303485, 3210438309, 893477039, 2884072669, 1918321957
        //
        // seeds = { 303093272, 3210438309,  893477039, 2884072669, 1918321957,
        //          1117182731, 1772877958, 2669970405, 3182737656, 4094066935}
        //
        // r1 =  423054846, 46783064, 3904109085, 1534123446, 1495905687
        // r2 =  423054841, 46783058, 3904109078, 1534123438, 1495905678
        //
        // seeds = { 4204997637, 4246533866, 1856049002, 1129615051, 690460811,
        //           1075771511,   46783058, 3904109078, 1534123438, 1495905678}
        //
        for (std::uint32_t k = m, r3, r4; k < m + n; ++k)
        {
            r3 = 1566083941 * T(begin_mod(k) + begin_mod(k + p) + begin_mod(k - 1));
            r4 = r3 - k % n;
            begin_mod(k+p) ^= r3;
            begin_mod(k+q) ^= r4;
            begin_mod(k) = r4;
        }
    }
};
int main()
{
    const auto input = std::initializer_list<std::uint32_t>{1, 2, 3, 4, 5};
    const auto output_size = 10;
    // std::seed_seq の標準バージョンを使用
    std::seed_seq seq(input);
    std::vector<std::uint32_t> seeds(output_size);
    seq.generate(seeds.begin(), seeds.end());
    for (const std::uint32_t n : seeds)
        std::cout << n << '\n';
    // カスタムバージョンのseed_seqを使用
    seed_seq seq2(input);
    std::vector<std::uint32_t> seeds2(output_size);
    seq2.generate(seeds2.begin(), seeds2.end());
    assert(seeds == seeds2);
}

出力:

不具合報告

以下の動作変更の欠陥報告書は、以前に公開されたC++規格に対して遡及的に適用されました。

DR	適用対象	公開時の動作	正しい動作
LWG 2180	C++11	`seed_seq::generate` は例外を送出しない	例外を送出する可能性がある

Compiler support
Freestanding and hosted
Language
Standard library
Standard library headers
Named requirements
Feature test macros (C++20)
Language support library
Concepts library (C++20)
Diagnostics library
Memory management library
Metaprogramming library (C++11)
General utilities library
Containers library
Iterators library
Ranges library (C++20)
Algorithms library
Strings library
Text processing library
Numerics library
Date and time library
Input/output library
Filesystem library (C++17)
Concurrency support library (C++11)
Execution control library (C++26)
Technical specifications
Symbols index
External libraries

Member functions
seed_seq::seed_seq
seed_seq::generate
seed_seq::size
seed_seq::param

cppreference.net

Namespaces

Variants

std::seed_seq:: generate

目次

生成アルゴリズム

パラメータ

例外

注記

例

不具合報告