24.9-dars: GPT — generatsiya

ARXITEKTURA:
  x (B, T) -> token embedding + pozitsiya embedding
           -> N ta blok: [LN -> kauzal self-attention -> +] [LN -> FFN -> +]
           -> LayerNorm -> Linear(d, V) -> logit (B, T, V)

MAQSAD (23.10 bilan AYNAN bir xil):
  loss = cross_entropy(logit[:, t], x[:, t+1])  - barcha t uchun
  teacher forcing + kauzal niqob -> bitta forward (24.7-dars)

24.7 DAGI DECODERDAN FARQI:
  hech narsa - GPT = cross-attention siz decoder-only stek
  encoder-decoder dagi decoderdan farqi: cross-attention bloki yo'q

MASSHTAB (taxminiy, tarixiy):
  GPT-1 (2018):  12 qatlam, d = 768,   ~117M parametr
  GPT-2 (2019):  48 qatlam, d = 1600,  ~1.5B
  GPT-3 (2020):  96 qatlam, d = 12288, ~175B
  bizniki:        2 qatlam, d = 48,    43 133 parametr

BIZNING MODEL:
  belgi darajasi, V = 29 (23.10 korpusi), kontekst L = 48
  F.scaled_dot_product_attention(q, k, v, is_causal=True)

O'RGATILADIGAN POZITSIYA EMBEDDINGI: nn.Embedding(L, d)
  faqat 0 .. L-1 pozitsiyalar mavjud
  L dan uzun kirish -> indeks xatosi (yoki o'rgatilmagan vektorlar)

GENERATSIYADA UZUN MATN:
  "sirpanuvchi oyna": modelga faqat oxirgi L token beriladi
    x = x[:, -L:]
  L dan oldingi hamma narsa model uchun YO'Q
  3-misol: 300 belgili matn, model har qadamda oxirgi 48 belgini ko'radi

OYNA BOSHIDAGI POZITSIYALAR:
  oyna chetida kontekst kam -> loss yuqori (24.7, 3-misol)
  1-misol: 0-7 pozitsiyalarda PPL 2.4-2.6, 8-47 da 1.5-1.6

KESHSIZ GENERATSIYA NARXI:
  har qadamda butun oyna qayta hisoblanadi
  KV-kesh va uzun kontekst usullari - Samaradorlik va masshtab darsida

HALOL TAQQOSLASH SHARTLARI:
  bir xil tokenizatsiya va lug'at (belgi, V = 29)
  bir xil val matni va baholash protokoli (48 belgili oynalar, ikkalasida)
  bir xil o'rgatish byudjeti: 400 qadam x 32 oyna, AYNAN bir xil batchlar
  bir necha seed; farq - juftlashgan, SE bilan
  har model o'ziga mos optimizator bilan (LSTM - 23.10 sozlamasi,
  GPT - AdamW + warmup + cosine, lr kichik to'rda tanlangan)

1-MISOL NATIJASI (3 seed):
  LSTM  (27 901 parametr): val PPL 1.6123
  GPT   (43 133 parametr): val PPL 1.7037
  GPT - LSTM: +0.0915, SE 0.0085 -> LSTM sezilarli yaxshi
  (23.10 dagi 1.4863 - uzluksiz kontekst bilan; bu yerda har 48 belgida
   kontekst uziladi; 8-47 pozitsiyalarda LSTM 1.485-1.487 - mos)

UZOQ BOG'LIQLIK ('-ga ... bordi', ~11 belgi):
  LSTM 0.852, GPT 0.875 (o'rtacha); farq +0.023, SE 0.051 - sezilarli emas

NEGA KICHIK MASSHTABDA LSTM YUTDI:
  induktiv moyillik: rekurrentlik "yaqin o'tmish muhim" degan taxminni
  arxitekturaga tikadi - belgi darajasidagi imloga juda mos
  transformer bu qonuniyatni ma'lumotdan O'RGANISHI kerak
  GPT 1.9 barobar ko'p FLOP sarflab ham yetib olmadi (482 va 257 MFLOP/qadam)

TRANSFORMER QACHON YUTADI:
  o'rgatish PARALLEL: ketma-ket qadamlar 2 (qatlamlar), LSTM da 48
  -> GPU da bir xil vaqtda ko'p marta ko'p ma'lumot
  uzoq masofa: istalgan ikki pozitsiya orasida 1 attention qadami
  masshtab: ma'lumot va parametr ortgan sari yaxshilanish davom etadi
  (bu kichik CPU tajribasida bu ustunliklar ko'rinmaydi)

SIKL: x = prompt
  takrorla: logit = model(x)[:, -1];  keyingi = TANLA(logit);  x = [x, keyingi]

GREEDY:     keyingi = argmax(logit)                - deterministik
TEMPERATURE: p = softmax(logit / T)
  T < 1 - o'tkirroq (ehtimolli tokenlar kuchayadi), T > 1 - tekisroq
  2-misol (0.50 0.20 0.15 0.10 0.04 0.01):
    T = 0.5 -> 0.770 0.123 0.071 0.031 0.005 0.000
    T = 2.0 -> 0.326 0.206 0.182 0.146 0.093 0.047

TOP-k:  eng katta k ta logit qoladi, qolgani -inf, keyin softmax
  k = 3 -> 0.585 0.234 0.180 0 0 0   (qayta normallangan)

TOP-p (NUCLEUS):  kamayish tartibida, yig'indisi >= p bo'lgan ENG KICHIK to'plam
  tartiblash -> cumsum -> "shu tokengacha yig'ilgan massa >= p" bo'lganlarni kesish
  p = 0.9: 0.50 + 0.20 + 0.15 = 0.85 < 0.9 -> 4-token ham kiradi 0.95-bob
  natija: 0.524 0.209 0.161 0.105 0 0

NEGA TOP-p MOSLASHUVCHAN (2-misol, 2-bo'lim):
  jumla boshi ('\n' dan keyin):  eng katta p 0.131 -> yadro 14 token
  "anvar bozo" dan keyin:        eng katta p 0.952 -> yadro 1 token
  top-k = 5 ikkalasida ham 5 ta: boshida kam, so'z ichida ortiqcha

CHEGARAVIY HOLATLAR (4-misol, hammasi greedy ga teng):
  top-k = 1,  top-p -> 0,  T -> 0

BEAM SEARCH (qisqa):
  bir nechta eng ehtimolli prefiksni parallel kuzatadi
  tarjima kabi "yagona to'g'ri javob" vazifalarda; ochiq generatsiyada
  greedy kabi takrorlanishga moyil (Katta til modellari qismida)

O'LCHOVLAR (2-misol, 300 jumla):
  shablon    - jumla korpus grammatikasiga to'liq mosmi (to'g'rilik)
  lug'atda   - so'zlar o'quv lug'atida bormi (imlo)
  noyob      - noyob jumlalar ulushi
  distinct-2 - noyob so'z bigrammlari / barcha bigrammlar

2-MISOL NATIJASI:
  usul       shablon  noyob  distinct-2
  greedy     100.0%   0.3%   0.003     - bitta jumla, lekin to'g'ri
  T=0.7       20.3%  99.0%   0.530
  T=1.0        7.0% 100.0%   0.620
  T=1.3        2.3% 100.0%   0.706
  top-k=5      8.3%  99.0%   0.555
  top-p=0.9   17.3%  99.7%   0.548

MUROSA:
  T oshsa - xilma-xillik oshadi, to'g'rilik tushadi
  top-p T=1.0 dan ancha to'g'ri (7.0% -> 17.3%), deyarli bir xil xilma-xil
  bu kichik modelda eng to'g'ri namuna olish - T=0.7

DEGENERATSIYA:
  greedy uzun matnda bitta jumlani cheksiz takrorlaydi
  sabab: deterministik tanlov + bir xil kontekst -> bir xil davom
  jumla tugashi bilan kontekst avvalgi holatga qaytadi -> sikl

O'LCHOVLAR (3-misol, 30 matn x 300 belgi):
  takror ulushi - matndagi jumla shu matnda OLDIN aynan uchraganmi
  distinct-1, distinct-2 - har matn ichida noyob so'z n-grammlari ulushi

  manba             takror  distinct-2  shablon
  greedy            89.8%     0.140      0.3%   - 30 matnning 30 tasida 1 jumlali sikl
  T=0.7              0.0%     0.875     16.3%
  top-p=0.9          0.0%     0.897     11.9%
  aralash           17.5%     0.592     38.3%
  korpus (haqiqiy)   1.5%     0.896    100.0%   - ma'lumotnoma

YECHIMLAR:
  namuna olish (temperature, top-p) - sikldan chiqaradi
  aralash: faqat noaniq joyda (jumla boshi) namuna, qolgan joyda greedy
  repetition penalty - oldin chiqqan tokenlar logitini kamaytirish
  no_repeat_ngram_size - bir xil n-grammni ikkinchi marta taqiqlash
  frequency / presence penalty - chastotaga qarab jarima
  (oxirgi uchtasi so'z/subword tokenlarida ma'noli; belgi darajasida
   har belgi baribir takrorlanadi)

TORCH.GENERATOR:
  g = torch.Generator().manual_seed(7)
  torch.multinomial(p, 1, generator=g)
  global torch.manual_seed ga bog'liq emas (4-misol: True)

TUZOQ 1 - BATCH TARKIBI:
  bitta generator butun batch uchun tasodifiy sonlarni ketma-ket oladi
  8 talik batchdagi 0-qator va yolg'iz 0-qator - BOSHQA natija
  yechim: har qatorga (so'rovga) o'z generatori, urug' = asosiy + i

TUZOQ 2 - BIR XIL URUG' HAMMA PROMPTGA:
  birinchi tasodifiy son hamma promptda bir xil -> namunalar korrelyatsiyalangan
  4-misol, '-ga ... bordi.': P('b') o'rtacha 0.764
    bitta urug': to'g'ri davom 0.42;  o'z urug'i: 0.69
  '-dan ... qaytdi.': bitta urug' 1.00, o'z urug'i 0.88
  ya'ni baho tasodifan har ikki tomonga siljiydi

AMALDA:
  so'rov ID sidan urug' (masalan, hash) - qayta ishga tushirishda bir xil javob
  baholashda har prompt uchun mustaqil urug' yoki bir necha urug'

PROMPT = BOSHLANG'ICH PREFIKS:
  x = tokenlash("anvar bozorga ertalab ")
  model davom ettiradi: P(keyingi | prompt)
  GPT uchun "vazifa" = to'g'ri tuzilgan prefiks (Katta til modellari
  qismida - ko'rsatmalar va misollar bilan prompt)

TEKSHIRISH (4-misol):
  '<ism> <joy>ga <vaqt> '  -> 'bordi.'   greedy 0.90
  '<ism> <joy>dan <vaqt> ' -> 'qaytdi.'  greedy 0.98
  hal qiluvchi qo'shimcha prompt oxiridan 5-10 belgi oldin
  model uni kauzal attention orqali "eslab" qoladi

import torch
import torch.nn.functional as F

# kauzal blok (qisqa)
o = F.scaled_dot_product_attention(q, k, v, is_causal=True)

# oyna: faqat oxirgi L token
logit = model(x[:, -L:])[:, -1]

# strategiyalar
keyingi = logit.argmax(-1)                                    # greedy
logit = logit / T                                             # temperature
chegara = logit.topk(k, dim=-1).values[:, -1:]                # top-k
logit = logit.masked_fill(logit < chegara, float("-inf"))
tartib, idx = logit.sort(dim=-1, descending=True)             # top-p
p_t = torch.softmax(tartib, -1)
tartib = tartib.masked_fill(p_t.cumsum(-1) - p_t >= p, float("-inf"))
logit = torch.full_like(logit, float("-inf")).scatter(-1, idx, tartib)
keyingi = torch.multinomial(torch.softmax(logit, -1), 1, generator=g)[:, 0]

# deterministik: har so'rovga o'z generatori
g_i = torch.Generator().manual_seed(asosiy_urug + i)

# o'lchovlar
distinct_2 = len(set(bigrammlar)) / len(bigrammlar)
takror = np.mean([j in oldingilar for j in jumlalar])

GPT = kauzal decoder-only, maqsad - keyingi token
kontekst oynasi L; uzun matnda sirpanuvchi oyna
halol taqqoslash: bir xil lug'at, val, protokol, batchlar, bir necha seed
greedy - bir xil va siklga tushadi; T, top-k, top-p - murosa tugmalari
top-p - ehtimol massasi bo'yicha moslashuvchan
torch.Generator + har so'rovga o'z urug'i

"""Kichik GPT va 23.10-darsdagi LSTM: bir xil ma'lumot, qadam va batchlarda perplexity."""

import math

import numpy as np
import torch
import torch.nn as nn
import torch.nn.functional as F

ISMLAR = ("anvar dilnoza bobur malika sardor nodira jasur zarina otabek madina "
          "sherzod gulnora farhod laylo rustam sevara aziz kamola bahrom "
          "shahlo temur nigora dilshod feruza jamshid mohira sanjar yulduz").split()
VAQTLAR = "ertalab kechqurun bugun kecha tushda yakshanba erta indinga".split()
JOYLAR = ("bozor maktab bog' shahar qishloq kutubxona do'kon universitet "
          "choyxona dala bekat kasalxona stadion muzey teatr vokzal "
          "ofis zavod").split()
NARSALAR = ("kitob olma non qalam daftar gul choy sut anor uzum ruchka gazeta "
            "qovun tarvuz sabzi guruch go'sht shakar asal pishloq ko'ylak "
            "do'ppi soat telefon").split()
SIFATLAR = ("katta kichik yangi eski chiroyli shirin qizil oq arzon qimmat "
            "yashil sariq issiq sovuq mazali").split()
MAQOLLAR = ["sabr tagi sariq oltin.", "til qilichdan o'tkir.",
            "vaqt oltindan qimmat.", "ko'p o'qigan ko'p biladi.",
            "mehnat qilsang rohat ko'rasan.", "yaxshi so'z jon ozig'i.",
            "daraxt mevasidan odam mehnatidan.",
            "ilm olish igna bilan quduq qazish."]
L = 48


def jumla(rng):
    t = rng.integers(0, 7)
    ism, ism2 = rng.choice(ISMLAR, 2, replace=False)
    vaqt, joy = rng.choice(VAQTLAR), rng.choice(JOYLAR)
    narsa, sifat = rng.choice(NARSALAR), rng.choice(SIFATLAR)
    if t == 0:
        return f"{ism} {joy}ga {vaqt} bordi."
    if t == 1:
        return f"{ism} {joy}dan {vaqt} qaytdi."
    if t == 2:
        return f"{ism} {sifat} {narsa} sotib oldi."
    if t == 3:
        return f"{joy}da {sifat} {narsa} bor."
    if t == 4:
        return f"{ism} {ism2}ga {sifat} {narsa} berdi."
    if t == 5:
        return f"{ism} {joy}dan {narsa} olib keldi."
    return str(rng.choice(MAQOLLAR))


def korpus(n, seed):
    rng = np.random.default_rng(seed)
    return "\n".join(jumla(rng) for _ in range(n)) + "\n"


class Blok(nn.Module):
    def __init__(self, d, boshlar):
        super().__init__()
        self.boshlar = boshlar
        self.ln1, self.ln2 = nn.LayerNorm(d), nn.LayerNorm(d)
        self.qkv = nn.Linear(d, 3 * d)
        self.proj = nn.Linear(d, d)
        self.ffn = nn.Sequential(nn.Linear(d, 2 * d), nn.GELU(), nn.Linear(2 * d, d))

    def forward(self, x):
        B, T, d = x.shape
        q, k, v = self.qkv(self.ln1(x)).split(d, dim=2)
        q, k, v = [t.view(B, T, self.boshlar, -1).transpose(1, 2) for t in (q, k, v)]
        o = F.scaled_dot_product_attention(q, k, v, is_causal=True)
        x = x + self.proj(o.transpose(1, 2).reshape(B, T, d))
        return x + self.ffn(self.ln2(x))


class GPT(nn.Module):
    """Decoder-only: token + pozitsiya embedding, kauzal bloklar, chiqish qatlami."""

    def __init__(self, V, d=48, boshlar=4, qatlamlar=2):
        super().__init__()
        self.emb = nn.Embedding(V, d)
        self.poz = nn.Embedding(L, d)
        self.bloklar = nn.Sequential(*[Blok(d, boshlar) for _ in range(qatlamlar)])
        self.ln = nn.LayerNorm(d)
        self.chiqish = nn.Linear(d, V)

    def forward(self, x):
        h = self.emb(x) + self.poz(torch.arange(x.shape[1]))
        return self.chiqish(self.ln(self.bloklar(h)))


class LSTMModel(nn.Module):
    """23.10-darsdagi model: Embedding(V, 32) -> LSTM(32, 64) -> Linear."""

    def __init__(self, V, d=32, h=64):
        super().__init__()
        self.emb = nn.Embedding(V, d)
        self.lstm = nn.LSTM(d, h, batch_first=True)
        self.chiqish = nn.Linear(h, V)

    def forward(self, x):
        o, _ = self.lstm(self.emb(x))
        return self.chiqish(o)


def orgat(tur, T_oquv, V, seed, qadamlar=400, B=32):
    """Ikkala model uchun AYNAN bir xil batchlar (bir xil generator urug'i)."""
    torch.manual_seed(seed)
    if tur == "LSTM":
        model = LSTMModel(V)
        opt = torch.optim.Adam(model.parameters(), lr=0.01)       # 23.10 sozlamasi
        jadval = None
    else:
        model = GPT(V)
        opt = torch.optim.AdamW(model.parameters(), lr=0.02, weight_decay=0.01)
        jadval = torch.optim.lr_scheduler.LambdaLR(
            opt, lambda s: min(1.0, (s + 1) / 40) * 0.5 * (1 + math.cos(math.pi * s / qadamlar)))
    g = torch.Generator().manual_seed(seed)
    oxirgi = []
    for q in range(qadamlar):
        bosh = torch.randint(0, len(T_oquv) - L - 1, (B,), generator=g)
        w = torch.stack([T_oquv[i:i + L + 1] for i in bosh.tolist()])
        loss = F.cross_entropy(model(w[:, :-1]).reshape(-1, V), w[:, 1:].reshape(-1))
        opt.zero_grad()
        loss.backward()
        nn.utils.clip_grad_norm_(model.parameters(), 1.0)
        opt.step()
        if jadval is not None:
            jadval.step()
        if q >= qadamlar - 20:
            oxirgi.append(loss.item())
    model.eval()
    return model, float(np.mean(oxirgi))


@torch.no_grad()
def val_ehtimollar(model, T_val):
    """Val ni 48 belgili oynalarga bo'lamiz - ikkala model uchun bir xil shart."""
    n = (len(T_val) - 1) // L
    x = T_val[:n * L].view(n, L)
    y = T_val[1:n * L + 1].view(n, L)
    logp = torch.log_softmax(model(x), -1)
    return logp.gather(2, y.unsqueeze(2)).squeeze(2).reshape(-1)     # log p(y_t)


def main() -> None:
    torch.set_num_threads(1)
    oquv, val = korpus(2000, 0), korpus(400, 1)
    lugat = sorted(set(oquv + val))
    V = len(lugat)
    s2i = {c: i for i, c in enumerate(lugat)}
    T_oquv = torch.tensor([s2i[c] for c in oquv])
    T_val = torch.tensor([s2i[c] for c in val])

    print("=== 1. Ikki model, bir xil sharoit ===")
    for tur in ("LSTM", "GPT"):
        torch.manual_seed(0)
        m = LSTMModel(V) if tur == "LSTM" else GPT(V)
        print(f"  {tur:<5} parametrlar {sum(p.numel() for p in m.parameters()):>6}")
    print(f"  korpus 23.10 dagi kabi: V = {V}, oyna L = {L}, batch 32, 400 qadam")
    print("  har seed da ikkala model AYNAN bir xil batchlarni ko'radi")

    print("\n=== 2. Val perplexity (3 seed, juftlashgan) ===")
    natija = {"LSTM": [], "GPT": []}
    ehtimol = {"LSTM": [], "GPT": []}
    for s in range(3):
        for tur in ("LSTM", "GPT"):
            m, oquv_loss = orgat(tur, T_oquv, V, s)
            lp = val_ehtimollar(m, T_val)
            natija[tur].append((math.exp(-lp.mean().item()), math.exp(oquv_loss)))
            ehtimol[tur].append(lp.exp().numpy())
    print("  model  val PPL (seed 0, 1, 2)      o'rtacha  o'quv PPL")
    for tur in ("LSTM", "GPT"):
        v = np.array(natija[tur])
        print(f"  {tur:<6} {', '.join(f'{x:.4f}' for x in v[:, 0]):<26} "
              f"{v[:, 0].mean():>9.4f} {v[:, 1].mean():>10.4f}")
    farq = np.array(natija["GPT"])[:, 0] - np.array(natija["LSTM"])[:, 0]
    se = farq.std(ddof=1) / math.sqrt(len(farq))
    xulosa = ("GPT sezilarli yaxshi" if farq.mean() < -2 * se else
              "LSTM sezilarli yaxshi" if farq.mean() > 2 * se else "sezilarli farq yo'q")
    print(f"  GPT - LSTM: {farq.mean():+.4f}, SE {se:.4f} -> {xulosa}")

    print("\n=== 3. Qayerda farq: oynadagi pozitsiya va uzoq kontekst ===")
    poz = np.tile(np.arange(L), len(ehtimol["GPT"][0]) // L)
    for a, b in [(0, 7), (8, 23), (24, 47)]:
        m = (poz >= a) & (poz <= b)
        q = {t: math.exp(-np.mean([np.log(e[m]).mean() for e in ehtimol[t]]))
             for t in ("LSTM", "GPT")}
        print(f"  pozitsiya {a:>2}-{b:<2}: LSTM PPL {q['LSTM']:.3f}, GPT PPL {q['GPT']:.3f}")
    joylar, ofset = [], 0
    n = len(ehtimol["GPT"][0])
    for j in val.split("\n"):
        if j.endswith(" bordi.") or j.endswith(" qaytdi."):
            k = ofset + j.rindex(" ")                    # y indeksi: fe'lning 1-harfi
            if k < n and k % L >= 16:                    # oynada kontekst yetarli
                joylar.append(k)
        ofset += len(j) + 1
    joylar = np.array(joylar)
    print(f"  'bordi'/'qaytdi' ning 1-harfi ({len(joylar)} ta, -ga/-dan ~11 belgi oldin):")
    for tur in ("LSTM", "GPT"):
        print(f"    {tur:<5} to'g'ri harf ehtimoli: "
              + ", ".join(f"{e[joylar].mean():.3f}" for e in ehtimol[tur]))
    f2 = np.array([g[joylar].mean() - l[joylar].mean()
                   for g, l in zip(ehtimol["GPT"], ehtimol["LSTM"])])
    se2 = f2.std(ddof=1) / math.sqrt(len(f2))
    print(f"    GPT - LSTM: {f2.mean():+.3f}, SE {se2:.3f} -> "
          f"{'sezilarli' if abs(f2.mean()) > 2 * se2 else 'sezilarli emas'}")

    print("\n=== 4. Hisob narxi (bir qadam, taxminiy FLOP) ===")
    tokenlar = 32 * L
    for tur in ("LSTM", "GPT"):
        torch.manual_seed(0)
        m = LSTMModel(V) if tur == "LSTM" else GPT(V)
        n_par = sum(p.numel() for p in m.parameters())
        flop = 6 * n_par * tokenlar
        if tur == "GPT":
            flop += 6 * 2 * 2 * L * L * 48 * 32          # attention: QK^T va w @ V
        print(f"  {tur:<5} ~{flop / 1e6:.0f} MFLOP/qadam; ketma-ket qadamlar: "
              f"{L if tur == 'LSTM' else 2}")
    print("  ⭐ Bir xil kichik byudjetda qaysi model yaxshi - o'lchab ko'rish kerak")


if __name__ == "__main__":
    main()

=== 1. Ikki model, bir xil sharoit ===
  LSTM  parametrlar  27901
  GPT   parametrlar  43133
  korpus 23.10 dagi kabi: V = 29, oyna L = 48, batch 32, 400 qadam
  har seed da ikkala model AYNAN bir xil batchlarni ko'radi

=== 2. Val perplexity (3 seed, juftlashgan) ===
  model  val PPL (seed 0, 1, 2)      o'rtacha  o'quv PPL
  LSTM   1.6072, 1.6239, 1.6057        1.6123     1.5939
  GPT    1.6849, 1.7310, 1.6953        1.7037     1.6864
  GPT - LSTM: +0.0915, SE 0.0085 -> LSTM sezilarli yaxshi

=== 3. Qayerda farq: oynadagi pozitsiya va uzoq kontekst ===
  pozitsiya  0-7 : LSTM PPL 2.423, GPT PPL 2.624
  pozitsiya  8-23: LSTM PPL 1.485, GPT PPL 1.572
  pozitsiya 24-47: LSTM PPL 1.487, GPT PPL 1.557
  'bordi'/'qaytdi' ning 1-harfi (84 ta, -ga/-dan ~11 belgi oldin):
    LSTM  to'g'ri harf ehtimoli: 0.887, 0.802, 0.866
    GPT   to'g'ri harf ehtimoli: 0.809, 0.886, 0.929
    GPT - LSTM: +0.023, SE 0.051 -> sezilarli emas

=== 4. Hisob narxi (bir qadam, taxminiy FLOP) ===
  LSTM  ~257 MFLOP/qadam; ketma-ket qadamlar: 48
  GPT   ~482 MFLOP/qadam; ketma-ket qadamlar: 2
  ⭐ Bir xil kichik byudjetda qaysi model yaxshi - o'lchab ko'rish kerak

"""Generatsiya strategiyalari noldan: greedy, temperature, top-k, top-p va ularning o'lchovlari."""

import math
import re

import numpy as np
import torch
import torch.nn as nn
import torch.nn.functional as F

ISMLAR = ("anvar dilnoza bobur malika sardor nodira jasur zarina otabek madina "
          "sherzod gulnora farhod laylo rustam sevara aziz kamola bahrom "
          "shahlo temur nigora dilshod feruza jamshid mohira sanjar yulduz").split()
VAQTLAR = "ertalab kechqurun bugun kecha tushda yakshanba erta indinga".split()
JOYLAR = ("bozor maktab bog' shahar qishloq kutubxona do'kon universitet "
          "choyxona dala bekat kasalxona stadion muzey teatr vokzal "
          "ofis zavod").split()
NARSALAR = ("kitob olma non qalam daftar gul choy sut anor uzum ruchka gazeta "
            "qovun tarvuz sabzi guruch go'sht shakar asal pishloq ko'ylak "
            "do'ppi soat telefon").split()
SIFATLAR = ("katta kichik yangi eski chiroyli shirin qizil oq arzon qimmat "
            "yashil sariq issiq sovuq mazali").split()
MAQOLLAR = ["sabr tagi sariq oltin.", "til qilichdan o'tkir.",
            "vaqt oltindan qimmat.", "ko'p o'qigan ko'p biladi.",
            "mehnat qilsang rohat ko'rasan.", "yaxshi so'z jon ozig'i.",
            "daraxt mevasidan odam mehnatidan.",
            "ilm olish igna bilan quduq qazish."]
L = 48


def jumla(rng):
    t = rng.integers(0, 7)
    ism, ism2 = rng.choice(ISMLAR, 2, replace=False)
    vaqt, joy = rng.choice(VAQTLAR), rng.choice(JOYLAR)
    narsa, sifat = rng.choice(NARSALAR), rng.choice(SIFATLAR)
    if t == 0:
        return f"{ism} {joy}ga {vaqt} bordi."
    if t == 1:
        return f"{ism} {joy}dan {vaqt} qaytdi."
    if t == 2:
        return f"{ism} {sifat} {narsa} sotib oldi."
    if t == 3:
        return f"{joy}da {sifat} {narsa} bor."
    if t == 4:
        return f"{ism} {ism2}ga {sifat} {narsa} berdi."
    if t == 5:
        return f"{ism} {joy}dan {narsa} olib keldi."
    return str(rng.choice(MAQOLLAR))


def korpus(n, seed):
    rng = np.random.default_rng(seed)
    return "\n".join(jumla(rng) for _ in range(n)) + "\n"


def shablon_tekshiruvchi():
    def y(lst):
        return "(?:" + "|".join(re.escape(s) for s in lst) + ")"
    i, v, j = y(ISMLAR), y(VAQTLAR), y(JOYLAR)
    n, s = y(NARSALAR), y(SIFATLAR)
    naqshlar = [f"{i} {j}ga {v} bordi\\.", f"{i} {j}dan {v} qaytdi\\.",
                f"{i} {s} {n} sotib oldi\\.", f"{j}da {s} {n} bor\\.",
                f"{i} {i}ga {s} {n} berdi\\.", f"{i} {j}dan {n} olib keldi\\.",
                y(MAQOLLAR)]
    umumiy = re.compile("|".join(f"(?:{p})" for p in naqshlar))
    return lambda jumla_: umumiy.fullmatch(jumla_) is not None


class Blok(nn.Module):
    def __init__(self, d, boshlar):
        super().__init__()
        self.boshlar = boshlar
        self.ln1, self.ln2 = nn.LayerNorm(d), nn.LayerNorm(d)
        self.qkv = nn.Linear(d, 3 * d)
        self.proj = nn.Linear(d, d)
        self.ffn = nn.Sequential(nn.Linear(d, 2 * d), nn.GELU(), nn.Linear(2 * d, d))

    def forward(self, x):
        B, T, d = x.shape
        q, k, v = self.qkv(self.ln1(x)).split(d, dim=2)
        q, k, v = [t.view(B, T, self.boshlar, -1).transpose(1, 2) for t in (q, k, v)]
        o = F.scaled_dot_product_attention(q, k, v, is_causal=True)
        x = x + self.proj(o.transpose(1, 2).reshape(B, T, d))
        return x + self.ffn(self.ln2(x))


class GPT(nn.Module):
    def __init__(self, V, d=48, boshlar=4, qatlamlar=2):
        super().__init__()
        self.emb = nn.Embedding(V, d)
        self.poz = nn.Embedding(L, d)
        self.bloklar = nn.Sequential(*[Blok(d, boshlar) for _ in range(qatlamlar)])
        self.ln = nn.LayerNorm(d)
        self.chiqish = nn.Linear(d, V)

    def forward(self, x):
        x = x[:, -L:]                        # kontekst oynasi: oxirgi L token
        h = self.emb(x) + self.poz(torch.arange(x.shape[1]))
        return self.chiqish(self.ln(self.bloklar(h)))


def orgat(T_oquv, V, seed=0, qadamlar=400, B=32):
    torch.manual_seed(seed)
    model = GPT(V)
    opt = torch.optim.AdamW(model.parameters(), lr=0.02, weight_decay=0.01)
    jadval = torch.optim.lr_scheduler.LambdaLR(
        opt, lambda s: min(1.0, (s + 1) / 40) * 0.5 * (1 + math.cos(math.pi * s / qadamlar)))
    g = torch.Generator().manual_seed(seed)
    for _ in range(qadamlar):
        bosh = torch.randint(0, len(T_oquv) - L - 1, (B,), generator=g)
        w = torch.stack([T_oquv[i:i + L + 1] for i in bosh.tolist()])
        loss = F.cross_entropy(model(w[:, :-1]).reshape(-1, V), w[:, 1:].reshape(-1))
        opt.zero_grad()
        loss.backward()
        nn.utils.clip_grad_norm_(model.parameters(), 1.0)
        opt.step()
        jadval.step()
    model.eval()
    return model


def tanla(logit, g, usul="namuna", temp=1.0, k=None, p=None):
    """logit: (B, V). greedy, temperature, top-k, top-p (nucleus) - noldan."""
    if usul == "greedy":
        return logit.argmax(-1)
    logit = logit / temp
    if k is not None:
        chegara = logit.topk(k, dim=-1).values[:, -1:]
        logit = logit.masked_fill(logit < chegara, float("-inf"))
    if p is not None:
        tartib, idx = logit.sort(dim=-1, descending=True)
        ehtimol = torch.softmax(tartib, dim=-1)
        oldingi = ehtimol.cumsum(-1) - ehtimol          # shu tokengacha yig'ilgan massa
        tartib = tartib.masked_fill(oldingi >= p, float("-inf"))
        logit = torch.full_like(logit, float("-inf")).scatter(-1, idx, tartib)
    return torch.multinomial(torch.softmax(logit, -1), 1, generator=g)[:, 0]


@torch.no_grad()
def generatsiya(model, x, qadamlar, g, **sozlama):
    """x: (B, t) boshlang'ich tokenlar; har qadamda butun oyna qayta hisoblanadi."""
    for _ in range(qadamlar):
        keyingi = tanla(model(x)[:, -1], g, **sozlama)
        x = torch.cat([x, keyingi[:, None]], 1)
    return x


def distinct(jumlalar, n):
    """distinct-n: noyob so'z n-grammlari / barcha n-grammlar."""
    hammasi = []
    for j in jumlalar:
        w = j.replace(".", " .").split()
        hammasi += [tuple(w[i:i + n]) for i in range(len(w) - n + 1)]
    return len(set(hammasi)) / max(1, len(hammasi))


def main() -> None:
    torch.set_num_threads(1)
    oquv = korpus(2000, 0)
    lugat = sorted(set(oquv + korpus(400, 1)))
    V = len(lugat)
    s2i = {c: i for i, c in enumerate(lugat)}
    model = orgat(torch.tensor([s2i[c] for c in oquv]), V)

    print("=== 1. Bitta taqsimotda strategiyalar (6 token) ===")
    p0 = torch.tensor([[0.50, 0.20, 0.15, 0.10, 0.04, 0.01]])
    logit0 = p0.log()
    for nom, sozlama in [("T = 1.0", {}), ("T = 0.5", {"temp": 0.5}),
                         ("T = 2.0", {"temp": 2.0}), ("top-k = 3", {"k": 3}),
                         ("top-p = 0.9", {"p": 0.9})]:
        n = 100000
        g = torch.Generator().manual_seed(0)
        tanlov = tanla(logit0.repeat(n, 1), g, **sozlama)
        chastota = torch.bincount(tanlov, minlength=6).float() / n
        print(f"  {nom:<12} " + " ".join(f"{x:.3f}" for x in chastota.tolist()))
    print("  greedy       har doim 0-token (ehtimoli 0.50)")
    print("  top-p = 0.9: 0.50 + 0.20 + 0.15 = 0.85 < 0.9 -> 4-token ham kerak 0.95-bob")

    print("\n=== 2. Moslashuvchanlik: top-k qat'iy, top-p taqsimotga qarab ===")
    with torch.no_grad():
        for kontekst in ["\n", "anvar bozo", "anvar bozorga ertalab b"]:
            x = torch.tensor([[s2i[c] for c in kontekst]])
            pr = torch.softmax(model(x)[0, -1], -1)
            tartib = pr.sort(descending=True).values
            yadro = int((tartib.cumsum(0) - tartib < 0.9).sum())
            entr = -(pr * pr.clamp_min(1e-12).log()).sum().item()
            print(f"  {kontekst[-12:]!r:<16} eng katta p {tartib[0].item():.3f}, "
                  f"top-p 0.9 yadrosi {yadro:>2} token, entropiya {entr:.2f}")
    print("  top-k = 5 uchala holatda ham 5 ta token qoldiradi")

    print("\n=== 3. 300 jumla har strategiya bilan ===")
    togrimi = shablon_tekshiruvchi()
    sozlar = set(oquv.replace(".", " ").split())
    oquv_jumlalar = set(oquv.strip().split("\n"))
    usullar = [("greedy", {"usul": "greedy"}), ("T=0.7", {"temp": 0.7}),
               ("T=1.0", {}), ("T=1.3", {"temp": 1.3}), ("top-k=5", {"k": 5}),
               ("top-p=0.9", {"p": 0.9})]
    print("  usul        shablon  lug'atda   noyob  distinct-2  o'quvda bor")
    olchov, namuna = {}, {}
    for nom, sozlama in usullar:
        g = torch.Generator().manual_seed(0)
        x = torch.full((300, 1), s2i["\n"])
        chiq = generatsiya(model, x, 45, g, **sozlama)
        js = ["".join(lugat[i] for i in q[1:]).split("\n")[0] for q in chiq.tolist()]
        barcha = [w for j in js for w in j.replace(".", " ").split()]
        sh = np.mean([togrimi(j) for j in js])
        lug = np.mean([w in sozlar for w in barcha])
        noyob = len(set(js)) / len(js)
        d2 = distinct(js, 2)
        bor = np.mean([j in oquv_jumlalar for j in js])
        olchov[nom] = (sh, noyob, d2)
        print(f"  {nom:<10} {sh:>8.1%} {lug:>9.1%} {noyob:>7.1%} {d2:>11.3f} {bor:>12.1%}")
        namuna[nom] = js[:2]
    print(f"  greedy: {namuna['greedy'][0]!r}, {namuna['greedy'][1]!r}")
    print(f"  top-p=0.9: {namuna['top-p=0.9'][0]!r}, {namuna['top-p=0.9'][1]!r}")

    print("\n=== 4. Xulosa (natijadan) ===")
    gr, t07, t13 = olchov["greedy"], olchov["T=0.7"], olchov["T=1.3"]
    if gr[1] < 0.01:
        print("  greedy: 300 marta bitta jumla - xilma-xillik nol")
    print(f"  T 0.7 -> 1.3: shablon {t07[0]:.1%} -> {t13[0]:.1%}, "
          f"distinct-2 {t07[2]:.3f} -> {t13[2]:.3f}")
    eng = max((n for n, _ in usullar if n != "greedy"), key=lambda n: olchov[n][0])
    print(f"  eng to'g'ri (greedy dan tashqari): {eng} - shablon {olchov[eng][0]:.1%}")
    tp, t10 = olchov["top-p=0.9"], olchov["T=1.0"]
    if tp[0] > t10[0]:
        print(f"  top-p=0.9 T=1.0 ga nisbatan: shablon {t10[0]:.1%} -> {tp[0]:.1%}, "
              f"noyob {t10[1]:.1%} -> {tp[1]:.1%}")
    print("  ⭐ Strategiya - to'g'rilik va xilma-xillik orasidagi tugma; ikkalasini o'lchang")


if __name__ == "__main__":
    main()

=== 1. Bitta taqsimotda strategiyalar (6 token) ===
  T = 1.0      0.498 0.199 0.153 0.099 0.040 0.010
  T = 0.5      0.770 0.123 0.071 0.031 0.005 0.000
  T = 2.0      0.326 0.206 0.182 0.146 0.093 0.047
  top-k = 3    0.585 0.234 0.180 0.000 0.000 0.000
  top-p = 0.9  0.524 0.209 0.161 0.105 0.000 0.000
  greedy       har doim 0-token (ehtimoli 0.50)
  top-p = 0.9: 0.50 + 0.20 + 0.15 = 0.85 < 0.9 -> 4-token ham kerak 0.95-bob

=== 2. Moslashuvchanlik: top-k qat'iy, top-p taqsimotga qarab ===
  '\n'             eng katta p 0.131, top-p 0.9 yadrosi 14 token, entropiya 2.81
  'anvar bozo'     eng katta p 0.952, top-p 0.9 yadrosi  1 token, entropiya 0.24
  'ga ertalab b'   eng katta p 0.978, top-p 0.9 yadrosi  1 token, entropiya 0.11
  top-k = 5 uchala holatda ham 5 ta token qoldiradi

=== 3. 300 jumla har strategiya bilan ===
  usul        shablon  lug'atda   noyob  distinct-2  o'quvda bor
  greedy       100.0%    100.0%    0.3%       0.003         0.0%
  T=0.7         20.3%     91.5%   99.0%       0.530         2.0%
  T=1.0          7.0%     80.0%  100.0%       0.620         1.0%
  T=1.3          2.3%     64.9%  100.0%       0.706         0.0%
  top-k=5        8.3%     83.6%   99.0%       0.555         1.0%
  top-p=0.9     17.3%     91.2%   99.7%       0.548         2.3%
  greedy: 'shahlo shahardan kechqurun qaytdi.', 'shahlo shahardan kechqurun qaytdi.'
  top-p=0.9: 'sevara qizil soat bor.', 'ot sariq sabzi sotib oldi.'

=== 4. Xulosa (natijadan) ===
  greedy: 300 marta bitta jumla - xilma-xillik nol
  T 0.7 -> 1.3: shablon 20.3% -> 2.3%, distinct-2 0.530 -> 0.706
  eng to'g'ri (greedy dan tashqari): T=0.7 - shablon 20.3%
  top-p=0.9 T=1.0 ga nisbatan: shablon 7.0% -> 17.3%, noyob 100.0% -> 99.7%
  ⭐ Strategiya - to'g'rilik va xilma-xillik orasidagi tugma; ikkalasini o'lchang

"""Takrorlanish muammosi: uzun matn generatsiyasida distinct-n va takror ulushi."""

import math
import re

import numpy as np
import torch
import torch.nn as nn
import torch.nn.functional as F

ISMLAR = ("anvar dilnoza bobur malika sardor nodira jasur zarina otabek madina "
          "sherzod gulnora farhod laylo rustam sevara aziz kamola bahrom "
          "shahlo temur nigora dilshod feruza jamshid mohira sanjar yulduz").split()
VAQTLAR = "ertalab kechqurun bugun kecha tushda yakshanba erta indinga".split()
JOYLAR = ("bozor maktab bog' shahar qishloq kutubxona do'kon universitet "
          "choyxona dala bekat kasalxona stadion muzey teatr vokzal "
          "ofis zavod").split()
NARSALAR = ("kitob olma non qalam daftar gul choy sut anor uzum ruchka gazeta "
            "qovun tarvuz sabzi guruch go'sht shakar asal pishloq ko'ylak "
            "do'ppi soat telefon").split()
SIFATLAR = ("katta kichik yangi eski chiroyli shirin qizil oq arzon qimmat "
            "yashil sariq issiq sovuq mazali").split()
MAQOLLAR = ["sabr tagi sariq oltin.", "til qilichdan o'tkir.",
            "vaqt oltindan qimmat.", "ko'p o'qigan ko'p biladi.",
            "mehnat qilsang rohat ko'rasan.", "yaxshi so'z jon ozig'i.",
            "daraxt mevasidan odam mehnatidan.",
            "ilm olish igna bilan quduq qazish."]
L = 48


def jumla(rng):
    t = rng.integers(0, 7)
    ism, ism2 = rng.choice(ISMLAR, 2, replace=False)
    vaqt, joy = rng.choice(VAQTLAR), rng.choice(JOYLAR)
    narsa, sifat = rng.choice(NARSALAR), rng.choice(SIFATLAR)
    if t == 0:
        return f"{ism} {joy}ga {vaqt} bordi."
    if t == 1:
        return f"{ism} {joy}dan {vaqt} qaytdi."
    if t == 2:
        return f"{ism} {sifat} {narsa} sotib oldi."
    if t == 3:
        return f"{joy}da {sifat} {narsa} bor."
    if t == 4:
        return f"{ism} {ism2}ga {sifat} {narsa} berdi."
    if t == 5:
        return f"{ism} {joy}dan {narsa} olib keldi."
    return str(rng.choice(MAQOLLAR))


def korpus(n, seed):
    rng = np.random.default_rng(seed)
    return "\n".join(jumla(rng) for _ in range(n)) + "\n"


def shablon_tekshiruvchi():
    def y(lst):
        return "(?:" + "|".join(re.escape(s) for s in lst) + ")"
    i, v, j = y(ISMLAR), y(VAQTLAR), y(JOYLAR)
    n, s = y(NARSALAR), y(SIFATLAR)
    naqshlar = [f"{i} {j}ga {v} bordi\\.", f"{i} {j}dan {v} qaytdi\\.",
                f"{i} {s} {n} sotib oldi\\.", f"{j}da {s} {n} bor\\.",
                f"{i} {i}ga {s} {n} berdi\\.", f"{i} {j}dan {n} olib keldi\\.",
                y(MAQOLLAR)]
    umumiy = re.compile("|".join(f"(?:{p})" for p in naqshlar))
    return lambda jumla_: umumiy.fullmatch(jumla_) is not None


class Blok(nn.Module):
    def __init__(self, d, boshlar):
        super().__init__()
        self.boshlar = boshlar
        self.ln1, self.ln2 = nn.LayerNorm(d), nn.LayerNorm(d)
        self.qkv = nn.Linear(d, 3 * d)
        self.proj = nn.Linear(d, d)
        self.ffn = nn.Sequential(nn.Linear(d, 2 * d), nn.GELU(), nn.Linear(2 * d, d))

    def forward(self, x):
        B, T, d = x.shape
        q, k, v = self.qkv(self.ln1(x)).split(d, dim=2)
        q, k, v = [t.view(B, T, self.boshlar, -1).transpose(1, 2) for t in (q, k, v)]
        o = F.scaled_dot_product_attention(q, k, v, is_causal=True)
        x = x + self.proj(o.transpose(1, 2).reshape(B, T, d))
        return x + self.ffn(self.ln2(x))


class GPT(nn.Module):
    def __init__(self, V, d=48, boshlar=4, qatlamlar=2):
        super().__init__()
        self.emb = nn.Embedding(V, d)
        self.poz = nn.Embedding(L, d)
        self.bloklar = nn.Sequential(*[Blok(d, boshlar) for _ in range(qatlamlar)])
        self.ln = nn.LayerNorm(d)
        self.chiqish = nn.Linear(d, V)

    def forward(self, x):
        x = x[:, -L:]                        # kontekst oynasi: oxirgi L token
        h = self.emb(x) + self.poz(torch.arange(x.shape[1]))
        return self.chiqish(self.ln(self.bloklar(h)))


def orgat(T_oquv, V, seed=0, qadamlar=400, B=32):
    torch.manual_seed(seed)
    model = GPT(V)
    opt = torch.optim.AdamW(model.parameters(), lr=0.02, weight_decay=0.01)
    jadval = torch.optim.lr_scheduler.LambdaLR(
        opt, lambda s: min(1.0, (s + 1) / 40) * 0.5 * (1 + math.cos(math.pi * s / qadamlar)))
    g = torch.Generator().manual_seed(seed)
    for _ in range(qadamlar):
        bosh = torch.randint(0, len(T_oquv) - L - 1, (B,), generator=g)
        w = torch.stack([T_oquv[i:i + L + 1] for i in bosh.tolist()])
        loss = F.cross_entropy(model(w[:, :-1]).reshape(-1, V), w[:, 1:].reshape(-1))
        opt.zero_grad()
        loss.backward()
        nn.utils.clip_grad_norm_(model.parameters(), 1.0)
        opt.step()
        jadval.step()
    model.eval()
    return model


def tanla(logit, g, usul="namuna", temp=1.0, k=None, p=None):
    """logit: (B, V). greedy, temperature, top-k, top-p (nucleus) - noldan."""
    if usul == "greedy":
        return logit.argmax(-1)
    logit = logit / temp
    if k is not None:
        chegara = logit.topk(k, dim=-1).values[:, -1:]
        logit = logit.masked_fill(logit < chegara, float("-inf"))
    if p is not None:
        tartib, idx = logit.sort(dim=-1, descending=True)
        ehtimol = torch.softmax(tartib, dim=-1)
        oldingi = ehtimol.cumsum(-1) - ehtimol          # shu tokengacha yig'ilgan massa
        tartib = tartib.masked_fill(oldingi >= p, float("-inf"))
        logit = torch.full_like(logit, float("-inf")).scatter(-1, idx, tartib)
    return torch.multinomial(torch.softmax(logit, -1), 1, generator=g)[:, 0]


@torch.no_grad()
def generatsiya(model, x, qadamlar, g, **sozlama):
    """x: (B, t) boshlang'ich tokenlar; har qadamda butun oyna qayta hisoblanadi."""
    for _ in range(qadamlar):
        keyingi = tanla(model(x)[:, -1], g, **sozlama)
        x = torch.cat([x, keyingi[:, None]], 1)
    return x


def jumlalarga(matn):
    """Birinchi to'liq bo'lmagan va oxirgi kesilgan jumlani tashlab yuboramiz."""
    qism = matn.split("\n")
    return [j for j in qism[1:-1] if j]


def olchovlar(matnlar):
    """takror: matn ichida oldin uchragan jumlaning aynan qaytishi ulushi.
    distinct-n: HAR MATN ichida noyob so'z n-grammlari ulushi (o'rtacha)."""
    takror, d1, d2 = [], [], []
    for m in matnlar:
        js = jumlalarga(m)
        korilgan = set()
        for j in js:
            takror.append(j in korilgan)
            korilgan.add(j)
        w = m.replace("\n", " ").replace(".", " .").split()
        for n, lst in ((1, d1), (2, d2)):
            ng = [tuple(w[i:i + n]) for i in range(len(w) - n + 1)]
            lst.append(len(set(ng)) / len(ng))
    return np.mean(takror), np.mean(d1), np.mean(d2)


@torch.no_grad()
def aralash(model, x, qadamlar, g, yangi_qator):
    """Jumla boshida (oldingi token '\n') namuna olish, qolgan joyda greedy."""
    for _ in range(qadamlar):
        logit = model(x)[:, -1]
        namuna = tanla(logit, g)
        keyingi = torch.where(x[:, -1] == yangi_qator, namuna, logit.argmax(-1))
        x = torch.cat([x, keyingi[:, None]], 1)
    return x


def main() -> None:
    torch.set_num_threads(1)
    oquv, val = korpus(2000, 0), korpus(400, 1)
    lugat = sorted(set(oquv + val))
    V = len(lugat)
    s2i = {c: i for i, c in enumerate(lugat)}
    model = orgat(torch.tensor([s2i[c] for c in oquv]), V)
    uzunlik, n_matn = 300, 30

    print("=== 1. Uzun matn: 30 ta boshlanish, har biri 300 belgi ===")
    val_j = val.strip().split("\n")
    boshlar = ["\n" + val_j[i] + "\n" for i in range(n_matn)]
    x0 = [torch.tensor([s2i[c] for c in b]) for b in boshlar]
    uz0 = min(len(t) for t in x0)
    x0 = torch.stack([t[-uz0:] for t in x0])              # bir xil uzunlikka kesamiz
    print(f"  boshlanish - val dagi haqiqiy jumla, masalan: {boshlar[0].strip()!r}")
    print(f"  kontekst oynasi L = {L}: uzun matnda model faqat oxirgi {L} belgini ko'radi")

    usullar = [("greedy", {"usul": "greedy"}), ("T=0.7", {"temp": 0.7}),
               ("T=1.0", {}), ("top-p=0.9", {"p": 0.9})]
    natija, matnlar = {}, {}
    for nom, sozlama in usullar:
        g = torch.Generator().manual_seed(0)
        chiq = generatsiya(model, x0, uzunlik, g, **sozlama)
        ms = ["".join(lugat[i] for i in q[uz0:]) for q in chiq.tolist()]
        matnlar[nom] = ms
        natija[nom] = olchovlar(ms)
    g = torch.Generator().manual_seed(0)
    chiq = aralash(model, x0, uzunlik, g, s2i["\n"])
    matnlar["aralash"] = ["".join(lugat[i] for i in q[uz0:]) for q in chiq.tolist()]
    natija["aralash"] = olchovlar(matnlar["aralash"])
    rng = np.random.default_rng(5)
    haqiqiy = []
    for _ in range(n_matn):
        b = int(rng.integers(0, len(oquv) - uzunlik))
        haqiqiy.append(oquv[b:b + uzunlik])
    natija["korpus (haqiqiy)"] = olchovlar(haqiqiy)

    print("\n=== 2. Greedy matnning boshlanishi ===")
    for q in matnlar["greedy"][0].split("\n")[1:6]:
        print(f"    {q}")

    print("\n=== 3. Takrorlanish o'lchovlari (30 matn o'rtachasi) ===")
    togrimi = shablon_tekshiruvchi()
    print(f"  {'manba':<17} {'takror ulushi':>14} {'distinct-1':>11} {'distinct-2':>11} "
          f"{'shablon':>8}")
    for nom, (t, d1, d2) in natija.items():
        ms = matnlar.get(nom, haqiqiy)
        sh = np.mean([togrimi(j) for m in ms for j in jumlalarga(m)])
        print(f"  {nom:<17} {t:>14.1%} {d1:>11.3f} {d2:>11.3f} {sh:>8.1%}")
    print("  aralash: jumla boshida namuna (T=1.0), jumla ichida greedy")
    print("  takror ulushi: matndagi jumla shu matnda OLDIN aynan uchraganmi")

    print("\n=== 4. Greedy sikli: davr uzunligi ===")
    davrlar = []
    for m in matnlar["greedy"]:
        js = jumlalarga(m)
        davr = None
        for i in range(len(js)):
            for d in range(1, 4):
                if i + 2 * d <= len(js) and js[i:i + d] == js[i + d:i + 2 * d]:
                    davr = d
                    break
            if davr:
                break
        davrlar.append(davr)
    sanoq = {d: davrlar.count(d) for d in (1, 2, 3, None)}
    print(f"  davr 1 jumla: {sanoq[1]}, 2 jumla: {sanoq[2]}, 3 jumla: {sanoq[3]}, "
          f"sikl topilmadi: {sanoq[None]}  (30 matndan)")
    t_gr, t_tp, t_k = natija["greedy"][0], natija["top-p=0.9"][0], natija["korpus (haqiqiy)"][0]
    if t_gr > 5 * max(t_tp, 0.01):
        print(f"  greedy takrori {t_gr:.1%}, top-p {t_tp:.1%}, haqiqiy matnda {t_k:.1%}")
        print("  deterministik tanlov + bir xil kontekst -> bir xil davom: sikl")
    print("  ⭐ Greedy uzun matnda siklga tushadi; namuna olish sikldan chiqaradi")


if __name__ == "__main__":
    main()

=== 1. Uzun matn: 30 ta boshlanish, har biri 300 belgi ===
  boshlanish - val dagi haqiqiy jumla, masalan: "bog'da mazali pishloq bor."
  kontekst oynasi L = 48: uzun matnda model faqat oxirgi 48 belgini ko'radi

=== 2. Greedy matnning boshlanishi ===
    sanjar sariq sotib oldi.
    sanjar sariq sotib oldi.
    sanjar sariq sotib oldi.
    sanjar sariq sotib oldi.
    sanjar sariq sotib oldi.

=== 3. Takrorlanish o'lchovlari (30 matn o'rtachasi) ===
  manba              takror ulushi  distinct-1  distinct-2  shablon
  greedy                     89.8%       0.121       0.140     0.3%
  T=0.7                       0.0%       0.686       0.875    16.3%
  T=1.0                       0.0%       0.720       0.901     6.7%
  top-p=0.9                   0.0%       0.707       0.897    11.9%
  aralash                    17.5%       0.432       0.592    38.3%
  korpus (haqiqiy)            1.5%       0.706       0.896   100.0%
  aralash: jumla boshida namuna (T=1.0), jumla ichida greedy
  takror ulushi: matndagi jumla shu matnda OLDIN aynan uchraganmi

=== 4. Greedy sikli: davr uzunligi ===
  davr 1 jumla: 30, 2 jumla: 0, 3 jumla: 0, sikl topilmadi: 0  (30 matndan)
  greedy takrori 89.8%, top-p 0.0%, haqiqiy matnda 1.5%
  deterministik tanlov + bir xil kontekst -> bir xil davom: sikl
  ⭐ Greedy uzun matnda siklga tushadi; namuna olish sikldan chiqaradi

"""Deterministik sampling: urug', batch tarkibi tuzog'i va prompt bilan shartli generatsiya."""

import math
import re

import numpy as np
import torch
import torch.nn as nn
import torch.nn.functional as F

ISMLAR = ("anvar dilnoza bobur malika sardor nodira jasur zarina otabek madina "
          "sherzod gulnora farhod laylo rustam sevara aziz kamola bahrom "
          "shahlo temur nigora dilshod feruza jamshid mohira sanjar yulduz").split()
VAQTLAR = "ertalab kechqurun bugun kecha tushda yakshanba erta indinga".split()
JOYLAR = ("bozor maktab bog' shahar qishloq kutubxona do'kon universitet "
          "choyxona dala bekat kasalxona stadion muzey teatr vokzal "
          "ofis zavod").split()
NARSALAR = ("kitob olma non qalam daftar gul choy sut anor uzum ruchka gazeta "
            "qovun tarvuz sabzi guruch go'sht shakar asal pishloq ko'ylak "
            "do'ppi soat telefon").split()
SIFATLAR = ("katta kichik yangi eski chiroyli shirin qizil oq arzon qimmat "
            "yashil sariq issiq sovuq mazali").split()
MAQOLLAR = ["sabr tagi sariq oltin.", "til qilichdan o'tkir.",
            "vaqt oltindan qimmat.", "ko'p o'qigan ko'p biladi.",
            "mehnat qilsang rohat ko'rasan.", "yaxshi so'z jon ozig'i.",
            "daraxt mevasidan odam mehnatidan.",
            "ilm olish igna bilan quduq qazish."]
L = 48


def jumla(rng):
    t = rng.integers(0, 7)
    ism, ism2 = rng.choice(ISMLAR, 2, replace=False)
    vaqt, joy = rng.choice(VAQTLAR), rng.choice(JOYLAR)
    narsa, sifat = rng.choice(NARSALAR), rng.choice(SIFATLAR)
    if t == 0:
        return f"{ism} {joy}ga {vaqt} bordi."
    if t == 1:
        return f"{ism} {joy}dan {vaqt} qaytdi."
    if t == 2:
        return f"{ism} {sifat} {narsa} sotib oldi."
    if t == 3:
        return f"{joy}da {sifat} {narsa} bor."
    if t == 4:
        return f"{ism} {ism2}ga {sifat} {narsa} berdi."
    if t == 5:
        return f"{ism} {joy}dan {narsa} olib keldi."
    return str(rng.choice(MAQOLLAR))


def korpus(n, seed):
    rng = np.random.default_rng(seed)
    return "\n".join(jumla(rng) for _ in range(n)) + "\n"


def shablon_tekshiruvchi():
    def y(lst):
        return "(?:" + "|".join(re.escape(s) for s in lst) + ")"
    i, v, j = y(ISMLAR), y(VAQTLAR), y(JOYLAR)
    n, s = y(NARSALAR), y(SIFATLAR)
    naqshlar = [f"{i} {j}ga {v} bordi\\.", f"{i} {j}dan {v} qaytdi\\.",
                f"{i} {s} {n} sotib oldi\\.", f"{j}da {s} {n} bor\\.",
                f"{i} {i}ga {s} {n} berdi\\.", f"{i} {j}dan {n} olib keldi\\.",
                y(MAQOLLAR)]
    umumiy = re.compile("|".join(f"(?:{p})" for p in naqshlar))
    return lambda jumla_: umumiy.fullmatch(jumla_) is not None


class Blok(nn.Module):
    def __init__(self, d, boshlar):
        super().__init__()
        self.boshlar = boshlar
        self.ln1, self.ln2 = nn.LayerNorm(d), nn.LayerNorm(d)
        self.qkv = nn.Linear(d, 3 * d)
        self.proj = nn.Linear(d, d)
        self.ffn = nn.Sequential(nn.Linear(d, 2 * d), nn.GELU(), nn.Linear(2 * d, d))

    def forward(self, x):
        B, T, d = x.shape
        q, k, v = self.qkv(self.ln1(x)).split(d, dim=2)
        q, k, v = [t.view(B, T, self.boshlar, -1).transpose(1, 2) for t in (q, k, v)]
        o = F.scaled_dot_product_attention(q, k, v, is_causal=True)
        x = x + self.proj(o.transpose(1, 2).reshape(B, T, d))
        return x + self.ffn(self.ln2(x))


class GPT(nn.Module):
    def __init__(self, V, d=48, boshlar=4, qatlamlar=2):
        super().__init__()
        self.emb = nn.Embedding(V, d)
        self.poz = nn.Embedding(L, d)
        self.bloklar = nn.Sequential(*[Blok(d, boshlar) for _ in range(qatlamlar)])
        self.ln = nn.LayerNorm(d)
        self.chiqish = nn.Linear(d, V)

    def forward(self, x):
        x = x[:, -L:]                        # kontekst oynasi: oxirgi L token
        h = self.emb(x) + self.poz(torch.arange(x.shape[1]))
        return self.chiqish(self.ln(self.bloklar(h)))


def orgat(T_oquv, V, seed=0, qadamlar=400, B=32):
    torch.manual_seed(seed)
    model = GPT(V)
    opt = torch.optim.AdamW(model.parameters(), lr=0.02, weight_decay=0.01)
    jadval = torch.optim.lr_scheduler.LambdaLR(
        opt, lambda s: min(1.0, (s + 1) / 40) * 0.5 * (1 + math.cos(math.pi * s / qadamlar)))
    g = torch.Generator().manual_seed(seed)
    for _ in range(qadamlar):
        bosh = torch.randint(0, len(T_oquv) - L - 1, (B,), generator=g)
        w = torch.stack([T_oquv[i:i + L + 1] for i in bosh.tolist()])
        loss = F.cross_entropy(model(w[:, :-1]).reshape(-1, V), w[:, 1:].reshape(-1))
        opt.zero_grad()
        loss.backward()
        nn.utils.clip_grad_norm_(model.parameters(), 1.0)
        opt.step()
        jadval.step()
    model.eval()
    return model


def tanla(logit, g, usul="namuna", temp=1.0, k=None, p=None):
    """logit: (B, V). greedy, temperature, top-k, top-p (nucleus) - noldan."""
    if usul == "greedy":
        return logit.argmax(-1)
    logit = logit / temp
    if k is not None:
        chegara = logit.topk(k, dim=-1).values[:, -1:]
        logit = logit.masked_fill(logit < chegara, float("-inf"))
    if p is not None:
        tartib, idx = logit.sort(dim=-1, descending=True)
        ehtimol = torch.softmax(tartib, dim=-1)
        oldingi = ehtimol.cumsum(-1) - ehtimol          # shu tokengacha yig'ilgan massa
        tartib = tartib.masked_fill(oldingi >= p, float("-inf"))
        logit = torch.full_like(logit, float("-inf")).scatter(-1, idx, tartib)
    return torch.multinomial(torch.softmax(logit, -1), 1, generator=g)[:, 0]


@torch.no_grad()
def generatsiya(model, x, qadamlar, g, **sozlama):
    """x: (B, t) boshlang'ich tokenlar; har qadamda butun oyna qayta hisoblanadi."""
    for _ in range(qadamlar):
        keyingi = tanla(model(x)[:, -1], g, **sozlama)
        x = torch.cat([x, keyingi[:, None]], 1)
    return x


def matnga(lugat, qator):
    return "".join(lugat[i] for i in qator).split("\n")[0]


@torch.no_grad()
def qatorma_qator(model, x, qadamlar, urug, **sozlama):
    """Har qator O'Z generatori bilan: natija batch tarkibiga bog'liq emas."""
    chiq = []
    for i in range(len(x)):
        g = torch.Generator().manual_seed(urug + i)
        chiq.append(generatsiya(model, x[i:i + 1], qadamlar, g, **sozlama)[0])
    return torch.stack(chiq)


def main() -> None:
    torch.set_num_threads(1)
    oquv = korpus(2000, 0)
    lugat = sorted(set(oquv + korpus(400, 1)))
    V = len(lugat)
    s2i = {c: i for i, c in enumerate(lugat)}
    model = orgat(torch.tensor([s2i[c] for c in oquv]), V)
    bosh = torch.full((8, 1), s2i["\n"])

    print("=== 1. Urug' va takrorlanuvchanlik (top-p = 0.9) ===")
    a = generatsiya(model, bosh, 40, torch.Generator().manual_seed(7), p=0.9)
    torch.manual_seed(12345)                               # global urug'ni o'zgartiramiz
    b = generatsiya(model, bosh, 40, torch.Generator().manual_seed(7), p=0.9)
    c = generatsiya(model, bosh, 40, torch.Generator().manual_seed(8), p=0.9)
    print(f"  urug' 7 va yana urug' 7 (global urug' boshqa): {torch.equal(a, b)}")
    print(f"  urug' 7 va urug' 8: bir xil qatorlar {int((a == c).all(1).sum())} / 8")
    for q in a[:3].tolist():
        print(f"    {matnga(lugat, q[1:])}")

    print("\n=== 2. Tuzoq: bitta generator va batch tarkibi ===")
    yolgiz = generatsiya(model, bosh[:1], 40, torch.Generator().manual_seed(7), p=0.9)
    print(f"  batch (8 ta) ichidagi 0-qator: {matnga(lugat, a[0, 1:].tolist())!r}")
    print(f"  xuddi shu urug', yolg'iz:      {matnga(lugat, yolgiz[0, 1:].tolist())!r}")
    print(f"  bir xilmi: {torch.equal(a[0], yolgiz[0])}")
    q8 = qatorma_qator(model, bosh, 40, 100, p=0.9)
    q3 = qatorma_qator(model, bosh[:3], 40, 100, p=0.9)
    print(f"  har qatorga o'z generatori: 8 talik va 3 talik batchda "
          f"birinchi 3 qator bir xil: {torch.equal(q8[:3], q3)}")

    print("\n=== 3. Chegaraviy holatlar: hammasi greedy ga teng bo'lishi kerak ===")
    gr = generatsiya(model, bosh, 40, torch.Generator().manual_seed(0), usul="greedy")
    k1 = generatsiya(model, bosh, 40, torch.Generator().manual_seed(0), k=1)
    p0 = generatsiya(model, bosh, 40, torch.Generator().manual_seed(0), p=1e-9)
    t0 = generatsiya(model, bosh, 40, torch.Generator().manual_seed(0), temp=1e-3)
    print(f"  top-k = 1 == greedy: {torch.equal(gr, k1)}")
    print(f"  top-p -> 0 == greedy: {torch.equal(gr, p0)}")
    print(f"  T = 0.001 == greedy: {torch.equal(gr, t0)}")

    print("\n=== 4. Prompt bilan shartli generatsiya: -ga ... bordi / -dan ... qaytdi ===")
    rng = np.random.default_rng(3)
    for qoshimcha, fel in (("ga", "bordi."), ("dan", "qaytdi.")):
        promptlar = [f"\n{rng.choice(ISMLAR)} {rng.choice(JOYLAR)}{qoshimcha} "
                     f"{rng.choice(VAQTLAR)} " for _ in range(100)]
        uz = min(len(p) for p in promptlar)
        natija = {}
        with torch.no_grad():
            ehtimol = np.mean([torch.softmax(model(torch.tensor([[s2i[c] for c in p]]))[0, -1],
                                             -1)[s2i[fel[0]]].item() for p in promptlar])
        for nom, sozlama, urug in (("greedy", {"usul": "greedy"}, "0"),
                                   ("top-p, bitta urug'", {"p": 0.9}, "0"),
                                   ("top-p, o'z urug'i", {"p": 0.9}, "i")):
            togri = 0
            for i, p in enumerate(promptlar):
                x = torch.tensor([[s2i[c] for c in p]])
                g = torch.Generator().manual_seed(0 if urug == "0" else i)
                davom = matnga(lugat, generatsiya(model, x, 10, g, **sozlama)[0, len(p):].tolist())
                togri += davom == fel
            natija[nom] = togri / len(promptlar)
        print(f"  '<ism> <joy>{qoshimcha} <vaqt> ' -> {fel!r}: o'rtacha P({fel[0]!r}) = {ehtimol:.3f}")
        for nom, v in natija.items():
            print(f"      {nom:<19} to'g'ri davom {v:.2f}")
    print(f"  (100 tadan prompt, eng qisqasi {uz} belgi)")
    print("  bitta urug' hamma promptga: birinchi tasodifiy son hammasida bir xil -")
    print("  namunalar korrelyatsiyalangan, baho tasodifiy tomonga siljiydi")
    print("  ⭐ torch.Generator + har qatorga o'z urug'i = takrorlanadigan generatsiya")


if __name__ == "__main__":
    main()

=== 1. Urug' va takrorlanuvchanlik (top-p = 0.9) ===
  urug' 7 va yana urug' 7 (global urug' boshqa): True
  urug' 7 va urug' 8: bir xil qatorlar 0 / 8
    madina chiroyli sotib oldi.
    mohira qishloq ko'ylak sotib oldi.
    madina ruchka asal berdi.

=== 2. Tuzoq: bitta generator va batch tarkibi ===
  batch (8 ta) ichidagi 0-qator: 'madina chiroyli sotib oldi.'
  xuddi shu urug', yolg'iz:      'mehna bur qaytdi.'
  bir xilmi: False
  har qatorga o'z generatori: 8 talik va 3 talik batchda birinchi 3 qator bir xil: True

=== 3. Chegaraviy holatlar: hammasi greedy ga teng bo'lishi kerak ===
  top-k = 1 == greedy: True
  top-p -> 0 == greedy: True
  T = 0.001 == greedy: True

=== 4. Prompt bilan shartli generatsiya: -ga ... bordi / -dan ... qaytdi ===
  '<ism> <joy>ga <vaqt> ' -> 'bordi.': o'rtacha P('b') = 0.764
      greedy              to'g'ri davom 0.90
      top-p, bitta urug'  to'g'ri davom 0.42
      top-p, o'z urug'i   to'g'ri davom 0.69
  '<ism> <joy>dan <vaqt> ' -> 'qaytdi.': o'rtacha P('q') = 0.866
      greedy              to'g'ri davom 0.98
      top-p, bitta urug'  to'g'ri davom 1.00
      top-p, o'z urug'i   to'g'ri davom 0.88
  (100 tadan prompt, eng qisqasi 21 belgi)
  bitta urug' hamma promptga: birinchi tasodifiy son hammasida bir xil -
  namunalar korrelyatsiyalangan, baho tasodifiy tomonga siljiydi
  ⭐ torch.Generator + har qatorga o'z urug'i = takrorlanadigan generatsiya

logit = model(x)                       # x.shape[1] > L -> xato     # ⚠️
logit = model(x[:, -L:])                                            # ✅

logit = model(x[:, -1:])               # GPT holat saqlamaydi       # ⚠️
logit = model(x[:, -L:])[:, -1]                                     # ✅

tartib[p_t.cumsum(-1) > p] = float("-inf")                          # ⚠️
tartib[p_t.cumsum(-1) - p_t >= p] = float("-inf")                   # ✅

p = torch.softmax(logit, -1) / T                                    # ⚠️
p = torch.softmax(logit / T, -1)                                    # ✅

torch.multinomial(p, 1)                                             # ⚠️
torch.multinomial(p, 1, generator=g)                                # ✅

g = torch.Generator().manual_seed(7); generatsiya(model, x_batch, n, g)    # ⚠️
[generatsiya(model, x[i:i + 1], n, torch.Generator().manual_seed(7 + i))
 for i in range(len(x))]                                            # ✅

matn = generatsiya(model, prompt, 300, g, usul="greedy")            # ⚠️
matn = generatsiya(model, prompt, 300, g, p=0.9, temp=0.8)          # ✅

1.  # GPT va 24.7 dagi decoder-only farqi?
2.  # GPT ning o'rgatish maqsadi 23.10 dagidan qanday farq qiladi?
3.  # pozitsiya embeddingi nn.Embedding(48, d) bo'lsa, 60 belgili kirish?
4.  # [0.5, 0.2, 0.15, 0.1, 0.04, 0.01] da top-p = 0.9 nechta token qoldiradi?
5.  # xuddi shu taqsimotda top-k = 2 dan keyingi ehtimollar?
6.  # T -> 0 da namuna olish nimaga aylanadi?
7.  # top-k = 1 nimaga teng?
8.  # nega greedy uzun matnda siklga tushadi?
9.  # distinct-2 formulasi?
10. # bitta generator bilan 8 talik batchning 0-qatori yolg'iz generatsiyaga tengmi?
11. # juftlashgan taqqoslashda "sezilarli" mezoni?
12. # nega kichik tajribada LSTM GPT dan yaxshi bo'lishi mumkin?

1.  for _ in range(300):
        logit = model(x)[:, -1]
        x = torch.cat([x, logit.argmax(-1, keepdim=True)], 1)

2.  p = torch.softmax(logit, -1)
    p[p.cumsum(-1) > 0.9] = 0
    keyingi = torch.multinomial(p / p.sum(-1, keepdim=True), 1)

3.  g = torch.Generator().manual_seed(0)
    for prompt in promptlar:
        g = torch.Generator().manual_seed(0)
        natija.append(generatsiya(model, prompt, 10, g, p=0.9))

4.  ppl_gpt = orgat_gpt(seed=0); ppl_lstm = orgat_lstm(seed=1)
    print("GPT yaxshi" if ppl_gpt < ppl_lstm else "LSTM yaxshi")

5.  p = torch.softmax(logit, -1) ** (1 / T)