전체 길이를 모르는 스트림에서 K개를 균등하게 뽑으려 합니다. 모든 항목을 저장하지 않고 어떻게 하나요?

reservoir sampling은 크기 K의 표본만 유지하면서 입력을 한 번 순회해 각 항목이 같은 포함 확률을 갖도록 하는 방법입니다. 전체 길이를 미리 몰라도 되지만 처리한 항목 수와 무작위 선택 규칙이 정확해야 합니다.

동작 원리와 전제

처음 K개를 저장하고 이후 i번째 항목에서 0부터 i-1까지 균등한 정수를 뽑아 K 미만이면 그 슬롯을 교체합니다. 최종 N개 입력에서 각 항목의 포함 확률이 K/N이 되도록 교체 확률을 조절합니다.

선택과 실패 처리

무작위 정수의 범위와 modulo bias, 카운터 overflow를 확인합니다. K보다 적은 입력은 모두 반환하고 K=0 같은 경계를 정의합니다. 동일 값이 여러 번 나온 것은 값 중복인지 서로 다른 발생 항목인지 표본 단위를 정해야 합니다.

구체적인 사례와 검증

K=1인 경우 첫 항목을 저장하고 두 번째는 1/2, 세 번째는 1/3 확률로 교체합니다. 최종 세 항목 각각이 남을 확률은 1/3이 되며 초기 항목이 항상 유리하지 않도록 교체 확률이 줄어듭니다. K가 일반 값이면 같은 논리를 K개 슬롯에 적용합니다. 무작위 순서의 앞 K개를 읽는 방식은 입력이 이미 균등 무작위라는 전제가 있어야 하므로 정렬된 로그에는 그대로 적용할 수 없습니다. 고정 RNG를 주입해 어떤 값에서 교체되는지 테스트하고 여러 실행의 포함 빈도를 보조 지표로 확인합니다. 스트림을 저장하지 않는 대신 과거 표본을 다시 재현할 seed·입력 버전이 필요한지도 정합니다.

작은 N에서 반복 실험해 포함 빈도를 확인하되 통계 시험만으로 구현을 증명하지 않습니다. 고정 난수 입력으로 경계 연산을 검증합니다. 시간 가중·테넌트 균형 표본은 균등 reservoir와 다른 목표이므로 별도 알고리즘을 선택합니다.