재배치 알고리즘 파이프라인 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 7·8이 포함되지 않는다

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 사본을 추가로 만든다. 실측으로 문서 한 개의 크기는 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/… 편집기 링크다 — 당시 실행 환경의 주소를 보존한 것으로, 최신 파일의 줄 번호를 가리키지는 않는다.

다시 재는 법