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

"가끔 가장 똑똑한 수는 동전 던지기야. 무작위성이 적이 이용할 최악-케이스 입력을 피하고, 정확한 답 계산이 불가능할 때 답을 샘플링하게 해. 확실성을 조금 포기하면 속도를 많이 사."

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

보통 결정론을 원하지 — 근데 일부러 무작위성을 주입하는 게 초능력 둘 있는 진짜 알고리즘 전략이야. 첫째, 적대적 입력을 물리쳐: 고정-피벗 퀵소트는 적이 정렬 데이터로 일으킬 최악 케이스가 있는데, 무작위 피벗은 예측 못 해, 그래서 O(n²) 케이스가 입력과 무관하게 천문학적으로 불가능해져. (Python 이 문자열 해시를 소금 치는 이유도 — 조작된 해시 충돌을 막으려.) 둘째, 샘플링을 가능케 해: 정확한 답 계산이 불가능할 때, 무작위 샘플이 좋은 추정을 빠르게 줘.

무작위 알고리즘 두 맛

Las Vegas: 늘 정확한 답을 반환하지만, 실행시간이 무작위. 무작위 퀵소트가 정석 — 출력은 늘 정렬됨; 속도만 운에 달림 (그리고 기댓값으로 훌륭). 틀린 답은 절대 안 받고, 가끔 더 느린 실행만.
Monte Carlo: 고정 시간에 돌지만 작고 제어 가능한 확률로 틀릴 수 있어. Miller-Rabin 소수 판정이 '아마 소수' 를 말하는데, 반복으로 어떤 임계값 아래로 오차를 몰 수 있어. 작은 오차 가능성을 보장된 속도랑 맞바꿔.

어떤 보장인지 — 늘-맞고-느릴-수도 vs 늘-빠르고-틀릴-수도 — 아는 게 무작위 알고리즘이 네 용도에 안전한지 알려줘.

무작위성은 도구야: 적대적 최악 케이스를 물리치고 (무작위 피벗, 소금 친 해시), 정확한 계산이 불가능할 때 샘플링을 가능케 해. 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