시계 재지 말고, 단계를 세

"초는 거짓말을 해. 어떤 노트북인지, 배터리가 얼마나 남았는지, 음악을 틀어놨는지에 따라 달라지니까. 단계는 거짓말을 안 하고."

스톱워치의 문제

비용을 재라고 하면 본능은 초를 집어들어. 돌리고, 시간 재고, 끝. 그런데 초는 자로 쓰기엔 형편없어. 같은 코드가 새 칩에서는 빠르고, 절전 모드에서는 느리고, 브라우저 탭 마흔 개가 메모리를 두고 싸우면 또 느려져. 월요일에 재고 금요일에 다시 재면 같은 코드인데 숫자가 달라. 알고리즘은 그대로인데 측정값이 흔들린다면, 재고 있는 건 알고리즘이 아니라 기계야.

그래서 시계를 내려놓고 하드웨어가 속일 수 없는 걸 세. 입력 크기에 따라 알고리즘이 몇 단계를 밟는가. 입력 크기를 n이라고 하자. 리스트를 한 번 훑으면 대략 n단계. 중첩해서 훑으면 대략 n × n. 이 수는 어떤 칩인지, 배터리가 얼마인지 신경 쓰지 않아. 레시피 자체의 성질이거든.

모양이 속도를 이긴다

처음엔 틀린 말처럼 들리는 대목이야. 입력만 충분히 크면 좋은 알고리즘을 돌리는 느린 컴퓨터가 나쁜 알고리즘을 돌리는 빠른 컴퓨터를 이겨. n²단계를 밟는 번개 같은 기계가 n단계를 밟는 굼뜬 기계한테 져. 작은 n에서는 아니지만, 교차점은 반드시 오고 그다음부터는 격차가 벌어지기만 해.

성장의 모양이 나머지 전부를 지배하는 거야. 입력을 두 배로 하면 일이 두 배가 되는지 네 배가 되는지, 데이터가 진짜로 커지면 그것만 남아. "그냥 더 빠른 서버 사"가 함정인 이유도 여기 있어. 빠른 하드웨어는 선을 조금 위로 올려. 더 나은 알고리즘은 선의 기울기를 바꾸고. 나쁜 기울기를 하드웨어로 영원히 이길 수는 없어.

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

상수의 함정

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

피파의 고백

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

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