Page 28 -

프로그램 4.1.2 두 배 가설의 검증 (doublingtest.py)
import sys
import stdarray
import stdio
import stdrandom
import threesum
from stopwatch import Stopwatch 4

# 크기 n의 난수에서 합이 0이 되는 세 수를 찾아내는 데 걸리는 시간
def timeTrial(n): 알고리즘과 데이터 구조
a = stdarray.create1D(n, 0)
for i in range(n): n 문제 크기
a[i] = stdrandom.uniformInt(-1000000, 1000000) a[] 정수 난수들
watch = Stopwatch() watch 스톱워치
count = threesum.countTriples(a)
return watch.elapsedTime()
n 문제 크기
n = int(sys.argv[1]) previous n // 2의 실행 시간
while True: current n의 실행 시간
previous = timeTrial(n // 2) ration 실생 시간의 배율
current = timeTrial(n)
ratio = current / previous
stdio.writef('%7d %4.2f\n', n, ratio)
n *= 2

이 프로그램은 합이 0이 되는 세 수를 찾는 문제의 크기를 두 배씩 증가시키면서 실행 시간의 배
율을 표준 출력 장치에 표로 출력한다. 이 표를 보면 문제 크기를 두 배로 증가시킬 때 threesum.
countTriples() 함수가 실행하는 데 걸리는 시간의 영향을 보여준다. 이 프로그램을 실행하면
입력 크기가 두 배가 되면 실행 시간이 8배 늘어난다는 가설에 도달하게 한다. 프로그램을 실행
할 때 각 메시지가 출력되는 시간이 8배 정도 늘어나므로, 이 가설을 검증할 수 있다.

% python3 doublingtest.py 256
256 7.52
512 8.09
1024 8.07
2048 7.97
...

481