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에 작성되었습니다.