빅오는 외우지 말고 두 배로 늘려 잰다

한 줄 요약

"이 함수는 O(n) 이다" 는 외워서 말하는 것이 아니라 재서 말하는 것입니다. 입력을 두 배로 늘렸을 때 시간이 몇 배가 되는지 보면 숨은 이차가 드러나고, 반복해서 잰 분포를 보면 "빨라졌다" 가 잡음인지 개선인지 가를 수 있습니다.

왜 이게 필요했나

스테이징에서 100건으로 0.1ms 걸리던 중복 제거가 운영에서 5만 건을 만나 몇 초가 되는 일은 흔합니다(예시). 코드는 한 줄도 바뀌지 않았고, 테스트는 모두 초록불이었습니다. 작은 입력에서는 이차 함수도 빠르기 때문입니다. 문제는 "얼마나 빠른가" 가 아니라 "입력이 늘 때 어떻게 늘어나는가" 이고, 그 질문에는 한 번의 측정으로 답할 수 없습니다.

거꾸로 코드 모양만 보고 판단해도 틀립니다. 이중 반복인데 안쪽이 늘 세 번이면 선형이고, 반복문 없이 if x not in seen: 한 줄인데 seen 이 list 면 그 한 줄이 목록을 처음부터 훑습니다. TimeComplexity 위키는 CPython 기준으로 list 의 x in s·insert·중간 원소 pop 을 O(n), set 의 x in s 를 평균 O(1)(최악 O(n))으로 적어 둡니다. 여기서 n 은 컨테이너에 지금 든 원소 수이고, 반복문 안에서 불리면 곱해집니다.

어떻게 동작하나

배가 실험. 걸리는 시간이 대략 c·n^k 라면 t(2n)/t(n) ≈ 2^k 입니다. 비율이 2 근처면 선형, 4 근처면 이차, 8 근처면 삼차입니다. 지수는 log2(비율) 로 읽습니다. n log n 은 한 번 두 배로 늘릴 때 2 를 조금 넘을 뿐이라 이 방법으로는 선형과 가르기 어렵고, 이 실습은 선형과 이차만 가릅니다. 크기는 n, 2n, 4n, 8n 처럼 여러 번 늘려 비율 세 개를 얻고, 그 중앙값을 대표로 씁니다 — 한 쌍만 보면 잡음 하나가 결론을 뒤집습니다.

시계. time.perf_counter 는 짧은 구간을 재도록 가장 높은 해상도를 주는 시계이고, 두 번 읽은 값의 차이만 의미가 있습니다. CPython 에서는 뒤로 가지 않는(monotonic) 시계입니다. 반면 time.time() 은 시스템 시계가 뒤로 조정되면 이전보다 작은 값을 돌려줄 수 있다고 문서에 적혀 있습니다. 어떤 시계가 조정 가능한지는 time.get_clock_info() 의 adjustable·monotonic 으로 직접 물어볼 수 있습니다.

반복과 대표값. 같은 코드를 일곱 번 재면 일곱 개의 다른 숫자가 나옵니다. timeit 문서는 반복 결과의 평균과 표준편차를 내는 것이 별로 쓸모없다고 말합니다. 가장 작은 값이 그 기계가 그 코드를 돌릴 수 있는 하한이고, 큰 값들은 대개 파이썬이 아니라 다른 프로세스의 간섭 때문이라는 이유입니다. 그래서 이 실습은 코드 자체의 증가율을 볼 때(배가 비율) 최솟값끼리 나눕니다. 반면 개선 전후를 비교해 보고할 때는 중앙값과 분포를 함께 적습니다. statistics.median 문서의 표현대로 중앙값은 튀는 값에 덜 흔들리는 대표값이고, 두 분포가 겹치지 않는다(개선 후의 가장 느린 표본이 개선 전의 가장 빠른 표본보다 빠르다)는 것은 평균 한 쌍보다 훨씬 강한 증거입니다. timeit 은 기본으로 재는 동안 가비지 컬렉션을 끄고, 반복 기본값은 5 입니다.

측정 도구가 지켜야 할 것이 하나 더 있습니다. 입력을 만드는 시간은 재지 않습니다. 선형으로 입력을 만드는 시간이 섞이면 이차 함수의 비율이 4 보다 작게 나와 이차가 가려집니다. 그리고 입력을 고치는 함수가 있으니 반복마다 입력을 새로 만듭니다.

숨은 이차 세 가지. list 에 대한 in, list.insert(0, x), 그리고 불변 시퀀스를 반복해서 이어 붙이기입니다. 공통 시퀀스 연산 문서는 불변 시퀀스를 이어 붙이면 늘 새 객체가 생기므로 반복 이어 붙이기는 전체 길이에 대해 이차 비용이 든다고 적고, str 은 str.join() 이나 io.StringIO, bytes 는 bytes.join()·io.BytesIO·bytearray 를 대안으로 듭니다. str 의 a += b 는 CPython 이 최적화해 주는 경우가 있지만, PEP 8 은 그 최적화가 CPython 에서도 깨지기 쉽고 참조 계수를 쓰지 않는 구현에는 아예 없으니 기대지 말라고 합니다. 이 실습이 str 대신 bytes 를 재는 이유입니다.

고칠 때 지킬 것. 중복 제거를 list(set(items)) 로 바꾸면 빨라지지만 set 은 순서가 없는 모음이라 결과 순서가 바뀝니다. dict 는 3.7부터 삽입 순서 보존이 언어 명세이므로 dict.fromkeys(items) 는 처음 나온 순서를 지킵니다. 빨라진 함수가 다른 답을 내면 개선이 아니라 버그입니다.

현장에서 만나는 모습

성능 개선 PR 에 "로컬에서 한 번 재 보니 12% 빨라짐" 이라고 적혀 있다면 그 숫자는 아직 아무것도 증명하지 않습니다. 같은 조건에서 몇 번 쟀는지, 전후 분포가 겹치는지, 그리고 입력이 열 배가 되면 어떻게 되는지를 함께 물어야 합니다. 배가 실험으로 지수를 얻으면 "지금 8천 건에 0.2초면 10만 건에는 몇 초인가" 를 외삽할 수 있고, 그 숫자를 예산과 견주어 지금 고칠지 정합니다. 외삽은 같은 증가율이 이어진다는 가정 위에 있어서, 데이터가 CPU 캐시를 넘어서는 지점에서는 비율 자체가 바뀔 수 있습니다 — 그 이야기는 '컴퓨터 구조' 코스가 합니다. 어디가 느린지 찾는 프로파일링(cProfile 의 tottime·cumtime)은 'CPU·메모리 누수 판별' 코스가, 서비스 전체에 부하를 걸어 백분위로 회귀를 판정하는 일은 '부하 테스트' 코스가 다룹니다. 이 모듈은 그 사이에서 함수 하나의 증가율을 재는 자리입니다.

다음 실습에서 할 것

두 시계의 성질을 파드에 직접 물어본 뒤, 반복·중앙값·최솟값을 내는 측정 도구를 만듭니다. 복잡도가 숨은 함수 다섯 개를 네 크기로 재서 비율과 지수를 구하고 선형과 이차로 가릅니다. 가장 흔한 이차인 중복 제거를 순서를 지키며 고치고, 개선 전후를 분포로 비교한 뒤, 10만 건에서 몇 초가 걸릴지 외삽해 예산과 견줍니다.