파이썬으로 Coupon collector's problem 코딩 해보기

자고로 배웠으면 써먹어야지.

Coupon collector's problem은 쉽게 말해 "장난감 N가지를 모두 모으고 싶은데 하나 살때마다 들어있는건 랜덤이다. 평균 몇번을 사야 다 모을수 있을까?"이다. 분명 이걸 노린 오덕 아이템이 있는 걸로 알고 있는데 (포켓몬?) 내가 덕력이 부족하여 더 나은 비유를 들 수가 없네.

자세한건 여기와 여기를 보자. 참고로 이미 이론적 정답은 다 나와있다. 조화급수에 N을 곱하면 됨.

간단한 예로 주사위를 던져 모든 숫자가 적어도 한번씩 나오도록 해보자. 

import random

import time

t0 = time.time()

Ntries = 100000

NN = []

for i in range(0,Ntries):

    a = range(1,7)

    N = 0

    while 1:

        try:

            a.remove(random.randrange(1,7))

        except:

            pass

        finally:

            N+=1

        if sum(a)==0:

            break

    NN.append(N)

t1 = time.time()

print float(sum(NN))/len(NN)

print "elapsed time: %0.4f (s)" % (t1-t0)

결과야 예상대로 14.7 근처에서 나온다. 하지만 시간이 맘에 안 든다. 10만번 반복에 2.2초 정도 나오는데 더 줄일 수 있을 것 같다. 가장 마지막에 배운 try/except를 써봤는데 왠지 저기서 시간을 먹을 것 같다. 그래서 다음처럼 바꿔봄.

import random

import time

t0 = time.time()

Ntries = 100000

NN = []

for i in range(0,Ntries):

    a = range(1,7)

    N = 0

    while 1:

        a[random.randrange(0,6)] = 0

        N+=1

        if sum(a)==0:

            break

        NN.append(N)

t1 = time.time()

print float(sum(NN))/len(NN)

print "elapsed time: %0.4f (s)" % (t1-t0)

1.7초로 줄었다! 

혹시나 싶어서 NN을 NN = [0 for i in range(0,Ntries)]로 초기화 해봤는데 거의 차이가 나지 않는다. matlab과 달리 행렬 크기 늘리는건 시간 부담이 없나보다. (아님 꼴랑 10만칸 밖에 안돼서 그런가?)

여기서 더 줄일수 있을라나?

====

파이썬.

확실히 문법이 간단하긴 하다. 아직 초보이긴 하지만, matlab만큼 쉽다는 게 헛소리는 아닌 듯 하다. 게다가 공짜. (맞지?) matlab을 제외한 다른 스크립트 언어를 하나 알아둬야겠다고 생각은 해왔는데, 파이썬이 좋은 선택지가 될 것 같기도 하다. 하지만 사정상 C++를 관둘 수가 없다는게 함정

그나저나, 최근에 산 책을 보니 처음 보는 내용들이 있네;; 대충 배웠나.

- 함수의 input argument 개수를 임의로 할 수도 있다는데, 혹시 *args를 말하는 건가?

- Glob()

- md5(), uuid()

- atexit module

- late binding (여기도)

- s.isalpha(), s.isdigit(), s.isspace()

- xrange

참고로 저 책은 정말 쓰레기 같은 책이다. 책의 90%는 딱 한 문장으로 요약할 수 있다. "Python is fucking good."