"""5장 실습: 어텐션과 Transformer 를 맨바닥부터.

하는 일
  1. 스케일드 내적 어텐션을 직접 구현하고, 본문의 손계산(토큰 3개 · 차원 2)을 그대로 계산한다.
  2. 왜 √d_k 로 나누는지 실험한다 (차원별 q·k 의 분산, 소프트맥스가 얼마나 쏠리는지).
  3. 마스크(열쇠 패딩 마스크 · 어텐션 마스크)가 가중치를 0 으로 만드는 것을 확인한다.
  4. 다중 머리 어텐션을 직접 구현하고, 같은 가중치를 넣은 nn.MultiheadAttention 과 출력이 같은지 확인한다.
  5. 자기 어텐션이 토큰의 순서를 모른다는 것(순열 등변성)을 숫자로 확인한다.
  6. 사인 위치 인코딩(1차원 · 2차원)을 만들고 그림으로 본다.
  7. Transformer 인코더 층(post-norm · pre-norm)을 구현하고 nn.TransformerEncoderLayer 와 대조한다.
  8. "색으로 찾기" 과제: 학습되는 질의 3개가 교차 어텐션 한 층으로 빨강 · 초록 · 파랑 도형의 중심을 맞힌다.
     시드 5개로 학습해 어텐션 지도를 그리고(시드에 따라 "도형을 보는" 풀이와 "도형만 빼고 보는" 풀이가 나온다),
     위치 인코딩을 뺀 모델과 비교한다.
  9. 토큰 수 N 에 따른 자기 어텐션 시간을 잰다 (CPU 스레드 하나로).

실행
  python ch05_attention.py            # 본문 결과 (노트북 GPU 약 2분)
  python ch05_attention.py --quick    # 연기 시험 (CPU 로 40초 안쪽)

이 파일은 rf_shapes.py(도형 세상)만 가져다 쓴다. 다른 장의 실습 파일은 이 파일을 불러오지 않는다
(직접 구현한 어텐션이 PyTorch 내장 nn.MultiheadAttention 과 같은 계산이라는 것을 여기서 확인해 둔다).
"""

from __future__ import annotations

import argparse
import math
import os
import time

import matplotlib

matplotlib.use("Agg")
import matplotlib.pyplot as plt
import numpy as np
import torch
import torch.nn as nn
import torch.nn.functional as F

from rf_shapes import PALETTE, render_scene, sample_scene


def get_device() -> str:
    if torch.cuda.is_available():
        return "cuda"
    if torch.backends.mps.is_available():
        return "mps"
    return "cpu"


# --8<-- [start:sdpa]
def scaled_dot_product_attention(q, k, v, mask=None):
    """스케일드 내적 어텐션: softmax(Q Kᵀ / √d_k) V.

    q: (..., N_q, d_k)  질의 N_q 개
    k: (..., N_k, d_k)  열쇠 N_k 개
    v: (..., N_k, d_v)  값 N_k 개 (열쇠와 짝을 이룬다)
    mask: (..., N_q, N_k) 로 넓혀질 수 있는 bool 텐서. True 인 자리는 "보지 못하게" 막는다.

    돌려주는 값: 출력 (..., N_q, d_v), 가중치 (..., N_q, N_k) — 가중치의 각 행은 합이 1.
    """
    d_k = q.shape[-1]
    scores = q @ k.transpose(-2, -1) / math.sqrt(d_k)  # (..., N_q, N_k): 질의마다 모든 열쇠와의 내적
    if mask is not None:
        scores = scores.masked_fill(mask, float("-inf"))  # exp(-inf) = 0 → 가중치가 정확히 0
    weights = torch.softmax(scores, dim=-1)  # 행(질의)마다 열쇠 방향으로 소프트맥스
    return weights @ v, weights  # 값의 가중 평균
# --8<-- [end:sdpa]


# --8<-- [start:hand]
def hand_example():
    """본문의 손계산: 토큰 3개, 차원 2. 질의 = 열쇠 = 값 = 토큰 그대로(자기 어텐션, 투영 없음)."""
    x = torch.tensor([[2.0, 0.0], [0.0, 2.0], [1.0, 1.0]])  # (3, 2)
    scores = x @ x.T  # (3, 3): 내적 표
    out, weights = scaled_dot_product_attention(x, x, x)
    torch.set_printoptions(precision=4, sci_mode=False)
    print("[손계산] 내적 Q Kᵀ =\n", scores)
    print("[손계산] √d_k 로 나눈 점수 =\n", scores / math.sqrt(2))
    print("[손계산] 가중치 A =\n", weights)
    print("[손계산] 출력 A V =\n", out)
    return x
# --8<-- [end:hand]


# --8<-- [start:scale]
def scale_experiment(dims=(4, 16, 64, 256, 1024), trials=20000, n_keys=16, seed=0):
    """성분이 표준 정규 분포인 q, k 를 뽑아 (1) 내적의 분산 (2) 소프트맥스의 쏠림을 잰다.

    쏠림은 열쇠 n_keys 개에 대한 가중치에서 '가장 큰 가중치' 와 '엔트로피' 의 평균으로 잰다.
    가중치가 고르면 최대 가중치 = 1/n_keys, 엔트로피 = log(n_keys). 한 곳에 쏠리면 최대 가중치 → 1, 엔트로피 → 0.
    """
    gen = torch.Generator().manual_seed(seed)
    rows = []
    for d in dims:
        q = torch.randn(trials, 1, d, generator=gen)  # (trials, 1, d): 질의 하나씩
        k = torch.randn(trials, n_keys, d, generator=gen)  # (trials, n_keys, d)
        scores = (q @ k.transpose(1, 2)).squeeze(1)  # (trials, n_keys): 나누기 전의 내적
        row = {"d": d, "var_raw": scores.var().item(), "var_scaled": (scores / math.sqrt(d)).var().item()}
        for name, s in (("raw", scores), ("scaled", scores / math.sqrt(d))):
            p = torch.softmax(s, dim=-1)
            row["max_" + name] = p.max(dim=-1).values.mean().item()
            row["ent_" + name] = -(p * torch.log(p.clamp_min(1e-30))).sum(-1).mean().item()
        rows.append(row)
    return rows
# --8<-- [end:scale]


# --8<-- [start:mask]
def mask_examples(x):
    """마스크 두 가지. True = 막는다."""
    # (1) 열쇠 패딩 마스크: 세 번째 토큰이 '채우기용 빈 토큰' 이라고 하자 → 모든 질의가 그 열쇠를 못 본다.
    key_padding = torch.tensor([False, False, True])  # (N_k,)
    _, w_pad = scaled_dot_product_attention(x, x, x, mask=key_padding[None, :])  # (1, N_k) → (N_q, N_k) 로 넓혀짐
    print("[마스크] 세 번째 열쇠를 가린 가중치 =\n", w_pad)

    # (2) 어텐션 마스크: 질의 4개를 두 묶음 {0, 1}, {2, 3} 으로 나누고, 다른 묶음은 서로 못 보게 한다.
    group = torch.tensor([0, 0, 1, 1])
    attn_mask = group[:, None] != group[None, :]  # (4, 4): 묶음이 다르면 True
    tokens = torch.randn(4, 8, generator=torch.Generator().manual_seed(0))
    _, w_group = scaled_dot_product_attention(tokens, tokens, tokens, mask=attn_mask)
    print("[마스크] 묶음 마스크 =\n", attn_mask.int())
    print("[마스크] 묶음끼리만 보는 가중치 =\n", w_group)
# --8<-- [end:mask]


# --8<-- [start:mha]
class MultiHeadAttention(nn.Module):
    """다중 머리 어텐션. 입력 · 출력 모두 (B, N, D) — 배치가 맨 앞이다.

    D 차원을 머리 h 개로 나눠(머리마다 d_k = D / h 차원) 머리마다 따로 어텐션한 뒤 다시 이어 붙인다.
    매개변수는 투영 넷(W_Q, W_K, W_V, W_O)뿐이고, 저마다 D × D 가중치와 길이 D 의 편향을 가진다.
    """

    def __init__(self, dim: int, num_heads: int):
        super().__init__()
        assert dim % num_heads == 0, "dim 은 머리 수로 나누어떨어져야 한다"
        self.dim, self.num_heads, self.head_dim = dim, num_heads, dim // num_heads
        self.q_proj = nn.Linear(dim, dim)  # W_Q: 머리 h 개의 (D → d_k) 투영을 한 행렬에 쌓은 것
        self.k_proj = nn.Linear(dim, dim)  # W_K
        self.v_proj = nn.Linear(dim, dim)  # W_V
        self.out_proj = nn.Linear(dim, dim)  # W_O: 이어 붙인 머리들을 다시 섞는다

    def split_heads(self, x):
        """(B, N, D) → (B, h, N, d_k). 마지막 축 D 를 (h, d_k) 로 쪼개고 머리 축을 앞으로 보낸다."""
        b, n, _ = x.shape
        return x.view(b, n, self.num_heads, self.head_dim).transpose(1, 2)

    def forward(self, query, key, value, key_padding_mask=None, attn_mask=None):
        """query (B, N_q, D), key · value (B, N_k, D).

        key_padding_mask: (B, N_k) bool — True 인 열쇠는 아무도 보지 못한다(그림마다 다른 패딩).
        attn_mask: (N_q, N_k) bool — True 인 (질의, 열쇠) 쌍을 막는다(모든 그림 · 모든 머리에 공통).
        돌려주는 값: 출력 (B, N_q, D), 머리별 가중치 (B, h, N_q, N_k).
        """
        b, n_q, _ = query.shape
        q = self.split_heads(self.q_proj(query))  # (B, h, N_q, d_k)
        k = self.split_heads(self.k_proj(key))  # (B, h, N_k, d_k)
        v = self.split_heads(self.v_proj(value))  # (B, h, N_k, d_k)

        mask = None  # 두 마스크를 (B, 1, N_q, N_k) 로 넓혀질 수 있는 하나로 합친다
        if key_padding_mask is not None:
            mask = key_padding_mask[:, None, None, :]  # (B, 1, 1, N_k)
        if attn_mask is not None:
            mask = attn_mask[None, None] if mask is None else mask | attn_mask[None, None]

        out, weights = scaled_dot_product_attention(q, k, v, mask)  # (B, h, N_q, d_k), (B, h, N_q, N_k)
        out = out.transpose(1, 2).reshape(b, n_q, self.dim)  # 머리들을 이어 붙인다: (B, N_q, h·d_k = D)
        return self.out_proj(out), weights
# --8<-- [end:mha]


# --8<-- [start:check-mha]
def copy_to_builtin(mine: MultiHeadAttention) -> nn.MultiheadAttention:
    """직접 만든 다중 머리 어텐션의 가중치를 PyTorch 내장 nn.MultiheadAttention 에 옮긴다.

    내장 모듈은 W_Q, W_K, W_V 를 세로로 쌓은 in_proj_weight (3D, D) 한 덩어리로 갖고 있다.
    """
    builtin = nn.MultiheadAttention(mine.dim, mine.num_heads, batch_first=True)
    with torch.no_grad():
        builtin.in_proj_weight.copy_(torch.cat([mine.q_proj.weight, mine.k_proj.weight, mine.v_proj.weight]))
        builtin.in_proj_bias.copy_(torch.cat([mine.q_proj.bias, mine.k_proj.bias, mine.v_proj.bias]))
        builtin.out_proj.weight.copy_(mine.out_proj.weight)
        builtin.out_proj.bias.copy_(mine.out_proj.bias)
    return builtin


def check_multi_head(seed=0):
    """d = 256, h = 8 에서 매개변수 수를 세고, 내장 모듈과 출력 · 가중치를 비교한다."""
    torch.manual_seed(seed)
    dim, heads = 256, 8
    mine = MultiHeadAttention(dim, heads).eval()
    builtin = copy_to_builtin(mine).eval()
    count = sum(p.numel() for p in mine.parameters())
    print(f"[다중 머리] 매개변수 수: 직접 구현 {count:,}, 내장 {sum(p.numel() for p in builtin.parameters()):,}"
          f" (손계산 4 × (256·256 + 256) = {4 * (256 * 256 + 256):,})")

    query = torch.randn(2, 5, dim)  # 질의 5개 (예: 객체 질의)
    memory = torch.randn(2, 12, dim)  # 열쇠 · 값 12개 (예: 그림 토큰)
    key_padding = torch.zeros(2, 12, dtype=torch.bool)
    key_padding[1, 9:] = True  # 둘째 그림의 마지막 토큰 3개는 패딩
    with torch.no_grad():
        out, weights = mine(query, memory, memory, key_padding_mask=key_padding)
        ref_out, ref_weights = builtin(query, memory, memory, key_padding_mask=key_padding,
                                       need_weights=True, average_attn_weights=False)
        print(f"[다중 머리] 교차 어텐션 모양: 출력 {tuple(out.shape)}, 가중치 {tuple(weights.shape)}")
        print(f"[check] nn.MultiheadAttention 과의 최대 차이: 출력 {(out - ref_out).abs().max().item():.2e},"
              f" 가중치 {(weights - ref_weights).abs().max().item():.2e}")
        print(f"[check] 패딩된 열쇠의 가중치 합: {weights[1, :, :, 9:].sum().item():.1f},"
              f" 가중치 행의 합(모두 1 이어야): 최소 {weights.sum(-1).min().item():.6f} 최대 {weights.sum(-1).max().item():.6f}")

        # 자기 어텐션 + 어텐션 마스크(질의 묶음 둘)도 대조한다
        x = torch.randn(2, 6, dim)
        group = torch.tensor([0, 0, 0, 1, 1, 1])
        attn_mask = group[:, None] != group[None, :]
        out2, _ = mine(x, x, x, attn_mask=attn_mask)
        ref2, _ = builtin(x, x, x, attn_mask=attn_mask, need_weights=False)
        print(f"[check] 어텐션 마스크를 준 자기 어텐션의 최대 차이: {(out2 - ref2).abs().max().item():.2e}")

        # F.scaled_dot_product_attention 과도 같은지 (머리 하나짜리로)
        q, k, v = torch.randn(3, 7, 32), torch.randn(3, 9, 32), torch.randn(3, 9, 32)
        ours, _ = scaled_dot_product_attention(q, k, v)
        print(f"[check] F.scaled_dot_product_attention 과의 최대 차이:"
              f" {(ours - F.scaled_dot_product_attention(q, k, v)).abs().max().item():.2e}")
    return mine
# --8<-- [end:check-mha]


# --8<-- [start:permutation]
def check_permutation(mine: MultiHeadAttention, seed=0):
    """자기 어텐션은 토큰을 섞어 넣으면 출력도 똑같이 섞여 나올 뿐이다(순열 등변성)."""
    gen = torch.Generator().manual_seed(seed)
    x = torch.randn(1, 10, mine.dim, generator=gen)  # 토큰 10개
    perm = torch.randperm(10, generator=gen)  # 섞는 순서
    with torch.no_grad():
        out, _ = mine(x, x, x)
        out_perm, _ = mine(x[:, perm], x[:, perm], x[:, perm])  # 섞어서 넣기
        diff = (out_perm - out[:, perm]).abs().max().item()  # "섞어 넣은 출력" 과 "출력을 섞은 것" 의 차이
        pos = sine_position_1d(10, mine.dim)[None]  # 위치 인코딩을 더하면?
        out_pos, _ = mine(x + pos, x + pos, x + pos)
        out_pos_perm, _ = mine(x[:, perm] + pos, x[:, perm] + pos, x[:, perm] + pos)
        diff_pos = (out_pos_perm - out_pos[:, perm]).abs().max().item()
    print(f"[순열] 섞는 순서 {perm.tolist()}")
    print(f"[순열] 위치 인코딩 없음: |f(PX) − P f(X)| 의 최댓값 = {diff:.2e}  (0 → 순서를 모른다)")
    print(f"[순열] 위치 인코딩 더함: 같은 차이 = {diff_pos:.3f}  (0 이 아님 → 순서가 출력을 바꾼다)")
# --8<-- [end:permutation]


# --8<-- [start:pos1d]
def sine_embed(position, dim: int, temperature: float = 10000.0):
    """실수 위치(임의 모양 (...))를 사인 · 코사인 dim 개로 바꾼다 → (..., dim).

    짝수 번째 성분 2i 는 sin(위치 · ω_i), 홀수 번째 성분 2i+1 은 cos(위치 · ω_i),
    각진동수 ω_i = 1 / temperature^(2i / dim)  (i = 0, 1, …, dim/2 − 1).
    """
    assert dim % 2 == 0
    i = torch.arange(dim // 2, dtype=torch.float32)
    omega = 1.0 / temperature ** (2 * i / dim)  # (dim/2,): 1 에서 시작해 점점 느려지는 각진동수
    angle = position[..., None].float() * omega  # (..., dim/2)
    return torch.stack([angle.sin(), angle.cos()], dim=-1).flatten(-2)  # sin, cos 를 번갈아 놓는다


def sine_position_1d(length: int, dim: int, temperature: float = 10000.0):
    """원 논문("Attention Is All You Need" 3.5절)의 위치 인코딩. 위치 0, 1, …, length−1 → (length, dim)."""
    return sine_embed(torch.arange(length), dim, temperature)
# --8<-- [end:pos1d]


# --8<-- [start:pos2d]
def sine_position_2d(height: int, width: int, dim: int, temperature: float = 10000.0, normalize: bool = True):
    """그림용 2차원 사인 위치 인코딩(DETR 방식) → (height · width, dim). 토큰 순서는 행 우선(위 줄부터 왼쪽 → 오른쪽).

    앞 절반 dim/2 개는 y(행) 좌표의 사인 인코딩, 뒤 절반 dim/2 개는 x(열) 좌표의 사인 인코딩이다.
    좌표는 1, 2, … 로 세고, normalize=True 면 (0, 2π] 범위로 바꾼다(격자 크기가 달라도 같은 범위를 쓰려고).
    """
    assert dim % 4 == 0
    y = torch.arange(1, height + 1, dtype=torch.float32)  # (H,)
    x = torch.arange(1, width + 1, dtype=torch.float32)  # (W,)
    if normalize:
        y, x = y / height * 2 * math.pi, x / width * 2 * math.pi
    pos_y = sine_embed(y, dim // 2, temperature)[:, None, :].expand(height, width, dim // 2)  # 같은 행은 같은 값
    pos_x = sine_embed(x, dim // 2, temperature)[None, :, :].expand(height, width, dim // 2)  # 같은 열은 같은 값
    return torch.cat([pos_y, pos_x], dim=-1).reshape(height * width, dim)
# --8<-- [end:pos2d]


# --8<-- [start:encoder-layer]
class EncoderLayer(nn.Module):
    """Transformer 인코더 층: 자기 어텐션 + FFN. 두 부분 모두 잔차 연결과 층 정규화로 감싼다.

    pre_norm=False (post-norm, 원 논문 · DETR):  x ← LN(x + 부분층(x))
    pre_norm=True  (pre-norm, ViT · DINOv2):      x ← x + 부분층(LN(x))
    입력 · 출력 (B, N, D). pos 를 주면 DETR 처럼 질의 · 열쇠에만 더한다(값에는 더하지 않는다).
    """

    def __init__(self, dim: int, num_heads: int, ffn_ratio: int = 4, pre_norm: bool = False):
        super().__init__()
        self.pre_norm = pre_norm
        self.attn = MultiHeadAttention(dim, num_heads)
        self.norm1 = nn.LayerNorm(dim)
        self.ffn = nn.Sequential(  # 토큰마다 따로 적용되는 2층 신경망: D → ffn_ratio·D → D
            nn.Linear(dim, ffn_ratio * dim), nn.ReLU(), nn.Linear(ffn_ratio * dim, dim)
        )
        self.norm2 = nn.LayerNorm(dim)

    def self_attention(self, x, pos, key_padding_mask):
        qk = x if pos is None else x + pos  # 질의 = 열쇠 = (토큰 + 위치), 값 = 토큰
        return self.attn(qk, qk, x, key_padding_mask=key_padding_mask)[0]

    def forward(self, x, pos=None, key_padding_mask=None):
        if self.pre_norm:
            x = x + self.self_attention(self.norm1(x), pos, key_padding_mask)
            x = x + self.ffn(self.norm2(x))
        else:
            x = self.norm1(x + self.self_attention(x, pos, key_padding_mask))
            x = self.norm2(x + self.ffn(x))
        return x
# --8<-- [end:encoder-layer]


def check_encoder_layer(seed=0):
    """EncoderLayer 를 같은 가중치의 nn.TransformerEncoderLayer 와 대조하고 매개변수 수를 센다."""
    torch.manual_seed(seed)
    dim, heads, ratio = 256, 8, 8  # FFN 은닉 2048 = 8 × 256 (RF-DETR 디코더의 dim_feedforward 와 같은 값)
    x = torch.randn(2, 20, dim)
    for pre_norm in (False, True):
        mine = EncoderLayer(dim, heads, ratio, pre_norm).eval()
        ref = nn.TransformerEncoderLayer(dim, heads, ratio * dim, dropout=0.0, activation="relu",
                                         batch_first=True, norm_first=pre_norm).eval()
        with torch.no_grad():
            builtin_attn = copy_to_builtin(mine.attn)
            ref.self_attn.load_state_dict(builtin_attn.state_dict())
            ref.linear1.load_state_dict(mine.ffn[0].state_dict())
            ref.linear2.load_state_dict(mine.ffn[2].state_dict())
            ref.norm1.load_state_dict(mine.norm1.state_dict())
            ref.norm2.load_state_dict(mine.norm2.state_dict())
            diff = (mine(x) - ref(x)).abs().max().item()
        name = "pre-norm " if pre_norm else "post-norm"
        print(f"[check] 인코더 층({name}) nn.TransformerEncoderLayer 와의 최대 차이: {diff:.2e}")
    parts = {
        "어텐션": sum(p.numel() for p in mine.attn.parameters()),
        "FFN": sum(p.numel() for p in mine.ffn.parameters()),
        "층 정규화 2개": sum(p.numel() for p in mine.norm1.parameters()) + sum(p.numel() for p in mine.norm2.parameters()),
    }
    print("[인코더 층] 매개변수 수 (D = 256, h = 8, FFN 2048): "
          + ", ".join(f"{k} {v:,}" for k, v in parts.items()) + f" → 합 {sum(parts.values()):,}")
    print(f"[인코더 층] 모양: 입력 {tuple(x.shape)} → 출력 {tuple(mine(x).shape)}")


# ───────────────────────── 색으로 찾기 과제 ─────────────────────────

COLOR_NAMES = ["red", "green", "blue"]
COLOR_RGB = PALETTE[[0, 3, 5]]  # 도형 세상 팔레트의 빨강 · 초록 · 파랑


# --8<-- [start:find-data]
def make_color_scenes(n: int, seed: int, size: int = 96, patch: int = 8):
    """빨강 · 초록 · 파랑 도형이 하나씩 있는 도형 세상 그림 n 장.

    돌려주는 값
      images  (n, 3, size, size) float32 0 – 1
      centers (n, 3, 2) float32: [빨강, 초록, 파랑] 도형의 중심 (cx, cy), 0 – 1 로 정규화
      on_obj  (n, 3, 패치 수) bool: 그 색 도형이 (조금이라도) 보이는 패치
    도형의 종류(원 · 사각형 · 삼각형) · 크기 · 위치는 무작위. 어느 도형이 어느 색인지도 무작위.
    """
    grid = size // patch
    images = np.zeros((n, 3, size, size), dtype=np.float32)
    centers = np.zeros((n, 3, 2), dtype=np.float32)
    on_obj = np.zeros((n, 3, grid * grid), dtype=bool)
    for i in range(n):
        rng = np.random.default_rng([seed, i])
        objects = sample_scene(rng, 3, 3)
        while len(objects) < 3:  # 자리가 없어 셋을 다 못 놓았으면 다시 뽑는다
            objects = sample_scene(rng, 3, 3)
        order = rng.permutation(3)  # objects[k] 는 색 order[k] 를 갖는다
        for k, obj in enumerate(objects):
            obj["color"] = COLOR_RGB[order[k]]
        image, masks = render_scene(objects, size, rng)  # masks (3, size, size): 실제로 보이는 픽셀
        images[i] = image
        for k, obj in enumerate(objects):
            centers[i, order[k]] = obj["box"][:2]
            per_patch = masks[k].reshape(grid, patch, grid, patch).any(axis=(1, 3))  # (grid, grid)
            on_obj[i, order[k]] = per_patch.reshape(-1)
    return torch.from_numpy(images), torch.from_numpy(centers), torch.from_numpy(on_obj)


def patchify(images, patch: int):
    """(B, 3, H, W) → (B, 패치 수, 3·patch·patch). 그림을 patch × patch 조각으로 잘라 조각마다 한 줄로 편다.

    토큰 순서는 행 우선: 맨 위 줄의 왼쪽 → 오른쪽, 다음 줄 … (sine_position_2d 와 같은 순서).
    """
    b, c, h, w = images.shape
    x = images.reshape(b, c, h // patch, patch, w // patch, patch)
    return x.permute(0, 2, 4, 1, 3, 5).reshape(b, (h // patch) * (w // patch), c * patch * patch)
# --8<-- [end:find-data]


# --8<-- [start:find-model]
class ColorFinder(nn.Module):
    """학습되는 질의 3개가 교차 어텐션 한 층으로 그림 토큰을 보고, 저마다 맡은 색 도형의 중심을 맞힌다.

    그림 (B, 3, 96, 96) → 패치 토큰 (B, 144, 192) → 선형 임베딩 (B, 144, D) [+ 2차원 사인 위치 인코딩]
    → 교차 어텐션(질의 3개 × 토큰 144개, 머리 1개) (B, 3, D) → 작은 MLP → 중심 (B, 3, 2).
    """

    def __init__(self, dim: int = 64, patch: int = 8, size: int = 96, num_queries: int = 3, use_pos: bool = True):
        super().__init__()
        self.patch, self.use_pos = patch, use_pos
        grid = size // patch
        self.embed = nn.Linear(3 * patch * patch, dim)  # 패치 픽셀 192개 → 토큰 벡터
        self.register_buffer("pos", sine_position_2d(grid, grid, dim))  # (144, D): 학습하지 않는 고정값
        self.queries = nn.Parameter(torch.randn(num_queries, dim) * 0.1)  # 학습되는 질의 (3, D)
        self.attn = MultiHeadAttention(dim, num_heads=1)  # 머리 하나 → 어텐션 지도를 그대로 읽을 수 있다
        self.head = nn.Sequential(nn.Linear(dim, dim), nn.ReLU(), nn.Linear(dim, 2))

    def forward(self, images):
        tokens = self.embed(patchify(images, self.patch))  # (B, 144, D)
        if self.use_pos:
            tokens = tokens + self.pos  # 토큰에 "나는 어디에 있다" 를 더한다 → 열쇠에도 값에도 위치가 실린다
        query = self.queries[None].expand(len(images), -1, -1)  # (B, 3, D): 모든 그림에 같은 질의
        out, weights = self.attn(query, tokens, tokens)  # 질의는 질의, 열쇠 · 값은 그림 토큰 → 교차 어텐션
        centers = torch.sigmoid(self.head(out))  # (B, 3, 2): 0 – 1 의 (cx, cy)
        return centers, weights[:, 0]  # 가중치 (B, 3, 144): 머리 축을 뗀다
# --8<-- [end:find-model]


# --8<-- [start:find-train]
def evaluate_finder(model, images, centers, on_obj, batch_size=500):
    """검증: 중심 오차(픽셀)와 '맡은 색 도형 위에 떨어진 어텐션 가중치의 합' 의 평균."""
    model.eval()
    errors, mass = [], []
    with torch.no_grad():
        for i in range(0, len(images), batch_size):
            pred, weights = model(images[i : i + batch_size])
            errors.append((pred - centers[i : i + batch_size]).abs().mean().item() * images.shape[-1])
            mass.append((weights * on_obj[i : i + batch_size]).sum(-1).mean().item())
    return float(np.mean(errors)), float(np.mean(mass))


def train_finder(train, val, use_pos, epochs, device, seed=0, batch_size=128, lr=2e-3):
    """L1 손실로 학습한다. 에폭마다 검증 오차(픽셀)와 '맡은 도형 위의 어텐션' 을 기록한다."""
    torch.manual_seed(seed)
    model = ColorFinder(use_pos=use_pos).to(device)
    optimizer = torch.optim.Adam(model.parameters(), lr=lr)
    images, centers, _ = train
    history = []
    for epoch in range(1, epochs + 1):
        model.train()
        perm = torch.randperm(len(images), device=device)
        for i in range(0, len(images), batch_size):
            idx = perm[i : i + batch_size]
            pred, _ = model(images[idx])
            loss = (pred - centers[idx]).abs().mean()  # 중심 좌표의 L1 오차
            optimizer.zero_grad()
            loss.backward()
            optimizer.step()
        err, mass = evaluate_finder(model, *val)
        history.append((epoch, err, mass))
    return model, history
# --8<-- [end:find-train]


# --8<-- [start:timing]
def time_self_attention(token_counts, dim=256, heads=8, rounds=3, repeats=3, budget=1.0):
    """토큰 N 개의 자기 어텐션 한 번(배치 1)에 걸리는 시간(밀리초)을 잰다.

    - 계산량이 N 에 따라 어떻게 느는지만 깨끗이 보려고 CPU 의 스레드 하나로 잰다
      (GPU 나 여러 스레드로 재면 작은 N 에서는 일을 나눠 맡기는 고정 비용이 시간을 좌우한다).
    - 시계는 time.process_time: 이 프로그램이 CPU 를 실제로 쓴 시간만 센다(다른 프로그램에 CPU 를 내준 시간은 빠진다).
    - 모든 N 을 한 바퀴 재는 일을 rounds 번 되풀이하고, 설정마다 가장 빠른 값을 쓴다
      (다른 프로그램이 끼어들면 느려질 뿐 빨라지지는 않으므로, 최솟값이 방해를 가장 덜 받은 값이다).
    - 직접 구현(가중치 행렬 N × N 을 만들어 돌려준다)과 내장 모듈(need_weights=False → 가중치를 돌려주지 않아도 되므로
      내부에서 F.scaled_dot_product_attention 을 쓴다) 둘 다 잰다.
    """
    torch.manual_seed(0)
    mine = MultiHeadAttention(dim, heads).eval()
    builtin = copy_to_builtin(mine).eval()
    threads = torch.get_num_threads()
    torch.set_num_threads(1)

    def clock(fn):
        """적어도 repeats 번, 그리고 budget 초가 찰 때까지 되풀이해 가장 빠른 값(밀리초)."""
        times, t_end = [], time.perf_counter() + budget
        while len(times) < repeats + 1 or time.perf_counter() < t_end:
            t0 = time.process_time()
            fn()
            times.append((time.process_time() - t0) * 1000)
        return min(times[1:])  # 첫 번은 준비 운동이라 뺀다

    best = {n: [float("inf"), float("inf")] for n in token_counts}
    with torch.no_grad():
        for _ in range(rounds):
            for n in token_counts:
                x = torch.randn(1, n, dim)
                best[n][0] = min(best[n][0], clock(lambda: mine(x, x, x)))
                best[n][1] = min(best[n][1], clock(lambda: builtin(x, x, x, need_weights=False)))
    torch.set_num_threads(threads)  # 스레드 수를 되돌려 놓는다
    return [(n, best[n][0], best[n][1]) for n in token_counts]
# --8<-- [end:timing]


# ───────────────────────── 그림 ─────────────────────────

def plot_scale(rows, n_keys, path):
    dims = [r["d"] for r in rows]
    fig, axes = plt.subplots(1, 3, figsize=(12.5, 3.7))
    ax = axes[0]
    ax.plot(dims, [r["var_raw"] for r in rows], "o-", color="#d55e00", label="Var(q.k)")
    ax.plot(dims, [r["var_scaled"] for r in rows], "s--", color="#0072b2", label="Var(q.k / sqrt(d))")
    ax.plot(dims, dims, ":", color="gray", label="y = d")
    ax.set_xscale("log", base=2)
    ax.set_yscale("log")
    ax.set_xlabel("dimension d")
    ax.set_ylabel("variance of the score")
    ax.set_title("Score variance grows like d")
    ax.legend(fontsize=8)
    ax = axes[1]
    ax.plot(dims, [r["max_raw"] for r in rows], "o-", color="#d55e00", label="no scaling")
    ax.plot(dims, [r["max_scaled"] for r in rows], "s--", color="#0072b2", label="divided by sqrt(d)")
    ax.axhline(1 / n_keys, color="gray", linestyle=":", label=f"uniform = 1/{n_keys}")
    ax.set_xscale("log", base=2)
    ax.set_ylim(0, 1.05)
    ax.set_xlabel("dimension d")
    ax.set_ylabel("mean of the largest weight")
    ax.set_title(f"Softmax over {n_keys} keys: largest weight")
    ax.legend(fontsize=8)
    ax = axes[2]
    ax.plot(dims, [r["ent_raw"] for r in rows], "o-", color="#d55e00", label="no scaling")
    ax.plot(dims, [r["ent_scaled"] for r in rows], "s--", color="#0072b2", label="divided by sqrt(d)")
    ax.axhline(math.log(n_keys), color="gray", linestyle=":", label=f"uniform = log {n_keys}")
    ax.set_xscale("log", base=2)
    ax.set_xlabel("dimension d")
    ax.set_ylabel("mean entropy (nats)")
    ax.set_title("Entropy of the attention weights")
    ax.legend(fontsize=8)
    for ax in axes:
        ax.set_xticks(dims)
        ax.set_xticklabels([str(d) for d in dims])
        ax.grid(alpha=0.3)
    fig.tight_layout()
    fig.savefig(path, dpi=120, facecolor="white")
    plt.close(fig)


def plot_pos1d(path, length=64, dim=64):
    pe = sine_position_1d(length, dim)  # (length, dim)
    fig, axes = plt.subplots(1, 3, figsize=(13, 3.8), gridspec_kw={"width_ratios": [1.25, 1, 1]})
    im = axes[0].imshow(pe.numpy(), cmap="RdBu_r", vmin=-1, vmax=1, aspect="auto", interpolation="nearest")
    axes[0].set_xlabel("component index (0 = fastest)")
    axes[0].set_ylabel("position pos")
    axes[0].set_title(f"PE(pos, .), length {length}, d = {dim}")
    fig.colorbar(im, ax=axes[0], fraction=0.046)
    styles = [("-", "#0072b2"), ("--", "#d55e00"), ("-.", "#009e73"), (":", "#000000")]
    for (ls, color), comp in zip(styles, (0, 8, 16, 32)):
        axes[1].plot(pe[:, comp].numpy(), ls, color=color, label=f"component {comp}")
    axes[1].set_xlabel("position pos")
    axes[1].set_ylabel("value")
    axes[1].set_title("Four sine components")
    axes[1].legend(fontsize=8, loc="lower right")
    axes[1].grid(alpha=0.3)
    sim = pe @ pe.T  # (length, length)
    for (ls, color), ref in zip(styles, (10, 32, 50)):
        axes[2].plot(sim[ref].numpy(), ls, color=color, label=f"reference pos = {ref}")
    axes[2].set_xlabel("position pos")
    axes[2].set_ylabel("dot product PE(pos) . PE(ref)")
    axes[2].set_title("Similarity to a reference position")
    axes[2].legend(fontsize=8)
    axes[2].grid(alpha=0.3)
    fig.tight_layout()
    fig.savefig(path, dpi=120, facecolor="white")
    plt.close(fig)


def plot_pos2d(path, grid=12, dim=64):
    pe = sine_position_2d(grid, grid, dim).reshape(grid, grid, dim)
    fig, axes = plt.subplots(2, 4, figsize=(12.5, 6.2))
    channels = [(0, "y half, ch 0 (sin, fastest)"), (1, "y half, ch 1 (cos, fastest)"),
                (4, "y half, ch 4 (sin, slower)"), (dim // 2, f"x half, ch {dim // 2} (sin, fastest)")]
    for ax, (ch, title) in zip(axes[0], channels):
        im = ax.imshow(pe[:, :, ch].numpy(), cmap="RdBu_r", vmin=-1, vmax=1, interpolation="nearest")
        ax.set_title(title, fontsize=9)
        ax.set_xlabel("x (column)")
        ax.set_ylabel("y (row)")
        fig.colorbar(im, ax=ax, fraction=0.046)
    flat = pe.reshape(-1, dim)
    refs = [(2, 3), (6, 6), (9, 10), (11, 0)]
    for ax, (r, c) in zip(axes[1], refs):
        sim = (flat @ pe[r, c]).reshape(grid, grid)  # 기준 위치와 모든 위치의 내적
        im = ax.imshow(sim.numpy(), cmap="viridis", interpolation="nearest")
        ax.plot([c], [r], marker="x", color="red", markersize=10, markeredgewidth=2)
        ax.set_title(f"dot product with (row {r}, col {c})", fontsize=9)
        ax.set_xlabel("x (column)")
        ax.set_ylabel("y (row)")
        fig.colorbar(im, ax=ax, fraction=0.046)
    fig.tight_layout()
    fig.savefig(path, dpi=120, facecolor="white")
    plt.close(fig)


def plot_find_curves(runs, hist_nopos, baseline, uniform_mass, path):
    """runs: [(시드, 기록, 풀이 종류)] — 종류는 "attend"(도형을 본다) 또는 "avoid"(도형만 빼고 본다)."""
    fig, axes = plt.subplots(1, 2, figsize=(11, 4.0))
    style = {"attend": ("-", "#0072b2", "o"), "avoid": ("--", "#d55e00", "s")}
    for seed, hist, kind in runs:
        ls, color, marker = style[kind]
        epochs = [h[0] for h in hist]
        label = f"seed {seed}: pos. enc., {'attends to' if kind == 'attend' else 'avoids'} its shape"
        axes[0].plot(epochs, [h[1] for h in hist], ls, color=color, marker=marker, markersize=3, markevery=3, label=label)
        axes[1].plot(epochs, [h[2] for h in hist], ls, color=color, marker=marker, markersize=3, markevery=3, label=label)
    epochs = [h[0] for h in hist_nopos]
    axes[0].plot(epochs, [h[1] for h in hist_nopos], "-.", color="black", label="seed 0: no position encoding")
    axes[1].plot(epochs, [h[2] for h in hist_nopos], "-.", color="black", label="seed 0: no position encoding")
    axes[0].axhline(baseline, color="gray", linestyle=":", label="always predict the mean center")
    axes[1].axhline(uniform_mass, color="gray", linestyle=":", label="uniform attention")
    axes[0].set_xlabel("epoch")
    axes[0].set_ylabel("validation center error (pixels)")
    axes[0].set_title("Error of the predicted centers")
    axes[0].set_ylim(bottom=0)
    axes[0].legend(fontsize=7)
    axes[1].set_xlabel("epoch")
    axes[1].set_ylabel("attention mass on the query's own shape")
    axes[1].set_title("Where does the attention go?")
    axes[1].set_ylim(-0.02, 1.02)
    axes[1].legend(fontsize=7, loc="center right")
    for ax in axes:
        ax.grid(alpha=0.3)
    fig.tight_layout()
    fig.savefig(path, dpi=120, facecolor="white")
    plt.close(fig)


def plot_find_attention(models, val, path, picks=(0, 2), grid=12):
    """models: [(이름, 모델)]. 행 = 모델, 열 = 검증 그림 picks 마다 [그림, 빨강 · 초록 · 파랑 질의의 어텐션 지도]."""
    images, centers, _ = val
    marker_colors = ["#ff5a5a", "#66d973", "#738cfa"]
    fig, axes = plt.subplots(len(models), 4 * len(picks), figsize=(4 * len(picks) * 2.0, 2.2 * len(models)), squeeze=False)
    with torch.no_grad():
        for row, (name, model) in enumerate(models):
            for col, index in enumerate(picks):
                image = images[index : index + 1]
                pred, weights = model(image)
                pred, weights = pred[0].cpu().numpy(), weights[0].cpu().numpy()
                ax = axes[row, 4 * col]
                ax.imshow(np.transpose(image[0].cpu().numpy(), (1, 2, 0)), interpolation="nearest")
                size = image.shape[-1]
                for c in range(3):
                    tx, ty = centers[index, c].cpu().numpy() * size - 0.5
                    px, py = pred[c] * size - 0.5
                    ax.plot([tx], [ty], marker="+", color="white", markersize=11, markeredgewidth=2.2)
                    ax.plot([px], [py], marker="o", markerfacecolor="none", markeredgecolor="black",
                            markersize=10, markeredgewidth=3.0)
                    ax.plot([px], [py], marker="o", markerfacecolor="none", markeredgecolor=marker_colors[c],
                            markersize=10, markeredgewidth=1.5)
                ax.set_title(f"{name}", fontsize=8)
                ax.set_xticks([])
                ax.set_yticks([])
                for c in range(3):
                    ax = axes[row, 4 * col + 1 + c]
                    ax.imshow(weights[c].reshape(grid, grid), cmap="magma", vmin=0, interpolation="nearest")
                    ax.set_title(f"{COLOR_NAMES[c]} query (max weight {weights[c].max():.2f})", fontsize=8)
                    ax.set_xticks([])
                    ax.set_yticks([])
    fig.tight_layout()
    fig.savefig(path, dpi=120, facecolor="white")
    plt.close(fig)


def plot_time(rows, path):
    ns = np.array([r[0] for r in rows], dtype=float)
    fig, ax = plt.subplots(figsize=(6.2, 4.2))
    ax.plot(ns, [r[1] for r in rows], "o-", color="#0072b2", label="our MultiHeadAttention")
    ax.plot(ns, [r[2] for r in rows], "s--", color="#d55e00", label="nn.MultiheadAttention (need_weights=False)")
    ref = rows[-1][1] * (ns / ns[-1]) ** 2
    ax.plot(ns, ref, ":", color="gray", label="slope 2 (time ~ N^2)")
    ax.set_xscale("log")
    ax.set_yscale("log")
    ax.set_xticks(ns)
    ax.set_xticklabels([str(int(n)) for n in ns], rotation=30)
    ax.minorticks_off()
    ax.set_xlabel("number of tokens N")
    ax.set_ylabel("time per self-attention (ms)")
    ax.set_title("Self-attention time vs. tokens (CPU, 1 thread, d = 256, 8 heads)")
    ax.grid(alpha=0.3)
    ax.legend(fontsize=8)
    fig.tight_layout()
    fig.savefig(path, dpi=120, facecolor="white")
    plt.close(fig)


def main():
    parser = argparse.ArgumentParser(description="5장: 어텐션과 Transformer")
    parser.add_argument("--quick", action="store_true", help="아주 작게 돌려 오류만 확인")
    parser.add_argument("--seed", type=int, default=0)
    parser.add_argument("--fig-dir", default="figures")
    args = parser.parse_args()
    os.makedirs(args.fig_dir, exist_ok=True)
    fig = lambda name: os.path.join(args.fig_dir, name)  # noqa: E731
    device = get_device()
    print(f"장치: {device}")
    t_start = time.time()

    # 1. 손계산
    x = hand_example()

    # 2. √d_k 실험
    n_keys = 16
    rows = scale_experiment(trials=2000 if args.quick else 20000, n_keys=n_keys, seed=args.seed)
    print(f"[√d] 열쇠 {n_keys}개. 고른 가중치라면 최대 가중치 {1 / n_keys:.4f}, 엔트로피 log {n_keys} = {math.log(n_keys):.3f}")
    for r in rows:
        print(f"[√d] d = {r['d']:4d}: Var(q·k) = {r['var_raw']:8.2f}, Var(q·k/√d) = {r['var_scaled']:.3f} |"
              f" 최대 가중치: 안 나눔 {r['max_raw']:.3f}, 나눔 {r['max_scaled']:.3f} |"
              f" 엔트로피: 안 나눔 {r['ent_raw']:.3f}, 나눔 {r['ent_scaled']:.3f}")
    for scores in ([8.0, 0.0], [1.0, 0.0]):
        p = torch.softmax(torch.tensor(scores), dim=0)
        print(f"[소프트맥스] 점수 {scores} → 가중치 [{p[0]:.5f}, {p[1]:.5f}], 기울기 p(1−p) = {(p[0] * p[1]).item():.5f}")
    plot_scale(rows, n_keys, fig("ch05-scale.png"))

    # 3. 마스크
    mask_examples(x)

    # 4 – 5. 다중 머리 어텐션, 순열 등변성
    mine = check_multi_head(args.seed)
    check_permutation(mine, args.seed)

    # 6. 위치 인코딩
    pe = sine_position_1d(4, 4)
    print("[위치] sine_position_1d(4, 4) =\n", pe)
    pe64 = sine_position_1d(64, 64)
    sim = pe64 @ pe64.T
    print(f"[위치] d = 64: PE(32)·PE(32) = {sim[32, 32]:.2f}, PE(32)·PE(33) = {sim[32, 33]:.2f},"
          f" PE(32)·PE(36) = {sim[32, 36]:.2f}, PE(32)·PE(48) = {sim[32, 48]:.2f}")
    print(f"[위치] 위치가 달라도 간격이 같으면 내적이 같다: PE(10)·PE(14) = {sim[10, 14]:.2f}, PE(50)·PE(54) = {sim[50, 54]:.2f}")
    pe2 = sine_position_2d(12, 12, 64)
    print(f"[위치] sine_position_2d(12, 12, 64) 모양 {tuple(pe2.shape)},"
          f" 같은 행의 두 토큰은 앞 절반(y)이 같다: {torch.equal(pe2[0, :32], pe2[5, :32])},"
          f" 같은 열의 두 토큰은 뒤 절반(x)이 같다: {torch.equal(pe2[5, 32:], pe2[17, 32:])}")
    plot_pos1d(fig("ch05-pos1d.png"))
    plot_pos2d(fig("ch05-pos2d.png"))

    # 7. 인코더 층
    check_encoder_layer(args.seed)

    # 8. 색으로 찾기
    n_train, n_val, epochs, seeds = (400, 200, 3, (0, 1)) if args.quick else (4000, 1000, 30, (0, 1, 2, 3, 4))
    t0 = time.time()
    train = tuple(t.to(device) for t in make_color_scenes(n_train, seed=0))
    val = tuple(t.to(device) for t in make_color_scenes(n_val, seed=1))
    baseline = (val[1] - train[1].mean(dim=0)).abs().mean().item() * 96
    uniform_mass = val[2].float().mean().item()  # 가중치가 고르다면 맡은 도형 위에 떨어질 몫 = 도형이 걸친 패치의 비율
    print(f"[찾기] 학습 {n_train}장, 검증 {n_val}장 ({time.time() - t0:.1f}초). 그림 {tuple(train[0].shape[1:])} →"
          f" 토큰 {tuple(patchify(train[0][:1], 8).shape[1:])}")
    print(f"[찾기] 기준선(늘 학습 데이터의 평균 중심을 답함): 검증 중심 오차 {baseline:.2f} 픽셀."
          f" 고른 어텐션이라면 맡은 도형 위의 가중치 합 {uniform_mass:.3f}")
    t0 = time.time()
    runs, models = [], {}
    shown = sorted({e for e in (1, 5, 10, epochs) if e <= epochs})  # 출력에 보일 에폭
    label = " · ".join(str(e) for e in shown)
    for seed in seeds:
        model, hist = train_finder(train, val, True, epochs, device, seed)
        kind = "attend" if hist[-1][2] > 0.5 else "avoid"
        runs.append((seed, hist, kind))
        models.setdefault(kind, (seed, model))  # 종류마다 처음 나온 시드의 모델을 그림에 쓴다
        marks = ", ".join(f"{hist[e - 1][1]:5.2f}" for e in shown)
        print(f"[찾기 · 위치 인코딩 있음] 시드 {seed}: 검증 중심 오차(픽셀) 에폭 {label} = {marks} |"
              f" 맡은 도형 위의 어텐션 {hist[-1][2]:.3f} → {'도형을 본다' if kind == 'attend' else '도형만 빼고 본다'}")
    model_nopos, hist_nopos = train_finder(train, val, False, epochs, device, seeds[0])
    marks = ", ".join(f"{hist_nopos[e - 1][1]:5.2f}" for e in shown)
    print(f"[찾기 · 위치 인코딩 없음] 시드 {seeds[0]}: 검증 중심 오차(픽셀) 에폭 {label} = {marks} |"
          f" 맡은 도형 위의 어텐션 {hist_nopos[-1][2]:.3f}")
    for kind, name in (("attend", "도형을 본다"), ("avoid", "도형만 빼고 본다")):
        errs = [hist[-1][1] for _, hist, k in runs if k == kind]
        if errs:
            print(f"[찾기] '{name}' 풀이: 시드 {len(errs)}개, 마지막 검증 중심 오차 평균 {np.mean(errs):.2f} 픽셀"
                  f" (최소 {min(errs):.2f}, 최대 {max(errs):.2f})")
    print(f"[찾기] 모델 {len(seeds) + 1}개 학습 {time.time() - t0:.1f}초, 모델 매개변수 {sum(p.numel() for p in model_nopos.parameters()):,}개")
    plot_find_curves(runs, hist_nopos, baseline, uniform_mass, fig("ch05-find-curves.png"))
    panel = [(f"pos. enc., seed {models[k][0]} ({k}s)", models[k][1]) for k in ("attend", "avoid") if k in models]
    panel.append((f"no pos. enc., seed {seeds[0]}", model_nopos))
    plot_find_attention(panel, val, fig("ch05-find-attention.png"))

    # 9. 시간
    counts = (144, 576, 1024) if args.quick else (144, 576, 1024, 1600, 2304, 4096)
    rows_t = time_self_attention(counts, rounds=1 if args.quick else 3, budget=0.2 if args.quick else 1.0)
    for n, mine_ms, builtin_ms in rows_t:
        print(f"[시간] N = {n:5d} (쌍 {n * n:>10,}개): 직접 구현 {mine_ms:8.3f} ms, 내장(가중치 안 돌려줌) {builtin_ms:8.3f} ms")
    (n1, a1, b1), (n2, a2, b2) = rows_t[0], rows_t[-1]
    print(f"[시간] N 이 {n1} → {n2} ({n2 / n1:.1f}배, N² 은 {(n2 / n1) ** 2:.0f}배)일 때 시간: 직접 구현 {a2 / a1:.0f}배,"
          f" 내장 {b2 / b1:.0f}배")
    log_n = np.log([r[0] for r in rows_t])  # 로그-로그 그림에서 직선의 기울기 = 시간이 N 의 몇 제곱으로 느는가
    slope_mine = np.polyfit(log_n, np.log([r[1] for r in rows_t]), 1)[0]
    slope_builtin = np.polyfit(log_n, np.log([r[2] for r in rows_t]), 1)[0]
    print(f"[시간] 로그-로그 직선 맞춤의 기울기(시간 ∝ N^기울기): 직접 구현 {slope_mine:.2f}, 내장 {slope_builtin:.2f}")
    plot_time(rows_t, fig("ch05-time.png"))
    print(f"전체 {time.time() - t_start:.1f}초")


if __name__ == "__main__":
    main()
