개념 확인: Running Time and Operation Counts

Timer(lambda: f(5000)).repeat(repeat=5, number=20)의 결과가 다음과 같다(단위: 초).

[0.0124, 0.0118, 0.0131, 0.0120, 0.0122]

1. 다섯 묶음의 중앙값을 구한다.
2. 중앙값을 함수 한 번 호출당 시간으로 바꾸고 마이크로초(μs)로 나타낸다.
3. 한 번만 실행해 재지 않고 여러 호출을 묶어 여러 번 재는 이유를 적는다.

다음 비교마다 시간 차이를 코드의 차이로 해석할 수 없는 이유와 바로잡는 방법을 적는다.

1. 함수 A의 측정문은 매번 파일에서 숫자를 읽어 목록을 만든 뒤 합을 구했고, 함수 B는 setup에서 목록을 만든 뒤 합만 쟀다.
2. 함수 A는 컴퓨터가 쉬고 있을 때, 함수 B는 같은 컴퓨터에서 동영상 변환 프로그램이 도는 동안 쟀다.
3. 함수 A는 원소 50,000개인 목록, 함수 B는 원소 500개인 목록으로 쟀다.
4. 함수 B가 A보다 빠르지만 빈 목록을 넣으면 오류가 난다.

반복 제어와 반환은 제외하고 명시적인 대입만 센다. n = len(a)다.

total = 0
squares = 0
for x in a:
    total = total + x
    squares = squares + x * x
    last = x

1. 반복문 밖과 반복문 안의 대입 수를 나누어 T(n)을 적는다.
2. a = [1, 2, 3, 4]와 a = []일 때 대입 수를 각각 구한다.
3. 같은 코드에서 곱셈만 세기로 하면 T(n)이 어떻게 바뀌는지 적고, 연산 수를 적기 전에 어떤 연산을 셀지 먼저 정해야 하는 이유를 설명한다.
4. 대입 수가 T(n) = 2 + 3n인 이 코드와 T(n) = n + 1인 다른 코드의 실행 시간 비율을 대입 수의 비로 단정할 수 있는지 적는다.

각 코드에서 count += 1이 실행되는 횟수를 식으로 적고, 주어진 크기에서 값을 구한다. a의 길이는 m, b의 길이는 n이다.

# (가) m = 6, n = 4
for x in a:
    count += 1
for y in b:
    count += 1

# (나) n = 6
for i in range(n):
    for j in range(n):
        count += 1

# (다) n = 6
for i in range(n):
    for j in range(i):
        count += 1

# (라) n = 6
for i in range(n):
    for j in range(4):
        count += 1

# (마) n = 6과 n = 7
for i in range(0, n, 3):
    count += 1

(나)~(라)가 모두 두 겹 반복문인데 횟수가 다른 이유를 한 문장으로 적는다. (가)에서 a만 두 배로 늘리면 횟수가 얼마가 되는지도 적는다.

한 컴퓨터에서 없는 값 −1을 찾는 -1 in a를 같은 방법으로 쟀다. a에는 0부터 n − 1까지의 정수가 들어 있고 값은 호출당 중앙값(μs)이다.

1. n이 1,000에서 100,000으로 100배 커질 때 list와 dict의 시간이 각각 대략 몇 배가 되는지 적는다.
2. dict의 0.021과 0.022 차이를 자료구조의 차이로 해석하기 어려운 이유를 적는다.
3. 찾는 값을 −1 대신 0으로 바꾸면 list 측정이 왜 다른 실험이 되는지 설명한다.
4. 원소 n개인 목록을 만드는 두 함수를 쟀다. append를 쓰는 함수는 n = 10,000에서 0.6 ms, 20,000에서 1.2 ms였고, 반복마다 a = a + [i]로 새 목록을 만드는 함수는 180 ms, 720 ms였다. n이 두 배일 때 각 시간이 몇 배가 되었는지 적고, 두 번째 함수가 더 빠르게 늘어난 이유를 적는다.
5. 길이를 유지하며 삭제를 반복 측정했더니 pop(0)의 시간만 목록 길이에 따라 크게 늘었다. 그 이유를 적는다.