원래 문제: https://gist.github.com/MetaFibonacci/bf74a547e4814a9be5b526743c208197


1. 코드


1) 문제코드(+조금 수정)


import random import statistics import math def incrementalRandom(N): x, y=(0, 0) for i in range(N): while x>=y: y=random.random() x=y return x def showResult(N,n): vals=[incrementalRandom(N) for i in range(n)] print(math.log2(1-statistics.mean(vals))) showResult(6, 1000) def test_func1(benchmark): benchmark(showResult, 6, 1000)



2) 제출 코드


import random import statistics import math def incrementalRandom(N): x, y = (0, 0) for i in range(N): y=x+random.random()*(1-x) x=y return x def averageIncRand(N, n): vals=[incrementalRandom(N) for i in range(n)] return statistics.mean(vals) def showResult(N, n): print(math.log2(1-averageIncRand(N,n))) showResult(6,1000) def test_func1(benchmark): benchmark(showResult,6,1000)



2. 결과&벤치마크(시행 기기: 라즈베리파이4(BCM2835))

*문제코드 (N=6, 1,000회 반복)




*제출코드 (N=6, 1,000회 반복)


*제출코드 (N=6, 1000,000회 반복)




문제 코드에서 x<y일때까지 y를 반복해서 추출하는 부분만 y를 새 분포에서 1번씩 추출하는 식으로 바꿈

대충 방향은 출제의도에 맞게 잡은 것 같긴 한데, 절대오차 10^(-6)이하로 0.1초이내라는 기준은 못 맞춤

-N을 정답으로 잡고 오차 확인해 봤는데, 100만번을 반복해서 평균을 내도 기준보다 높게 나옴

나는 여기까지가 한계