데이터를 처리할 때 항상 모든 값을 메모리에 저장할 수 있는 것은 아닙니다.
예를 들어 서버 로그, 클릭 이벤트, 센서 데이터처럼 계속 들어오는 데이터는 양이 너무 많을 수 있습니다.
이럴 때 전체 데이터를 저장하지 않고도, 지금까지 들어온 데이터 중 일부를
공평하게 대표 샘플로 유지해야 하는 경우가 있습니다.
이번 글에서는 큰 로그 스트림에서 대표 샘플 K개를 유지하는 방법을 정리해보겠습니다.
이 방식은 Reservoir Sampling을 여러 개 샘플로 확장한 형태입니다.
문제
한 서버에는 사용자 이벤트 로그가 계속 들어오고 있습니다.
로그의 양이 너무 많아서 전체 로그를 리스트에 저장할 수 없습니다.
대신 지금까지 들어온 로그 중에서 대표 샘플 K개만 유지하려고 합니다.
단, 최종적으로는 지금까지 들어온 모든 로그가 샘플에 포함될 기회를 공평하게 가져야 합니다.
로그 스트림과 샘플 개수 K가 주어졌을 때, 전체 데이터를 저장하지 않고 대표 샘플 K개를 반환하는 함수를 작성하세요.
예시 상황
로그가 아래 순서로 들어온다고 해보겠습니다.
login
click
scroll
purchase
logout
share
그리고 K = 3이라면, 최종적으로 이 로그들 중 3개만 샘플로 남깁니다.
예를 들어 결과는 실행할 때마다 달라질 수 있습니다.
["click", "purchase", "share"]
또는 이렇게 나올 수도 있습니다.
["login", "scroll", "logout"]
중요한 점은 특정 로그만 계속 유리하면 안 된다는 것입니다.
앞에 들어온 로그든, 뒤에 들어온 로그든, 전체 로그 중 샘플에 포함될 확률이 공평해야 합니다.
처음 떠오르는 생각
가장 쉬운 방법은 모든 로그를 배열에 저장한 뒤 무작위로 K개를 뽑는 것입니다.
random.sample(logs, k)
하지만 이 방법은 전체 로그가 메모리에 있어야 합니다.
이번 문제에서는 로그가 너무 많아서 전체를 저장할 수 없습니다.
그래서 필요한 것은 이런 방식입니다.
전체 데이터는 저장하지 않는다.
현재 대표 샘플 K개만 유지한다.
새 로그가 들어올 때마다 일정 확률로 샘플을 교체한다.
핵심 아이디어
처음 K개의 로그는 일단 샘플에 넣습니다.
그다음부터 새로운 로그가 들어올 때마다, 현재까지 본 데이터 개수를 기준으로 샘플에 들어갈 기회를 줍니다.
예를 들어 지금까지 본 로그 개수가 count라고 하겠습니다.
새 로그가 들어왔을 때:
0부터count - 1사이의 무작위 번호를 하나 뽑습니다.- 그 번호가
K보다 작으면 샘플의 해당 위치를 새 로그로 교체합니다. - 그 번호가
K이상이면 새 로그는 버립니다.
이렇게 하면 전체 데이터를 저장하지 않고도 대표 샘플 K개를 공평하게 유지할 수 있습니다.
코드
import random
def sample_k_from_stream(stream, k):
if k <= 0:
return []
samples = []
count = 0
for item in stream:
count += 1
if len(samples) < k:
samples.append(item)
continue
index = random.randint(0, count - 1)
if index < k:
samples[index] = item
return samples
코드 해설
1. 대표 샘플을 저장할 배열 만들기
samples = []
samples에는 최종적으로 유지할 대표 샘플들이 들어갑니다.
전체 데이터를 저장하는 것이 아니라, 최대 K개만 저장합니다.
2. 지금까지 본 데이터 개수 세기
count = 0
스트림에서 데이터를 하나 읽을 때마다 count를 증가시킵니다.
count += 1
count는 지금까지 몇 개의 데이터를 봤는지 알려줍니다.
3. 처음 K개는 그대로 넣기
if len(samples) < k:
samples.append(item)
처음에는 샘플 공간이 비어 있습니다.
그래서 처음 K개의 데이터는 바로 샘플에 넣습니다.
예를 들어 K = 3이라면 처음 3개는 일단 샘플이 됩니다.
4. K개 이후부터는 확률적으로 교체하기
index = random.randint(0, count - 1)
if index < k:
samples[index] = item
새 데이터가 들어올 때마다 0부터 count - 1 사이의 번호를 하나 뽑습니다.
그 번호가 K보다 작으면 샘플 안의 해당 위치를 새 데이터로 교체합니다.
그 번호가 K 이상이면 새 데이터는 샘플에 들어가지 못합니다.
예제로 흐름 따라가기
스트림이 아래처럼 들어온다고 해보겠습니다.
a, b, c, d, e
그리고 K = 2라고 하겠습니다.
1. a 입력
샘플 공간이 아직 비어 있으므로 a를 넣습니다.
samples = [a]
2. b 입력
아직 샘플 크기가 K보다 작으므로 b도 넣습니다.
samples = [a, b]
3. c 입력
이제부터는 샘플이 이미 가득 찼습니다.
현재까지 본 개수는 3개입니다.
0부터 2 사이의 숫자를 하나 뽑습니다.
- 0이 나오면
samples[0]을c로 교체 - 1이 나오면
samples[1]을c로 교체 - 2가 나오면 교체하지 않음
즉, c가 샘플에 들어갈 확률은 2/3입니다.
4. d 입력
현재까지 본 개수는 4개입니다.
0부터 3 사이의 숫자를 하나 뽑습니다.
그중 0 또는 1이 나오면 샘플에 들어갑니다.
즉, d가 샘플에 들어갈 확률은 2/4입니다.
왜 공평할까?
최종적으로 전체 데이터가 N개라면, 각 데이터가 샘플에 포함될 확률은 K / N이 되어야 합니다.
Reservoir Sampling은 이 조건을 만족하도록 설계된 방식입니다.
처음에 들어온 데이터는 먼저 샘플에 들어가지만, 뒤에 들어오는 데이터들에 의해 교체될 수 있습니다.
뒤에 들어온 데이터는 처음부터 샘플에 있지는 않지만, 들어오는 순간 일정 확률로 기존 샘플을 대체할 기회를 가집니다.
이 과정을 거치면 앞쪽 데이터와 뒤쪽 데이터 모두 최종 샘플에 남을 확률이 같아집니다.
초보 단계에서는 수식을 모두 외우기보다 이렇게 이해하면 됩니다.
처음 데이터는 먼저 들어갈 기회를 얻고,
나중 데이터는 교체할 기회를 얻는다.
이 균형 덕분에 최종 확률이 맞춰진다.
시간 복잡도와 공간 복잡도
데이터 개수를 N, 유지할 샘플 개수를 K라고 하면:
- 시간 복잡도:
O(N) - 공간 복잡도:
O(K)
스트림 데이터를 한 번씩 확인해야 하므로 시간은 O(N)입니다.
하지만 저장하는 데이터는 전체가 아니라 샘플 K개뿐입니다.
그래서 공간은 O(K)입니다.
이 문제에서 중요한 포인트
이 문제는 단순히 무작위로 뽑는 문제가 아닙니다.
핵심은 아래 조건입니다.
전체 데이터를 저장하지 못한다.
데이터 개수를 미리 알 수 없을 수 있다.
샘플 K개만 유지해야 한다.
모든 데이터가 공평한 확률을 가져야 한다.
그래서 일반적인 random.sample() 방식이 아니라 Reservoir Sampling을 사용합니다.
언제 사용할 수 있을까?
이 방식은 이런 상황에서 사용할 수 있습니다.
- 서버 로그가 너무 많을 때
- 실시간 이벤트 중 일부만 대표 샘플로 남기고 싶을 때
- 큰 파일에서 일부 줄만 공평하게 뽑고 싶을 때
- 데이터 전체 개수를 미리 알 수 없을 때
- 메모리를 적게 쓰면서 표본을 유지해야 할 때
즉, 데이터가 계속 흐르고 전체 저장이 어려운 상황에 잘 맞습니다.
헷갈리기 쉬운 부분
1. 왜 처음 K개는 그냥 넣을까?
처음에는 샘플 공간이 비어 있기 때문입니다.
샘플을 K개 유지해야 하므로 처음 K개는 일단 후보로 넣습니다.
그 뒤에 들어오는 데이터들이 일정 확률로 기존 샘플을 교체합니다.
2. 왜 새 데이터가 항상 들어가면 안 될까?
새 데이터가 항상 샘플에 들어가면 뒤쪽 데이터가 너무 유리해집니다.
그렇게 되면 앞쪽 데이터가 공평한 기회를 갖지 못합니다.
그래서 새 데이터는 일정 확률로만 샘플에 들어가야 합니다.
3. 전체 데이터 개수를 몰라도 될까?
네, 몰라도 됩니다.
스트림을 읽으면서 count를 직접 세기 때문입니다.
이 점이 Reservoir Sampling이 스트림 처리에 잘 맞는 이유입니다.
정리
이번 글에서는 전체를 저장할 수 없는 로그 스트림에서 대표 샘플 K개를 유지하는 방법을 정리했습니다.
핵심은 아래와 같습니다.
처음 K개는 샘플에 넣고,
그 이후 데이터는 일정 확률로 기존 샘플을 교체한다.
이 방식은 전체 데이터를 저장하지 않고도 공평한 샘플을 유지할 수 있습니다.
정리하면:
전체 저장 불가 → 샘플 K개만 유지
새 데이터 등장 → 확률적으로 교체
최종 결과 → 모든 데이터가 같은 기회
Reservoir Sampling은 처음에는 확률이 낯설 수 있지만, 큰 로그나 실시간 스트림을 다룰 때 매우 유용한 아이디어입니다.