배가 실험으로 숨은 이차를 찾고 고친다

목표

입력을 두 배씩 늘려 재는 배가 실험으로 함수 다섯 개의 증가율을 가르고, 가장 흔한 숨은 이차(중복 제거)를 순서를 지키며 고친 뒤, 개선을 반복 측정의 분포로 증명하고 목표 크기에서의 시간을 외삽합니다.

왜 중요한가

작은 입력에서는 이차 함수도 빠르기 때문에 테스트는 통과하고 운영에서만 느려집니다. 한 번 잰 숫자는 잡음 하나와 구별되지 않고, 코드 모양만 보고 한 판단은 한 줄짜리 in 을 놓칩니다. 그래서 크기를 바꿔 가며 반복해서 재고, 증가율은 최솟값끼리의 비율로, 개선은 중앙값과 분포의 겹침으로 말합니다. 채점기는 시간 자체는 넓은 띠로만 보고, 여러분이 적은 중앙값·비율이 여러분의 표본에서 나왔는지와 개선한 함수가 원본과 같은 답을 내는지를 정확히 봅니다.

재료

/opt/fixtures/svccs/measure/ 아래에 있습니다. 읽기만 하세요.

suspects.py   함수 다섯 개(dedupe · newest_first · pack · flag_known · window_pairs)
              SUSPECTS[이름] → 함수, make_input(이름, n, seed=0) → 크기 n 의 입력(고정 시드)
params.json   sizes(함수마다 잴 네 크기, 두 배씩) · repeat_min(최소 반복 수 5)
              compare_sizes(7단계 크기) · target_n · budget_s(8단계 외삽 목표와 예산, 초)

불러 쓰는 법: sys.path.insert(0, "/opt/fixtures/svccs/measure") 뒤에 import suspects.

단계

/root/svccs/measure/clock.json 에 perf_counter 와 time 두 시계의 성질을 적습니다. 각각 {"monotonic", "adjustable", "resolution", "implementation"} 이고 값은 time.get_clock_info(이름) 그대로입니다. 그리고 구간을 잴 시계를 "choice" 에 "perf_counter" 또는 "time" 으로 적습니다.
/root/svccs/measure/bench.py 에 time_it(fn, make_input, n, repeat=7) 를 만듭니다. 반복마다 data = make_input(n) 으로 입력을 새로 만들고, 그 뒤에 time.perf_counter() 로 fn(data) 한 번의 시간을 잽니다. {"n", "repeat", "samples"(초 목록, 길이 repeat), "median"(statistics.median), "min"} 을 돌려줍니다.
params.json 의 sizes 에 있는 함수마다, 그 네 크기를 순서대로 time_it 으로 5번 이상 재서 /root/svccs/measure/doubling.json 에 {"functions": {이름: [{"n", "samples", "median", "min"}, …]}} 로 적습니다. 입력은 suspects.make_input(이름, n) 입니다.
/root/svccs/measure/ratios.json 에 함수마다 {"ratios", "ratio", "exponent"} 를 적습니다. ratios 는 이웃한 두 크기의 min 끼리 나눈 비율 세 개(작은 n 부터, 소수 셋째 자리), ratio 는 그 세 비율(반올림 전)의 중앙값(셋째 자리), exponent 는 log2(ratio)(둘째 자리)입니다.
/root/svccs/measure/classes.json 에 다섯 함수를 "linear" 또는 "quadratic" 으로 분류합니다(예: {"dedupe": "…", …}).
/root/svccs/measure/fixed.py 에 dedupe_fast(items) 를 만듭니다. suspects.dedupe 와 같은 값을 같은 순서로 돌려주되 선형이어야 합니다. 받은 목록을 고치지 않고, 문자열이 아닌 해시 가능한 값도 받아야 합니다.
compare_sizes 의 크기마다 suspects.dedupe(before)와 fixed.dedupe_fast(after)를 같은 입력 생성기(make_input("dedupe", n))로 각각 5번 이상 재서 /root/svccs/measure/compare.json 에 {"rows": [{"n", "before": {"samples", "median"}, "after": {"samples", "median"}, "speedup", "separated"}]} 로 적습니다. speedup 은 before 중앙값 ÷ after 중앙값(둘째 자리), separated 는 after 의 가장 큰 표본이 before 의 가장 작은 표본보다 작은지(true/false)입니다.
/root/svccs/measure/forecast.json 에 외삽을 적습니다. 7단계 가장 큰 n 의 행을 쓰고, exponent_before 는 4단계의 dedupe 지수, before_s = before 중앙값 × (target_n ÷ n) ** exponent_before(셋째 자리), after_s = after 중앙값 × (target_n ÷ n)(다섯째 자리), fits_before·fits_after 는 각각 budget_s 이하인지, 그리고 target_n·budget_s 를 그대로 적습니다.

참고

측정은 파드가 CPU 를 다른 작업과 나눠 쓰는 동안 이뤄집니다. 5단계에서 "측정이 분류를 받쳐 주지 않는다" 는 말이 나오면 3단계부터 다시 재세요.
채점기는 bench.py·fixed.py 를 불러옵니다. 실행 코드는 if __name__ == "__main__": 아래나 별도 스크립트에 두세요.
흔한 실수: 입력 만들기까지 시간에 넣는 것, 한 번만 재는 것, 중앙값 자리에 평균을 적는 것, 중복 제거를 set() 으로 바꿔 순서를 잃는 것.
산출물은 세션이 끝나면 사라집니다. 필요하면 따로 보관하세요.

구간을 잴 시계를 고른다

time.get_clock_info 로 perf_counter 와 time 두 시계의 monotonic·adjustable·resolution·implementation 을 /root/svccs/measure/clock.json 에 적고, 구간 측정에 쓸 시계를 choice 에 적는다.

time.get_clock_info('perf_counter') 가 돌려주는 객체의 속성 네 개를 그대로 옮기면 됩니다. adjustable 이 true 인 시계는 NTP 나 관리자가 시계를 되돌릴 때 함께 뒤로 갈 수 있어서, 두 번 읽은 차이가 음수가 될 수 있습니다.

반복해서 재는 측정 도구

/root/svccs/measure/bench.py 에 time_it(fn, make_input, n, repeat=7) 를 만든다. 채점기가 느린 make_input 과 짧은 fn 을 넣어, 입력을 반복마다 새로 만드는지와 입력 만들기를 시간에서 뺐는지 확인한다.

시계는 make_input 이 끝난 뒤, fn 을 부르기 직전에 읽습니다. 중앙값은 statistics.median, 최솟값은 min 입니다. 같은 입력을 여러 번 쓰면 입력을 고치는 함수는 두 번째부터 다른 일을 하게 됩니다.

입력을 두 배씩 늘려 잰다

params.json 의 sizes 에 있는 다섯 함수를 네 크기씩 time_it 으로 5번 이상 재서 /root/svccs/measure/doubling.json 에 functions → 이름 → [{n, samples, median, min}] 으로 적는다.

입력은 suspects.make_input(이름, n) 으로 만듭니다. 람다로 넘길 때 반복 변수 name 을 기본 인자로 묶지 않으면 모든 람다가 마지막 이름을 봅니다. 가장 큰 크기의 이차 함수는 한 번에 1초 가까이 걸릴 수 있습니다.

비율로 지수를 읽는다

doubling.json 에서 함수마다 이웃한 크기의 min 끼리 나눈 비율 세 개, 그 중앙값, log2 지수를 /root/svccs/measure/ratios.json 에 적는다. 채점기는 여러분의 표본에서 같은 규칙으로 다시 계산해 대조한다.

t(2n)/t(n) ≈ 2^k 이므로 k = log2(비율) 입니다. math.log 는 자연로그라 math.log2 를 씁니다. 증가율을 볼 때 min 을 쓰는 이유는 timeit 문서에 있습니다 — 큰 값들은 대개 다른 프로세스의 간섭입니다.

선형과 이차를 가른다

다섯 함수를 linear 또는 quadratic 으로 분류해 /root/svccs/measure/classes.json 에 적는다. 채점기는 설계 정답과 대조하고, 여러분의 측정이 그 분류를 넓은 띠 안에서 받쳐 주는지도 본다.

비율 2 근처는 선형, 4 근처는 이차입니다. 코드 모양으로 판단하지 마세요 — 이중 반복이어도 안쪽이 상수 번이면 선형이고, 한 줄짜리 in·insert(0, x)·반복 이어 붙이기가 이차를 숨깁니다.

순서를 지키며 중복 제거를 고친다

/root/svccs/measure/fixed.py 에 dedupe_fast(items) 를 만든다. 채점기가 변형 입력에서 원본과 같은 값·같은 순서인지, == 호출 수가 입력에 비례하는지, 20만 개에서 시간이 이차로 늘지 않는지 본다.

'이미 보았나' 를 list 가 아니라 해시 기반 구조로 물으면 선형이 됩니다. set 은 순서가 없는 모음이라 결과 순서가 바뀝니다. dict 는 삽입 순서를 지킵니다(3.7부터 언어 명세).

개선을 분포로 증명한다

compare_sizes 의 크기마다 dedupe 와 dedupe_fast 를 같은 입력 생성기로 5번 이상 재서 /root/svccs/measure/compare.json 에 before·after 표본과 중앙값, speedup, separated 를 적는다.

평균 한 쌍은 튀는 표본 하나에 끌려갑니다. 두 분포가 겹치지 않는다(after 의 가장 느린 값 < before 의 가장 빠른 값)는 것이 '잡음이 아니다' 의 가장 쉬운 증거입니다.

목표 크기로 외삽해 예산과 견준다

4단계의 dedupe 지수와 7단계 가장 큰 n 의 중앙값으로 target_n 에서의 개선 전후 시간을 외삽해 /root/svccs/measure/forecast.json 에 적고 budget_s 와 견준다.

t(target) ≈ t(n) × (target ÷ n)^k 입니다. 개선 후는 6단계에서 선형(k = 1)임을 확인했습니다. 외삽은 같은 증가율이 이어진다는 가정이라, 결과는 '대략 몇 자리 수인가' 로 읽으세요.