いつから壊れたか — 64版を6回で絞る

목표

좋다·나쁘다·판정 불가를 가르는 기계 판정기를 만들고, 그것으로 빌드 이력 64판과 입력 자료 4096행을 각각 반씩 잘라 경계를 찾는다. 판정 불가를 비켜 가는 길과 경계를 전수로 검증하는 길까지 붙이고, 순차 탐색이었다면 몇 번이었을지를 함께 기록한다.

왜 중요한가

"지난주까지는 됐는데요" 와 "어제 파일에서만 죽어요" 는 같은 모양의 문제다. 경계가 하나 있고 앞뒤가 갈린다. 앞에서부터 하나씩 보면 64번과 4096번이지만, 반씩 자르면 여섯 번과 열두 번이다. 이 차이를 만드는 것은 도구가 아니라 판정기다. 사람이 화면을 보고 판단하는 절차가 섞이면 열 번을 반복할 수 없고, 다섯 번째쯤에서 자기가 어느 쪽을 좋다고 했는지 잊는다. 어려운 것은 반으로 자르는 코드가 아니라 경계 조건이다. 기동하지 않는 판을 나쁨으로 셈하면 범인이 앞으로 밀리고, 조각에서 머리글을 떼면 모든 조각이 실패해 1행을 가리키고, 중간에 고쳤다가 다시 깨진 이력에서는 답 자체가 틀린다. 채점기는 여러분의 문구를 믿지 않는다. 채점기가 만든 이력과 자료를 임시 디렉터리에 차려 놓고 여러분의 도구를 실제로 실행해, 경계가 맞는지와 몇 번 만에 찾았는지를 함께 잰다. 경계는 실행할 때마다 다른 자리에 있으므로 값을 외워 넣을 수 없다.

단계

1. /root/bisect/gen_history.py 를 만들어 실행해 빌드 이력 64판과 /root/bisect/ref.csv, /root/bisect/rows.csv, /root/bisect/loader.py 를 만드세요.
2. /root/bisect/judge.py 를 만들어 한 판을 good·bad·unknown 으로 가르게 하세요. 종료 코드는 각각 0, 1, 125 입니다.
3. /root/bisect/bisect_run.py 로 이력을 반씩 잘라 처음 나빠진 판을 찾고 /root/bisect/bisect_result.json 에 남기세요. 후보 63개는 여섯 번이면 끝납니다.
4. bisect_run.py 가 판정 불가를 만나면 이웃 판으로 비켜 다시 묻게 하고, 구간이 통째로 판정 불가면 한 판을 지목하지 않게 하세요.
5. /root/bisect/row_bisect.py 로 적재기를 죽이는 행을 찾아 /root/bisect/row_result.json 에 남기세요. 조각에는 머리글을 항상 붙입니다.
6. /root/bisect/probe_count.json 에 순차 탐색과 이분 탐색의 최악 횟수, 그리고 실제로 든 횟수를 나란히 적으세요.
7. /root/bisect/verify_bisect.py 로 경계를 전수 검증해 /root/bisect/verify_result.json 을 만드세요. 단조가 아닌 이력을 만나면 반례를 이름으로 적어야 합니다.
8. /root/bisect/summary.json 과 /root/bisect/bisect_report.md 에 네 절로 보고하세요.

참고

• 판정 계약: python3 /root/bisect/judge.py --rev <판 디렉터리> --input <csv> --expect <정수> 는 good·bad·unknown 중 한 낱말을 표준출력에 내고 종료 코드 0·1·125 로 끝납니다.
• 파이프라인 계약: python3 <판>/pipeline.py --in <csv> 는 total=<정수> 한 줄을 내고 0 으로 끝납니다. 기동하지 않는 판은 0 이 아닌 코드로 끝납니다.
• 탐색 계약: python3 /root/bisect/bisect_run.py --hist <이력 디렉터리> --input <csv> --expect <정수> --out <json> 은 first_bad·last_good·probe_count·probes·undecided 를 담은 JSON 한 덩어리를 냅니다. 판 이름은 디렉터리 이름 그대로(예: r41)입니다.
• 행 탐색 계약: python3 /root/bisect/row_bisect.py --csv <파일> --loader <적재기> --out <json> 은 bad_row(머리글을 뺀 1부터 세는 행 번호)·probe_count·rows 를 냅니다. 적재기는 python3 <적재기> <csv> 로 부르고 0 이 아닌 코드면 그 조각에 범인이 있습니다.
• 검증 계약: python3 /root/bisect/verify_bisect.py --hist <디렉터리> --input <csv> --expect <정수> --boundary <판 이름> --out <json> 은 boundary_bad·prev_good·monotone·contradictions·checked 를 냅니다.
• 횟수 계산: 후보 n 개의 순차 탐색 최악은 n 번, 이분 탐색 최악은 올림한 log2(n) 번입니다. 이력의 후보 수는 판의 수에서 하나를 뺀 값(첫 판은 좋다고 보고 시작하므로)이고, 자료의 후보 수는 행 수입니다.
• 흔한 실수: 판정 불가를 나쁨으로 접기, 조각에서 머리글 떼기, 경계를 찾고 검증하지 않기, 판정기를 만들기 전에 눈으로 탐색하기.
• 이 실습의 가정: 종료 코드 125 를 판정 불가로 쓰는 것은 git bisect run 의 규약을 그대로 빌린 것입니다. 표준이 정한 값은 아닙니다.
• 부하 시험을 만들지 마세요. 채점 하나의 예산은 60초이고 파드는 2코어입니다.

빌드 이력과 새 입력 손에 쥐기

/root/bisect/gen_history.py 를 만들어 실행해 빌드 이력 64판(/root/bisect/hist/r00 부터 r63)과 /root/bisect/ref.csv(300행), /root/bisect/rows.csv(4096행), /root/bisect/loader.py 를 만드세요.

현장에서 손에 쥐는 것은 코드가 아니라 자료입니다. 이 스크립트를 그대로 저장해 실행하면 됩니다. 마지막 줄에 나오는 expect 값(ref.csv 의 올바른 합계)은 뒤 단계에서 계속 쓰니 적어 두세요.

좋다와 나쁘다를 기계가 가르게 하기

/root/bisect/judge.py 를 만들어 판 하나를 good·bad·unknown 중 한 낱말로 판정하게 하세요. 종료 코드는 각각 0·1·125 이고, 기동하지 않는 판은 나쁨이 아니라 판정 불가입니다.

판정기는 그 판의 pipeline.py 를 실제로 돌려 total 값을 기대값과 견주는 프로그램입니다. 세 갈래를 분명히 하세요 — 돌아가고 값이 맞으면 good, 돌아가는데 값이 다르면 bad, 아예 못 돌거나 total 을 못 찾으면 unknown 입니다. 125 는 git bisect run 이 건너뛰기로 읽는 값입니다.

이력을 반씩 잘라 경계 찾기

/root/bisect/bisect_run.py 로 처음 나빠진 판을 찾고 결과를 /root/bisect/bisect_result.json 에 남기세요. first_bad·last_good·probe_count·probes·undecided 를 담아야 하고, 후보 63개를 60번 넘게 묻는다면 그것은 이분 탐색이 아닙니다.

알려진 좋은 자리 lo 와 알려진 나쁜 자리 hi 를 두고, 사이가 한 칸이 될 때까지 가운데를 물어 한쪽을 당깁니다. 양 끝을 먼저 확인해야 전제가 성립하는지 알 수 있습니다. 물어본 판 이름을 순서대로 모아 두면 probes 와 probe_count 가 그냥 나옵니다.

기동하지 않는 판 비켜 가기

bisect_run.py 가 판정 불가를 만나면 이웃 판으로 한 칸씩 비켜 다시 묻게 하고, 비켜 간 판 이름을 undecided 에 모으세요. 구간이 통째로 판정 불가면 한 판을 지목하지 말고 last_good 과 first_bad 로 남은 구간을 보고해야 합니다.

판정 불가를 나쁨으로 접으면 경계가 앞으로 밀려 무고한 판이 범인이 됩니다. 가운데가 판정 불가면 그 자리를 포기하고 mid-1, mid+1, mid-2 처럼 좌우로 한 칸씩 넓혀 가며 판정할 수 있는 이웃을 찾습니다. 구간 안에 판정 가능한 판이 하나도 없으면 그 구간이 답입니다 — 좁힌 것도 성과입니다.

적재기를 죽이는 행 찾기

/root/bisect/row_bisect.py 로 /root/bisect/rows.csv 의 어느 행이 적재기를 멈춰 세우는지 찾아 /root/bisect/row_result.json 에 bad_row·probe_count·rows 로 남기세요. bad_row 는 머리글을 뺀 1부터 세는 행 번호입니다.

이력과 원리가 같습니다. 앞에서부터 m 행까지만 담은 조각을 만들어 적재기에 물리고, 실패하면 범인은 그 안에 있습니다. 조각에는 머리글을 항상 붙이세요 — 떼면 뒤쪽 조각이 첫 자료 행을 열 이름으로 읽어 모든 조각이 실패합니다. 4096행이면 열두 번이면 충분합니다.

몇 번 만에 끝났는지 세기

/root/bisect/probe_count.json 에 history·rows·million 세 항목을 적으세요. 각 항목은 candidates·sequential_worst·bisect_worst 를 담고, history 와 rows 는 실제로 든 횟수 measured 도 담습니다. million 의 candidates 는 1000000 입니다.

순차 탐색의 최악은 후보 수 그대로이고, 이분 탐색의 최악은 올림한 log2(후보 수)입니다. 이력의 후보 수는 판의 수에서 하나를 뺀 값입니다 — 첫 판은 좋다고 보고 시작하니까요. measured 는 앞 단계가 남긴 JSON 의 probe_count 를 그대로 가져옵니다.

경계가 정말 경계인지 전수로 확인하기

/root/bisect/verify_bisect.py 로 경계 앞뒤를 전수 조사해 /root/bisect/verify_result.json 에 boundary_bad·prev_good·monotone·contradictions·checked 를 남기세요. 경계 뒤에 좋은 판이 있거나 경계 앞에 나쁜 판이 있으면 그 이름을 contradictions 에 적어야 합니다.

탐색은 로그지만 검증은 선형입니다. 모든 판을 한 번씩 돌려 good·bad·unknown 을 매기고, 경계 뒤의 good 과 경계 앞의 bad 를 모으면 그것이 단조가 깨진 증거입니다. 판정 불가는 반례가 아닙니다 — 따로 셉니다.

두 경계를 한 장으로 보고하기

/root/bisect/summary.json 에 revisions·first_bad·last_good·unknown·history_probes·rows·bad_row·row_probes·sequential_total·bisect_total 을 적고, /root/bisect/bisect_report.md 에 ## 무엇이 깨졌나 ## 어떻게 좁혔나 ## 몇 번 만에 ## 남은 위험 네 절로 보고하세요.

sequential_total 은 두 순차 최악의 합이고 bisect_total 은 실제로 든 두 횟수의 합입니다. 보고서에는 처음 나빠진 판 이름과 범인 행 번호, 그리고 두 숫자를 모두 적으세요. 고객이 사는 것은 결론이 아니라 절차입니다.