재배치 알고리즘 파이프라인 v0.6

본판 합본 method 3 + 1 + 2 + 5 + 4 + 7 + 8 + 6 이 한 문서를 어떻게 통과시키는지, 분기·되돌림·되부름까지 폈다. 왼쪽 여백은 그 단계가 거는 게이트와 되돌림 단위, 오른쪽 여백은 반복 상한이다.

위상 네 층 — 좌표를 건드리기 전에 굳힌다

freezeRelations 가 한 번 정하고 굳힌다. 옮기는 도중에 다시 재면 소속이 바뀌어 결과가 처리 순서에 의존한다. 이 층이 겹침 후보 넷을 가른다 — 움직이는 단위가 무엇이냐가 곧 무엇을 풀 수 있냐다.

위상을 굳히면 좌표는 정확히 풀린다

위상까지 탐색 변수로 열면 배치는 조합 최적화가 되어 다항시간에 못 푼다. 굳히면 남는 것은 1차원 좌표 문제이고, 그건 닫힌 해가 있다. 음수 갭이 곧 겹침이라 「겹친 것을 떼어 놓기」는 「갭 하한을 0 으로 두고 다시 나누기」와 같은 말이다.

게이트 — 후보가 스스로에게 거는 제동

②가 겹침 후보에만 있는 이유 — 자리를 다시 나누는 연산은 한 쌍을 떼어놓느라 원래 있던 쌍을 키울 수 있는데 ①은 그것을 못 잡는다(쌍 자체는 있던 것이라서).

판정 — 무엇이 SUCCESS 인가

겹침을 푸는 후보가 넷이고, 넷을 가르는 것은 두 축이다 — 층(유닛 안 / 유닛 사이)과 이동축(세로 / 가로). 4·7 이 같은 칸에 앉는 것이 §5 에서 따질 중복이다.

① 진짜 중복 — method 4 의 2단계와 method 7 의 2-b

겹침 후보 넷 중 4 와 7 은 같은 칸에 앉아 있다(§3) — 같은 층(유닛 사이), 같은 축(세로), 같은 게이트 셋(①②③), 같은 MOVE_EPS·OVERLAP_EPS. 각각의 「짝 밀기」를 나란히 놓으면 관계가 분명해진다.

② 코드 중복 — 고쳐야 할 셋

③ 흐름의 비대칭 — 축소 뒤에 스프레드가 다시 안 돈다

method 6 은 배율을 한 칸 줄일 때마다 앞의 다섯을 되부른다(options.relayout). 그런데 본판 합본이 넘기는 되부름 함수는 3+1+2+5+4 뿐이다 — 7·8 이 빠져 있다.

의도된 것일 수 있다 — 되부름을 한 겹으로 묶어 「배율 위에 배율」을 막는 규율이 있고, 7·8 을 넣으면 되부름 비용이 다시 배가 된다. 다만 결과적으로 축소된 판에서는 스프레드가 최신이 아니다. betterOf 가 그 손해를 사후에 걸러내므로 안전하지만 최적은 아닌 구조다 — 적어 둘 값어치가 있는 트레이드다.

기호 — N = 전체 노드 수, L = leaf 노드 수, U = 유닛 수, P = 겹친 쌍 수, k = 한 행/클러스터의 셀 수, g = 한 체인의 갭 수, M = method 6 의 배율 칸 수(≤ 10).

6.1 시간

6.2 공간

지배 요인은 문서 복제다. 모든 후보가 structuredClone(input) 으로 시작하고 (run(doc): Doc 계약이 「입력을 건드리지 않는다」이므로), 되풀이마다 trial 을 한 벌 더 뜬다. 실측으로 doc 한 벌이 JSON 기준 중앙값 39.1KB · p90 83.2KB · 최대 174.1KB 다 (객체 그래프는 그보다 몇 배).

6.3 실제로 몇 번 타나 1,177건 전건 실행 · 2026-08-28

복잡도의 상한과 실제 비용은 다르다. 코퍼스 전건에 후보를 태워 각 후보의 리포트를 집계했다 — 발동(그 후보가 할 일을 찾음)과 실제 조치(문서를 실제로 바꿈)를 나눠 셌다.

단독 = 후보 하나를 rendered.json 에 바로 태웠을 때. 합본 = 본판 3+1+2+5+4+7+8+6 안에서 그 패스가 한 일. 원안이 있는 1,177건 전건, 예외 0건. ⚠️ 단독 method 2 는 세 번째 트리거(collided)를 못 받는다 — 그 값은 합본이 만들어 넘기므로 단독 수치가 그만큼 낮게 잡힌다.

6.4 분업이 실측으로 확인된다

§4 에서 코드로 보인 배타적 분업이 숫자로도 나온다. 각 후보는 자기 몫이 아닌 쌍을 세어서 넘긴다 — 그 계량기를 집계한 값이다.

단독 실행에서 7·8 이 실제로 옮긴 케이스를 갈라 보면 — 7만 옮김 394건 · 8만 옮김 25건 · 둘 다 옮김 8건 · 아무도 안 옮김 750건. 「둘 다」 8건은 모순이 아니다 — 한 문서 안의 서로 다른 쌍을 각자 맡은 것이다. 분업은 케이스 단위가 아니라 쌍 단위다.

method 8 이 실제로 맡는 쌍은 중앙값 1쌍 · 최대 10쌍(75건에서만 대상이 생긴다). 가로 침투가 진짜인 겹침은 드물고, 그래서 method 8 의 조치율이 2.3%로 가장 낮다 — §5 에서 「7 이 4 를 포함한다」고 본 것과 달리, 8 은 대체 불가능하되 사정권이 좁은 특수 연산자다.

정리하면 — 선택 층은 지금 「두 갈래 · 스프레드 합본 한정」까지만 와 있다. 전 후보를 대상으로 하는 층은 설계로만 존재하고, 그 설계에서 method 7·8 은 선택 대상의 일부일 뿐이다.

지표 ④ idleMarginRatio 는 「여백이 얼마나 남았나」만 답하는 페이지 전역 스칼라였고, 후보들이 쓰는 여유는 전부 국소적이었다 — neighbors.ts 는 좌·우 이웃의 한계선, gapAlgebra.ts 는 한 체인의 1차원 갭. 「어디에 남았나」를 답하는 자리가 없어서 겹침을 옮겨 풀 후보가 밀 자리를 찾지 못했다.

넘침은 조건이 아니다. 이것이 v0.5 와의 가장 큰 차이다 — 기존 후보들은 「텍스트가 넘쳤을 때」 발동했고, 그래서 넘침 없이 겹침만 남은 케이스에는 아무도 손대지 않았다. 발동에 「신규 겹침 존재」가 결합돼 있어 원안부터 여백이 큰 미니멀 디자인을 멀쩡한데 건드리는 일은 없다 — τ 는 예산의 하한이지 목표가 아니다.

v0.6 에서 가장 값진 발견은 새 연산자가 아니라 「자(판정 박스)의 불일치」였다. 후보 안쪽에서는 엔진이 잰 값을 못 얻으므로 frameBoxesAsTight 로 노드 박스를 그 자리에 끼워 쓴다. 그런데 성적표는 실측 tight 로 잰다 — 두 자가 다르면 후보가 유령 겹침을 쫓는다.

지금 코퍼스 2026-08-28 직접 셈

eval-out/cases/*/case.json 을 직접 세어 얻은 값이다. before(대치 직후)의 FAIL 사유는 신규 겹침 843 · 넘침 709 · 유휴 11 로 갈린다(한 케이스가 여러 사유를 가진다).

후보 성적표 111건 · 2026-08-26 · 낡음

읽는 법 — 넘침은 3+1+2 에서 87% 가 사라진다. 거기서 게이트가 43/111 밖에 안 되는 것은 넘침과 겹침이 다른 문제이기 때문이다. +4 가 유닛 사이를, +5+4 가 유닛 안까지 푼다 — 그 셋은 넘침이 한 자리도 안 다르다(「넘침이 늘면 되돌린다」가 게이트라서). 마지막 +6 만 글자를 줄이므로 넘침까지 지우지만, 대가로 SUCCESS 는 한 건도 안 는다.

method 7·8 의 기여 96건 · 2026-08-27 · 낡음

FAIL 17 → 12(−29%) · 신규 겹침 59 → 42쌍(−29%) · 나빠진 케이스 0건. §4 의 분업이 실측으로 확인된다 — 5628689 는 B 만이, 5611182·5694141·5698092·6377108 은 A 가 풀었고, A+B 는 정확히 둘의 합집합이다. 겹치는 일을 했다면 합집합보다 작았을 것이다. 자세한 설계·평가는 유휴 여백 재배치 설계 에 있다.

아래 링크는 vscode://file/… 편집기 링크다 — 이 커밋(aee07d0b)이 원격에 없어 GitHub permalink 가 서지 않는다.

다시 재는 법