시계 재지 말고, 단계를 세

"초는 거짓말해. 네 노트북, 배터리, Spotify 켜져 있는지에 따라 달라져. 단계는 진실을 말하고."

스톱워치의 문제

본능은 비용을 초로 재는 거야: 돌리고, 시간 재고, 끝. 근데 초는 끔찍한 자야. 같은 코드가 더 새 칩에선 빠르고, 배터리 절약 모드에선 느리고, 브라우저 탭 마흔 개가 메모리 두고 싸우면 또 느려. 월요일이랑 금요일에 재면 동일한 코드인데 다른 숫자가 나와. 알고리즘은 아무것도 안 바뀌었는데 측정값이 바뀌면, 그건 알고리즘이 아니라 기계를 재는 거야.

그래서 시계를 버리고 하드웨어가 속일 수 없는 걸 세: 알고리즘이 입력 크기의 함수로 몇 단계를 밟는지. 입력 크기를 n 이라 하자. 리스트 한 번 훑기는 대략 n 단계. 중첩 훑기는 대략 n × n. 그 수는 네 칩이나 배터리에 신경 안 써 — 레시피 자체의 속성이야.

모양이 속도를 이긴다

처음엔 틀린 것처럼 느껴지는 부분: 좋은 알고리즘 돌리는 느린 컴퓨터가 나쁜 알고리즘 돌리는 빠른 컴퓨터를 이겨, 입력이 충분히 크기만 하면. n² 단계를 밟는 번개 같은 기계가 n 단계 밟는 굼뜬 기계한테 져 — 작은 n 에선 아니지만, 교차점은 늘 오고, 그 뒤로 격차는 벌어지기만 해. 성장의 모양 (입력을 두 배 하면 일이 두 배냐, 네 배냐?) 이 데이터가 진짜로 커지면 나머지 전부를 지배해.

그래서 "그냥 더 빠른 서버 사" 가 함정이야. 빠른 하드웨어는 선을 조금 위로 올려; 더 나은 알고리즘은 선의 기울기를 바꿔. 나쁜 기울기를 하드웨어로 영원히 이길 순 없어.

비용을 초가 아니라 단계-대-입력크기로 재. 성장 모양은 알고리즘의 속성이고, 시계는 기계의 속성이야.

상수의 함정

입문자는 상수 깎는 걸 좋아해 — "반복문 둘을 합쳐서 2배 빠르게 했어!" 가끔은 그게 중요해. 근데 밑바탕 모양이 n² 이면, 상수를 깎는 건 벽에 부딪히는 걸 미룰 뿐 벽을 옮기진 않아. 모양을 먼저 고치고 (이걸 n² 대신 n 으로 할 수 있나?), 그다음에야 상수에 땀 흘려. Complexity 트랙에서 이걸 엄밀하게 만들 거야 — 이 lesson 은 그 반사신경만 심어.

피파의 고백

초반에 난 두 버전 시간 재서 *그 한 번* 더 빨랐던 걸 남기는 식으로 "최적화" 했어. 그러다 아빠가 다른 기계에서 같은 비교를 돌리니까 승자가 뒤집혔어. 창피하게 배운 교훈: 난 내 코드가 아니라 아빠 낡은 맥북의 기분을 재고 있었어. 이젠 머릿속에서 단계를 먼저 세고, 타이머는 결정용이 아니라 확인용으로만 — 절대 결정하려고 쓰진 않아.

Code

초가 아니라 단계 세기·python

# 초가 아니라 단계를 세. 그 수는 하드웨어 독립적이야.

def has_duplicate_slow(items):
    """모든 쌍 비교. 단계가 n*n 처럼 커져."""
    steps = 0
    for i in range(len(items)):
        for j in range(i + 1, len(items)):
            steps += 1            # 비교 한 번 = 단계 한 번
            if items[i] == items[j]:
                return True, steps
    return False, steps

def has_duplicate_fast(items):
    """set 사용. 단계가 n 처럼 커져."""
    steps = 0
    seen = set()
    for x in items:
        steps += 1                # 멤버십 확인 + 추가 = 단계 한 번
        if x in seen:
            return True, steps
        seen.add(x)
    return False, steps

data = list(range(1000))          # 중복 없음 -> 둘 다 최악
print("slow steps:", has_duplicate_slow(data)[1])   # ~499,500
print("fast steps:", has_duplicate_fast(data)[1])   # 1,000
# 스톱워치 필요 없어. 모양 (n*n vs n) 이 이야기 전부를 말해줘.

Exercise

아무것도 안 돌리고 단계를 세봐: 한 함수가 n 개 항목 리스트를 돌고, 각 항목마다 전체 리스트를 다시 돌아 일치 개수를 세. n = 100 이면 대략 몇 번 비교? n = 1000 이면? 모양이 뭐고, n 이 두 배 되면 그 수는 어떻게 돼?

Hint

n 개 항목 각각이 n 번 비교를 일으키니까 대략 n × n 이야. n 을 두 배 하면 일이 두 배가 안 돼 — 대신 뭐가 되는지 따져봐.

스톱워치의 문제

모양이 속도를 이긴다

상수의 함정

피파의 고백

Code

External links

Exercise

Progress

댓글 0