C++17 - 랜덤 샘플링 알고리즘

std::sample()<algorithm>에 추가 되었다.

#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;
    }
}

선정되는 확률은 등확률이다.

범위의 요소 수가 지정된 추출 수보다 작은 경우, 범위의 요수 수만 추출된다.

난수 생성기를 전달하지 않으면 스레드 로컬에 만들어지는 난수 생성기를 함수 내에서 정의된다.

이 알고리즘은 아래의 2가지 버전이 사용된다

  • 출력을 랜덤 접근으로 하는 버전 : Knuth의 Algorithm R(Reservoir sampling)
  • 출력을 앞에서 차례로 하는 버전 : Knuth의 Algorithm S(Selection sampling)

이 알고리즘들은 반복자 카테고리에 의해서 컴파일 시에 자동으로 선택된다.


이 글은 2020-06-23에 작성되었습니다.