무작위 알고리즘: 확실성을 속도와 맞바꾸기

"가끔은 동전 던지기가 가장 똑똑한 수야. 무작위성은 적이 노릴 최악 입력을 비켜 가게 해 주고, 정확한 답을 계산할 수 없을 때 답을 샘플링하게 해 줘. 확실성을 조금 내주면 속도를 두둑이 사 오는 거래야."

버그가 아니라 도구로서의 무작위성

무작위성은 고정된 입력과 알고리즘의 선택 사이 상관을 끊어. 무작위 퀵소트가 기대 O(n log n)을 얻는 이유가 그거야. 물론 최악의 O(n²)은 여전히 존재해. CPython은 조작된 충돌 공격을 어렵게 하려고 많은 문자열 해시에 실행마다 다른 salt를 섞는데, 이건 런타임의 방어이지 모든 해싱의 보편 성질이 아니야. 그리고 샘플링은 정확한 계산이 불가능할 때만이 아니라, 가능하긴 해도 너무 비싸고 통제된 추정으로 충분할 때도 유용해.

무작위 알고리즘의 두 갈래

Las Vegas: 늘 정확한 답을 반환하지만 실행 시간이 무작위야. 무작위 퀵소트가 정석이지. 출력은 언제나 정렬돼 있고 속도만 운에 달렸어. 그것도 기댓값으로는 훌륭하고. 틀린 답을 받는 일은 절대 없어. 가끔 더 느린 실행을 받을 뿐.
Monte Carlo: 실행 시간에 상한을 두는 대신 오차 확률이나 근사 오차를 허용해. 모든 입력에서 정확히 같은 고정 시간이라는 뜻은 아니고, 반복 횟수나 표본 수로 시간과 오차를 맞바꿔.

내 보장이 어느 쪽인지, 그러니까 늘 맞지만 느릴 수 있는 쪽인지 늘 빠르지만 틀릴 수 있는 쪽인지 아는 것이, 그 무작위 알고리즘을 지금 용도에 써도 안전한지를 알려 줘.

무작위성은 입력과 선택의 상관을 끊고, 샘플링으로 시간과 정확도를 맞바꿔. Las Vegas는 답은 항상 정확하고 실행 시간이 확률적이야. Monte Carlo는 실행 시간 상한과 맞바꿔 오차 가능성이나 근사 오차를 허용해.

보석: 저수지 샘플링

가장 우아한 무작위 알고리즘은 저수지 샘플링(reservoir sampling)이야. 길이를 모르는, 어쩌면 거대한 스트림에서 균일한 무작위 항목 하나를 O(1) 공간, 단 한 번의 패스로 뽑아. 트릭은 이래. 현재 픽을 하나 들고 있다가, i번째 항목이 도착하면 확률 1/i로 픽을 그 항목으로 교체해. 스트림이 끝나는 순간, 첫 번째 항목이든 십억 번째 항목이든 전부 똑같은 확률로 뽑혔다는 게 증명돼. 메모리에 안 들어가는 파일에서 무작위 한 줄을, 끝없는 피드에서 무작위 로그 항목 하나를 뽑는 방법이 바로 이거야. 변수 하나, 패스 한 번, 완벽한 균일성, 스트림 길이는 몰라도 됨.

피파의 고백

저수지 샘플링은 내 직관을 부쉈어. 변수 하나만 들고 총 개수를 본 적도 없는데, 어떻게 십억 개 스트림 항목 하나하나가 똑같이 뽑힐 수 있어? 아빠가 1/i 교체 확률을 한 단계씩 짚어 줬고, 대수를 따라가니 정확히 균일로 떨어졌어. 완전히 아귀가 맞을 때까지 그 앞에 앉아 있었지. 무작위성은, 정확하게 쓰면, 전역 지식 없이도 공정함을 보장할 수 있어. 깊은 교훈이야. 잘 고른 무작위성 한 꼬집은 예측 불가능성, 균일성, 기대 속도 같은 속성을, 어떤 결정론적 트릭도 그만큼 싸게 못 주는 값에 사다 줘.

Code

저수지 샘플링과 Monte Carlo pi·python

import random

# 저수지 샘플링: 알 수 없는 길이 스트림에서 균일 무작위 항목 하나.
# O(1) 공간, 한 패스 — 그리고 전체 스트림에 증명 가능하게 균일.
def reservoir_sample(stream):
    pick = None
    for i, item in enumerate(stream, start=1):
        # 현재 픽을 확률 1/i 로 교체
        if random.randint(1, i) == 1:
            pick = item
    return pick
# 스트림이 끝나면, 모든 항목이 동등한 1/n 기회를 가졌어 — n 을
# 미리 알지도 못하고. 변수 하나, 한 패스.

# Monte Carlo: 무작위 샘플링으로 pi 추정 (고정 일, 근사 답).
def estimate_pi(samples):
    inside = 0
    for _ in range(samples):
        x, y = random.random(), random.random()
        if x*x + y*y <= 1.0:        # 사분원 안?
            inside += 1
    return 4 * inside / samples     # 면적 비율 -> pi 근사
# 샘플 많을수록 -> 더 가까운 추정. 정확성을 빠른 근사랑 맞바꿈.

# (정렬 트랙의 무작위 퀵소트가 Las Vegas 정석:
#  무작위 피벗이 O(n^2) 최악 케이스를 실질적 불가능으로.)

Exercise

*무작위* 피벗이 왜 퀵소트의 O(n²) 최악 케이스를 실질적으로 불가능하게 만드는지 설명해 봐. 그 최악이 기술적으로는 여전히 존재하는데도 말이야. 무작위 퀵소트는 Las Vegas야, Monte Carlo야? 왜? 그리고 저수지 샘플링에서 픽을 확률 1/i로 교체하는 게 왜 모든 항목에게 똑같은 최종 확률을 주는지도.

Hint

무작위 피벗이면 어떤 특정 입력도 나쁜 분할을 안정적으로 일으킬 수 없어. 공격자가 선택을 예측할 수 없으니, 최악 케이스가 나오려면 천문학적으로 운 나쁜 무작위성이 필요해. 무작위 퀵소트는 Las Vegas야. 언제나 올바르게 정렬하고 실행 시간만 무작위니까. 저수지는 i번째 항목이 1/i로 채택된 뒤 이후의 모든 교체를 (i/(i+1))·…·((n−1)/n) 확률로 살아남아서, 곱하면 모든 항목이 1/n으로 telescoping 돼.

버그가 아니라 도구로서의 무작위성

무작위 알고리즘의 두 갈래

보석: 저수지 샘플링

피파의 고백

Code

External links

Exercise

Progress

댓글 0