길이를 모르는 스트림의 균등 표본

K개 슬롯만 유지하는 reservoir sampling의 교체 확률을 추적하고 포함 확률·중복 값·종료와 재현 조건을 구분합니다.

알고리즘 · 원리·구현·운영

기술 지식 트리

이 문제의 핵심은 전체 입력을 기억하지 않고도 각 발생 항목이 최종 표본에 들어갈 확률을 같게 만드는 것입니다. 표본 크기 K, 지금까지 본 항목 수 N, 난수 범위를 분리해 생각해야 하며, 값의 고유성·최근성·테넌트별 공정성은 다른 정책입니다. 아래 알고리즘은 입력이 끝나지 않아도 한 번씩만 흘려보내며, 종료 시점의 포함 확률을 설명할 수 있는 상태를 유지합니다.

앞 K개 편향과 후속 입력의 표본 기회

끝이 언제인지 모르는 로그에서 100개만 표본으로 보관하고 싶다고 합시다. 앞의 100개만 저장하면 오래된 입력에 치우칩니다. 전체를 저장한 뒤 셔플하면 공정하게 고를 수 있지만 메모리 목표를 잃습니다.

Reservoir sampling은 K개 슬롯만 유지하면서 새로운 항목이 들어올 때 일부 표본을 교체합니다. 처리한 입력 N개 중 각 발생 항목이 K/N 확률로 남도록 설계합니다. 기본 알고리즘은 최근 항목을 더 중요하게 보거나 테넌트별 표본 수를 균등하게 만들지 않습니다.

K=1·세 항목의 포함 확률 예시

K=1이고 입력이 A,B,C 순서라고 하겠습니다. A를 먼저 저장하고, B는 1/2 확률로 A를 교체합니다. C는 1/3 확률로 현재 표본을 교체합니다.

최종 표본	남는 사건	확률
A	B에서 유지하고 C에서도 유지	1/2 × 2/3 = 1/3
B	B로 교체하고 C에서 유지	1/2 × 2/3 = 1/3
C	마지막에 교체	1/3

처음 항목은 오래 살아남아야 하므로 이후의 교체 위험을 더 많이 겪습니다. 새 항목은 작은 확률로 들어오지만 남은 위험이 적습니다. 두 효과가 맞아떨어져 최종 포함 확률이 같아집니다.

새 항목의 교체 기회를 줄이기 화살표는 입력을 처리하는 순서입니다. 각 단계의 교체 확률은 현재까지 읽은 항목 수를 기준으로 합니다.

그림을 글로 읽기

첫 항목 A: 일단 저장
두 번째 B: 1/2 확률로 교체
세 번째 C: 1/3 확률로 교체
표본 1개: A · B · C 각각 1/3

첫 항목 A → 두 번째 B: 입력 수 2
두 번째 B → 세 번째 C: 입력 수 3
세 번째 C → 표본 1개: 이 시점에 종료

K개 reservoir 슬롯 적용 알고리즘

작은 상태를 따라가면 규칙이 분명해집니다. K=2에서 A, B를 읽은 뒤 reservoir는 [A,B]입니다. 세 번째 C에서 j=1이면 B를 C로 바꾸어 [A,C]가 되고, j=0이면 [C,B]가 되며, j=2이면 아무것도 바꾸지 않습니다. 네 번째 D에서는 j의 범위가 0~3으로 다시 넓어집니다. 따라서 “새 항목을 넣을지”와 “어느 슬롯을 바꿀지”를 한 번의 난수로 처리하되, seen을 먼저 증가시키는 순서가 경계 조건입니다.

sample(stream, K):
    require integer K and K >= 0
    if K == 0: return []
    reservoir = []
    seen = 0
    for item in stream:
        seen += 1
        if seen <= K:
            reservoir.append(item)
        else:
            j = uniformBelow(seen)       # 0 .. seen-1
            if j < K:
                reservoir[j] = item
    return reservoir

처음 K개는 모두 넣습니다. i번째 새 항목은 i개 숫자 중 K개를 뽑았을 때 들어가므로 확률 K/i입니다. 들어갈 경우 K개 슬롯 가운데 하나를 균등하게 교체합니다. 입력이 K개보다 적으면 모두 반환합니다. K=0에서 스트림을 소비해야 하는 부수 계약이 있다면 즉시 반환 대신 순회하되 표본을 저장하지 않는 별도 동작으로 정의합니다.

N개 입력의 시간은 O(N), 표본 공간은 O(K)입니다. 로그 수가 매우 크면 seen의 정수 범위와 난수 API가 지원하는 상한을 확인해야 합니다. 원천 난수의 범위를 넘는 i를 단순 나머지로 처리하면 균등성 전제가 깨집니다.

기존 항목의 K/i 포함 확률 유도

i-1개 처리 뒤 어떤 기존 항목의 포함 확률이 K/(i-1)이라고 가정합니다. 새 항목이 그 항목의 슬롯을 골라 제거할 확률은 1/i입니다. 따라서 기존 항목이 계속 남을 확률은 다음과 같습니다.

K/(i-1) × (1 - 1/i) = K/i

새 항목도 K/i 확률로 들어오므로 모든 항목의 주변 포함 확률이 같아집니다. 더 강하게는 Algorithm R의 교체 규칙으로 크기 K의 모든 부분집합도 균등합니다. 하지만 reservoir 배열 안의 순서가 균등 순열이라는 뜻은 아닙니다. 순서까지 무작위여야 한다면 마지막 표본을 별도로 셔플합니다.

표본 항목의 발생 단위와 고유 값 기준

값이 A,A,B로 들어오면 기본 알고리즘은 두 A의 발생을 별개로 셉니다. 고유 값 A와 B를 반반 뽑는 알고리즘이 아닙니다. 고유 사용자별 표본이라면 먼저 중복 제거 상태를 유지해야 하고 그 메모리가 K를 넘을 수 있습니다.

예를 들어 A와 B까지 처리한 뒤 중단했다면, reservoir 배열만 저장해서는 다음 입력을 같은 결과로 이어 갈 수 없습니다. 현재 처리 위치와 seen=2, 난수 상태, 입력 버전을 함께 보존해야 하며, 같은 seed라도 입력 순서나 알고리즘 버전이 달라지면 결과가 달라질 수 있습니다. 여러 샤드가 각각 K개씩 보관한 표본을 단순히 합쳐 다시 K개로 줄이는 방법도 샤드 크기가 다르면 원래 항목별 포함 확률을 보존하지 못합니다. 분산으로 합치려면 각 샤드가 처리한 항목 수를 반영하는 별도 병합 절차가 필요합니다.

소규모 입력의 전수 확률 계산

재현 가능한 검증에서는 uniformBelow를 고정열 [1, 2, 0, 3]처럼 주입하고 각 단계의 reservoir를 기록합니다. 예상 결과는 세 번째 입력에서 j=K-1일 때 교체되고 j=K일 때 건너뛰는 것입니다. 실제 난수 구현의 균등성은 이 한 사례로 증명되지 않으므로, 분포 검정과 큰 seen 값의 범위 처리도 별도로 확인해야 합니다.

N=4, K=2에서 3번째 선택 j는 0~~2, 4번째는 0~~3이므로 12개 동일 확률 경로가 있습니다. 최종 부분집합 여섯 개가 각각 두 경로씩 나오는지 전수 계산할 수 있습니다. K=1의 세 항목 예와 함께 고정 난수를 주입해 j=K-1은 교체하고 j=K는 건너뛰는 경계도 확인합니다.

운영 표본이 오류를 더 많이 보존하도록 가중되었다면 그 정책을 균등 reservoir라고 부르지 않습니다. 관찰 지표를 표본으로 추정할 때도 추출 확률을 반영해야 하며, 단순 표본 개수를 전체 비율로 오해하지 않아야 합니다.

후속·관련 개념

함께 읽을 문서

전체 기술 지식

선택 연습 · 관련 질문 1개

질문은 이해를 확인하는 보조 자료입니다. 학습 경로와 문서의 범위는 질문 수와 독립적입니다.

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