열 개에서 즉시, 십만 개에서 한 시간Instant at Ten Items, an Hour at a Hundred Thousand

"빅데이터"는 사실 크기를 두고 하는 말이 아닙니다. 만족스럽게 쓰던 알고리즘이 더 이상 끝나지 않는 지점을 두고 하는 말입니다. 500행짜리 파일럿에서 눈 깜짝할 새 끝나던 절차가 50만 행에서는 다음 날 아침까지 돌고 있을 수 있습니다. 원인은 거의 항상 하드웨어가 아닙니다.

"Big data" is not really about size. It is about the point where an algorithm you were happy with stops finishing. A procedure that runs in a blink on a pilot sample of 500 rows can still be running the next morning on the full 500,000 — and the reason is almost never the hardware.

이 편은 그걸 직접 잽니다. 일부러 순진하게 짠 정렬 루틴을 여러 입력 크기에서 시간 재고 나온 곡선을 이론과 맞춰 봅니다.

This post measures it directly. We take a deliberately naive sorting routine, time it across a range of input sizes, and check the resulting curve against theory.

중요한 구분The distinction that matters

복잡도 등급은 입력이 커질 때 비용이 어떻게 자라는지를 기술합니다. 두 알고리즘이 작은 입력에서는 둘 다 "빠르"면서 나중에 크게 갈라질 수 있습니다.

Complexity classes describe how the cost of an algorithm grows as the input grows. Two algorithms can both be "fast" on small inputs and diverge wildly later.

배경에 깔린 P 대 NP 문제는 답을 검증하기 쉬운 모든 문제가 답을 찾기도 쉬운가를 묻습니다. 아직 미해결이고 실무적으로는 아니라고 보고 움직입니다. 매일의 함의는 이렇습니다. 최적 부분집합 선택, 다수 공변량 정확 매칭, 외판원 형태의 경로 문제 같은 것들에는 빠른 정확해가 없습니다. 더 큰 장비로 밀어붙일 생각 대신 근사를 쓰십시오.

The P vs NP question in the background asks whether every problem whose solution can be verified quickly can also be solved quickly. It is unresolved, and the working assumption is no. What that means day to day: for certain problems — optimal subset selection, exact matching on many covariates, travelling-salesman-shaped routing — nobody has a fast exact algorithm, so reach for an approximation rather than assuming a bigger machine will do.

이차 알고리즘을 재 보기A quadratic algorithm, measured

버블 정렬은 좋은 표본입니다. 같은 리스트를 두 겹으로 순회하니 비용이 코드에서 바로 보입니다. 비교 횟수가 대략 n²/2입니다.

Bubble sort is a good specimen because its cost is obvious from the code: two nested loops over the same list, so roughly n²/2 comparisons.

import numpy as np
import matplotlib.pyplot as plt
import random

def bubble_sort(n):
    values = list(range(n))
    random.shuffle(values)
    for i in range(n - 1):
        for j in range(i + 1, n):
            if values[i] > values[j]:
                values[i], values[j] = values[j], values[i]
    return values

%timeit bubble_sort(10)

21.1 µs ± 970 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)

n = 10에서 21마이크로초. 즉시입니다. 여기에는 문제가 있다는 신호가 없고 그게 바로 함정입니다. 측정 한 번은 확장성에 대해 아무것도 말해 주지 않습니다. 곡선이 필요합니다.

At n = 10 it takes 21 microseconds. Instant. Nothing here suggests a problem, and that is exactly the trap. A single measurement tells you nothing about scaling. You need the curve.

sizes = [10, 50, 100, 200, 500, 1000]
timings = []

for n in sizes:
    result = %timeit -o -q bubble_sort(n)
    timings.append(np.mean(result.timings))

for n, t in zip(sizes, timings):
    print(f"n={n:>5}  {t*1000:>9.3f} ms")

n=   10      0.022 ms
n=   50      0.281 ms
n=  100      0.884 ms
n=  200      3.040 ms
n=  500     23.400 ms
n= 1000    103.000 ms

절대 숫자가 아니라 비율을 읽으십시오. 절대값은 기계에 따라 달라지지만 비율은 그렇지 않습니다.

Read the ratios rather than the absolute numbers, because the absolute numbers depend on the machine and the ratios do not.

• n: 100 → 200 (데이터 2배), 시간: 0.884ms → 3.04ms (3.4배)
• n: 200 → 500 (데이터 2.5배), 시간: 3.04ms → 23.4ms (7.7배, 이론값 6.25배)
• n: 500 → 1000 (데이터 2배), 시간: 23.4ms → 103ms (4.4배)

• n: 100 to 200 (2x the data), time: 0.884ms to 3.04ms (3.4x)
• n: 200 to 500 (2.5x the data), time: 3.04ms to 23.4ms (7.7x, theory says 6.25x)
• n: 500 to 1000 (2x the data), time: 23.4ms to 103ms (4.4x)

두 배마다 대략 네 배가 듭니다. 이차 함수의 서명이고 측정값에서 바로 보입니다.

Every doubling costs roughly four times as much. That is the quadratic signature, visible directly in the measurements.

피해 규모 외삽하기Extrapolating the damage

측정은 n = 1000에서 멈추지만 맞춘 곡선은 그럴 필요가 없습니다. n = 1000에서 103ms라면 이차 성장은 이렇게 예측합니다.

The measurements stop at n = 1000, but the fitted curve does not have to. At 103 ms for n = 1000, quadratic growth predicts:

• n = 10,000 → 약 10초
• n = 100,000 → 약 17분
• n = 1,000,000 → 약 29시간

• n = 10,000: about 10 seconds
• n = 100,000: about 17 minutes
• n = 1,000,000: about 29 hours

한편 파이썬 내장 sorted()는 O(n log n)이고 100만 개를 1초 안에 처리합니다. 차이는 두 배 수준이 아닙니다. 100만 개에서 대략 다섯 자릿수 차이이고 하드웨어를 바꿔도 좁혀지지 않습니다. 곡선의 모양이 다르기 때문입니다. 열 배 빠른 기계로도 세 시간이 필요합니다.

Meanwhile Python built-in sorted() is O(n log n) and handles a million items in well under a second. The gap is not a factor of two — at a million items it is roughly five orders of magnitude, and no amount of faster hardware closes it because the curves have different shapes. A machine ten times faster still needs three hours.

계량 작업에서 이차 비용이 숨는 자리Where quadratic cost hides in empirical work

쌍별 연산이 대개 범인입니다. 성향점수 매칭은 처치군의 모든 단위를 대조군의 모든 단위와 비교하므로 O(n_처치 × n_대조)입니다. 거리 행렬, 공간 가중 행렬, "가장 가까운 이웃 찾기" 루프가 전부 위장한 이차입니다. 5만 단위에서 완전 거리 행렬은 25억 개 항목이고 float64로 약 20GB입니다. 뒤에 나오는 매칭 편이 완전 비교 대신 k-d 트리와 캘리퍼 제한을 쓰는 이유입니다.

Pairwise operations are the usual culprit. Propensity score matching that compares every treated unit to every control is O(n_treated x n_control). Distance matrices, spatial weight matrices and "find the nearest neighbour" loops are all quadratic in disguise. On 50,000 units a full distance matrix is 2.5 billion entries, around 20 GB in float64. This is why the matching post later in the series uses k-d trees and caliper restrictions rather than exhaustive comparison.

부트스트랩과 순열검정은 모든 것을 곱합니다. 1만 회 부트스트랩은 추정량을 1만 번 돌립니다. 추정량이 O(n²)이면 전체는 O(10,000 n²)입니다. 전체를 돌리기 전에 한 번만 시간을 재 보십시오. 밤샘 작업을 여러 번 살려 준 습관입니다.

Bootstrap and permutation tests multiply everything. A bootstrap with 10,000 replications runs your estimator 10,000 times. If the estimator is O(n²), the bootstrap is O(10,000 n²). Time a single replication before launching the full run — a habit that has saved many overnight jobs.

병합이 조용히 이차가 됩니다. 유일하지 않은 키로 Pandas 조인을 하면 결과 행 수가 양쪽 그룹 크기의 곱이 됩니다. 키가 양쪽에서 1,000번씩 반복되면 그 그룹에서만 100만 행이 나옵니다. 병합 전에 df.duplicated(subset=key).sum()을 확인하고 병합 후에 모양을 확인하십시오.

Merges quietly become quadratic. A Pandas join on a non-unique key produces rows equal to the product of matching group sizes. If a key repeats 1,000 times on each side, those groups alone yield a million rows. Check df.duplicated(subset=key).sum() before, and the shape after.

실무에서In practice

• 최적화 전에 프로파일링하십시오. 병목을 짐작하면 대개 틀립니다. 표현식 하나면 %timeit, 함수 전체면 %prun이나 cProfile, 함수 안 어느 줄인지 봐야 하면 line_profiler. 엉뚱한 5%를 최적화하는 것이 오후를 날리는 가장 흔한 방법입니다.
• 언제 상관없는지도 아십시오. n = 200에서 O(n²) 루틴은 영원히 괜찮습니다. 복잡도 분석은 절벽이 어디인지 알려 주는 것이지 모든 루프를 다시 쓰라는 말이 아닙니다. 파이프라인의 어느 부분이 큰 n을 만나고 어느 부분이 안 만나는지 알아보는 것이 기술입니다.
• 전체 데이터로 돌리기 전에 두세 가지 크기의 표본으로 돌려 비율을 보십시오. 1분이면 되고 전체 작업이 커피 한 잔인지 애초에 불가능한지 알려 줍니다. 이 시리즈는 시뮬레이션과 재표본추출을 많이 쓰는데, 설계가 실행 가능한지 미리 아는 가장 싼 방법입니다.

• Profile before optimising. Guessing at bottlenecks is unreliable. %timeit for a single expression, %prun or cProfile for a whole function, and line_profiler when you need to see which line inside it. Optimising the wrong 5% is the most common way to waste an afternoon.
• Know when it does not matter. An O(n²) routine on n = 200 is fine, forever. Complexity analysis tells you where the cliff is, not that every loop needs rewriting. The skill is recognising which parts of a pipeline will meet a large n and which will not.
• Run on a sample at two or three sizes first and look at the ratio. It takes a minute and tells you whether the full job is a coffee break or a non-starter. This series does a lot of simulation and resampling, and this is the cheapest way to know in advance whether a design is feasible.