Algoritmlar real ishda: kesh, noaniq qidiruv, diff, pagination, rate limiting va debounce

Qisqacha: Ishda algoritm "masala" ko'rinishida kelmaydi — u kesh, qidiruv, ro'yxatni yangilash, sahifalash va so'rovlarni cheklash ko'rinishida keladi. LRU kesh — Map tartibi, noaniq qidiruv — tahrir masofasi, kalitli diff — Map bilan O(n), kursorli pagination — binary search, rate limiting — token bucket. Lekin birinchi qoida boshqa: avval o'lchang. vazifalar da 1 000 vazifada qidiruvning o'zi 2,2 ms, ro'yxatni qayta chizish esa ~50 ms oldi. Tezlashtirish kerak bo'lgan joy algoritm emas, chizish ekan.

Bu darsda

• Haqiqiy ilova o'lchovidan "qaysi qism sekin?" degan savolga javob topasiz va debounce qachon foyda bermasligini tushuntira olasiz.
• Noaniq qidiruv, kalitli diff va kursorli pagination'da 14-qism naqshlarini taniysiz.
• Token bucket bilan so'rovlarni cheklaydigan kod yozasiz va uni xususiyat testi bilan tekshirasiz.
• 14-qismni yakunlab, o'zingizni tekshirish ro'yxati bo'yicha baholaysiz.

Oldin bilishingiz kerak: LeetCode uslubidagi muntazam mashq, Debounce va throttle, Hash tuzilmalari JS'da va LRU kesh, 2D DP masalalari.

1. Nega bu kerak?

Sardor so'radi: "Jasur aka, men 60 ta algoritm darsini o'tdim. Lekin «Bahor» saytida hech qachon graf chizmadim va knapsack yechmadim. Bu ishda kerakmi o'zi?"

Jasur aka kulib javob berdi: "Har kuni kerak, faqat boshqa nom bilan." Saytdagi qidiruv — matn algoritmi. Menyu sahifalarini eslab qolish — kesh. Ro'yxatda faqat o'zgargan qatorni yangilash — diff. "Yana yuklash" tugmasi — pagination. Serverni ortiqcha so'rovlardan himoyalash — rate limiting. Ularning ichida 14-qismning naqshlari ishlaydi: Map, binary search, DP, oyna.

Bugun shu beshtasini ko'ramiz. Lekin avval eng muhim saboqni — haqiqiy ilovada qayerga qarash kerakligini. Buning uchun vazifalar ilovasining 14-qismdagi o'lchovlarini olamiz.

2. Avval o'lchang: vazifalar dan saboq

2.1 Vaqt qayerga ketadi?

14-qismda vazifalar v4.1 ga uchta algoritm qo'shildi: qidiruv (Matn algoritmlari), ko'p kalitli saralash (Saralash tushunchalari) va teg takliflari uchun Trie (Trie). Keyin har amal o'lchandi: alohida Node'da (faqat algoritm) va Chrome'da (algoritm + ekranni qayta chizish). 1 000 vazifada natija:

Grafikda farq yaqqol: qidiruvning o'zi 2,2 ms, foydalanuvchi esa 50–56 ms kutadi. Vaqtning 95 foizdan ko'prog'i — render(), ya'ni ro'yxatni noldan qayta qurish. Uni qancha tezlashtirmang, qidiruv algoritmini O(1) qilsangiz ham, foydalanuvchi farqni sezmaydi.

2.2 Big-O va haqiqiy raqamlar

O'sha o'lchovdan yana bir saboq. Vazifalar 100 baravar ko'payganda (1 000 → 100 000) O(n) amallar nazariyadagidek 100 emas, 200–500 baravar sekinlashdi. Sabab — konstantalar. 100 000 vazifa (~10 MB) protsessor keshiga sig'maydi (Massiv xotirada) va axlat yig'uvchi ko'proq ishlaydi. O(n log n) saralash esa kutilgan ×166 o'rniga ×108–139 sekinlashdi: JavaScript'ning saralashi qisman tartiblangan ma'lumotdan foydalanadi.

Big-O shaklni to'g'ri aytdi: chiziqli amallar chiziqli o'sdi. Lekin aniq soniyalarni faqat o'lchov aytadi. Shuning uchun real ishda tartib doim bir xil:

1. O'lchang — qaysi qism sekin?
2. Sababini toping — algoritm (Big-O), konstanta yoki chizish/tarmoq.
3. Faqat o'sha qismni tuzating va yana o'lchang.

3. Debounce: qachon kerak, qachon emas

Debounce va throttle darsida debounce'ni o'rgangan edik: hodisalar to'xtagandan keyin bir marta chaqirish. vazifalar qidiruvida esa debounce yo'q va bu ataylab qilingan qaror. Nega?

Debounce chaqiruvlar sonini kamaytiradi, bitta chaqiruvning narxini emas. Uning ishini qog'ozda hisoblaymiz. Mijoz lag'mon ni yozdi — 7 ta tugma, har 120 ms da:

// Debounce'ni vaqtsiz, "qog'ozda" hisoblaymiz: qachon chaqiriladi?
function debounceCalls(keyTimes, wait) {
  const calls = [];
  for (let i = 0; i < keyTimes.length; i++) {
    const next = keyTimes[i + 1];
    // keyingi bosish wait ichida kelmasa — chaqiruv bo'ladi
    if (next === undefined || next - keyTimes[i] >= wait) {
      calls.push(keyTimes[i] + wait);
    }
  }
  return calls;
}

// "lag'mon" — 7 ta bosish, har 120 ms da (ms hisobida)
const typing = [0, 120, 240, 360, 480, 600, 720];
console.log(debounceCalls(typing, 300)); // [ 1020 ]
console.log(debounceCalls(typing, 100).length); // 7

300 ms debounce bilan 7 ta qidiruv o'rniga bitta — oxirgi tugmadan 300 ms keyin. Foydalanuvchi natijani 1 020-millisekundda ko'radi. Debounce'siz esa har tugmada ~50 ms chizish bor, natija esa darhol paydo bo'ladi.

Qaror shunga bog'liq:

• Har chaqiruv tarmoqqa boradi (server qidiruvi, avtoto'ldirish API). Bunda debounce kerak: 7 ta so'rov o'rniga 1 ta — server yuki va pul tejaladi, eski javoblar yangisini bosib ketmaydi.
• Chaqiruv qimmat, lekin oraliq natijalar keraksiz (katta hisob, 200 ms chizish). Bunda ham debounce kerak.
• Chaqiruv arzon va natija darhol kerak — vazifalar dagi kabi bir necha yuz qator. Debounce faqat kechiktiradi. Yaxshiroq yo'l — chizishni arzonlashtirish, buni keyingi bo'limlarda ko'ramiz.

Tekshirib ko'ring: Mijoz har 400 ms da bitta harf yozadi, debounce — 300 ms. 7 ta harf uchun nechta chaqiruv bo'ladi?

4. Kesh: LRU

Menyu sahifasi serverdan keladi va har ochilishda qayta so'ralmasligi kerak. Lekin hamma sahifani xotirada saqlab bo'lmaydi. Chegara kerak: to'lib qolsa, eng uzoq ishlatilmagan yozuv chiqariladi. Bu LRU kesh. JavaScript'da u Map ning qo'shilish tartibiga tayanadi: get da yozuv o'chirilib, oxiriga qayta qo'shiladi. To'lsa, map.keys().next() — eng eskisi — o'chiriladi. Ikkala amal ham O(1).

Real ishda LRU hamma joyda uchraydi: Redis serverida xotira to'lganda kalitlarni chiqarish siyosati (allkeys-lru — taxminiy LRU), ma'lumotlar bazasining xotiradagi sahifalari, frontend so'rov kutubxonalarining keshi. Ularning hammasida savol bitta: qaysi yozuvni qurbon qilish? LRU javobi: uzoq vaqt kerak bo'lmaganini — yaqinda kerak bo'lgani yana kerak bo'lishi ehtimoli yuqori.

Kesh qo'shishdan oldin ham o'lchang. Kesh xotira oladi va eskirib qolishi mumkin. Kesh invalidatsiyasi — dasturlashdagi eng nozik masalalardan biri.

5. Noaniq qidiruv

Mijoz lagmon deb yozdi, menyuda lag'mon bor. Aniq qidiruv hech narsa topmaydi. vazifalar qidiruvi apostrof turlarini birlashtiradi, lekin apostrof umuman yo'q bo'lsa, u ham topmaydi. Yechim — 2D DP darsidagi tahrir masofasi: masofasi 1–2 bo'lgan nomlarni taklif qilish.

function editDistance(a, b) {
  let prev = Array.from({ length: b.length + 1 }, (_, j) => j);
  for (let i = 1; i <= a.length; i++) {
    const cur = [i];
    for (let j = 1; j <= b.length; j++) {
      cur[j] = a[i - 1] === b[j - 1]
        ? prev[j - 1]
        : 1 + Math.min(prev[j], cur[j - 1], prev[j - 1]);
    }
    prev = cur;
  }
  return prev[b.length];
}

function suggest(query, menu, maxEdits = 2) {
  return menu
    .filter((name) => // uzunligi juda farqli — darhol tashlaymiz
      Math.abs(name.length - query.length) <= maxEdits)
    .map((name) => ({ name, d: editDistance(query, name) }))
    .filter((x) => x.d <= maxEdits)
    .toSorted((x, y) => x.d - y.d)
    .map((x) => x.name);
}

const menu = ["osh", "lag'mon", "manti", "chuchvara",
  "somsa", "norin"];
console.log(suggest("lagmon", menu)); // [ "lag'mon" ]
console.log(suggest("mantu", menu)); // [ 'manti' ]
console.log(suggest("palov", menu)); // []

Ikkita amaliy hiyla bor. Birinchisi — arzon filtr oldinda: uzunligi 2 dan ko'p farq qiladigan so'z masofasi ham 2 dan katta. Bunday so'zlar qimmat O(L²) hisobga yetib kelmaydi. Ikkinchisi — xotira uchun ikki qatorli DP.

Murakkablik: N ta nom, uzunligi L — O(N · L²). Menyuda 50 ta taom bo'lsa, bu mikrosekundlar. Million mahsulotli do'konda esa har harfda million marta DP — qimmat. U yerda maxsus tuzilmalar (BK-daraxt, n-gram indekslar) yoki qidiruv serverlari ishlatiladi. Ular ham "avval nomzodlarni arzon qisqartir, keyin aniq hisobla" g'oyasida ishlaydi.

Uchinchi misolga qarang: palov hech narsa topmadi, garchi menyuda osh bo'lsa ham. Noaniq qidiruv harflarni taqqoslaydi, ma'noni bilmaydi. Sinonimlar uchun alohida lug'at kerak.

6. Kalitli diff: faqat o'zgargan qatorga tegish

6.1 Muammo

vazifalar ning render() har o'zgarishda butun ro'yxatni qayta quradi. 1 000 vazifada bu ~50 ms. Bitta vazifani belgilasangiz ham, 1 000 qator qaytadan yasaladi. Yaxshiroq yo'l — diff: eski va yangi ro'yxatni solishtirib, faqat farqni ekranga qo'llash.

Matn uchun LCS — O(n · m). Ro'yxatda esa yaxshiroq imkoniyat bor: har vazifaning noyob kaliti (id) bor. Kalit bo'lsa, "bu qator qaysi?" degan savolga Map O(1) da javob beradi. Diff O(n) ga tushadi.

6.2 Qoida

Yangi ro'yxatni chapdan o'ngga yuramiz va har id'ning eski indeksiga qaraymiz. lastIndex — joyida qoldirilgan qatorlarning eng katta eski indeksi. Eski indeks undan kichik bo'lsa — tartib buzilgan, qatorni ko'chiramiz. Aks holda tegmaymiz:

Bu React'ning ro'yxatlarni yangilash (reconciliation) usulidagi g'oya. React — 17-qismda o'rganadigan interfeys kutubxonasi, hozir bilish shart emas. Uning ham ro'yxat elementlaridan key talab qilishining sababi shu: kalitsiz diff qaysi qator qaysi ekanini bilmaydi va hammasini qayta chizadi.

Bu qoida eng kam ko'chirishni har doim ham bermaydi. Oxirgi qatorni boshiga olsangiz, qolgan hammasi "ko'chirildi" bo'lib chiqadi. Eng kam ko'chirishni eng uzun o'suvchi qism ketma-ketlik (1D DP masalalari darsidagi LIS, LCS ning qarindoshi) beradi: eski indekslar ketma-ketligidagi LIS joyida qoladi, qolganlari ko'chiriladi. Vue 3 kutubxonasi aynan shunday qiladi — uning diff kodida LIS binary search bilan, O(n log n) da topiladi. Amalda ikkala usul ham butun ro'yxatni qayta chizishdan ancha arzon.

6.3 O'lchov

Kalit bo'yicha qidirishni Map o'rniga indexOf va includes bilan qilsak, diff O(n²) bo'ladi. Ikkalasini benchmarking darsidagi usulda o'lchadik (har n alohida jarayonda, isitish, mediana; raqamlar taxminiy). 1 % qator o'chirilgan, 1 % qo'shilgan, 1 % joy almashgan:

indexOf varianti kvadratik o'sdi va 8 000 qatorda o'zi bir kadrdan (16 ms) to'rt baravar ko'p vaqt oldi. Map varianti million qatorda ham ≈ 0,35 soniya oldi. Kichik o'lchamlarda Map ustunidagi nisbat shovqinli: vaqtlar millisekunddan kam.

7. Pagination: offset yoki kursor

Ro'yxat katta bo'lsa, u bo'laklab yuklanadi: 20 ta, keyin yana 20 ta. Buning ikki usuli bor. Offset: "21-dan boshlab 20 ta". Kursor: "id'si 8 dan kichiklardan 20 ta" — oxirgi ko'rilgan elementdan keyin.

Farq ro'yxat o'zgarganda ko'rinadi. Yangi vazifalar tepada, sahifa — 3 ta:

// Yangilari tepada: id kamayish tartibida
let feed = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1];

const pageByOffset = (list, offset, limit) =>
  list.slice(offset, offset + limit);

function pageByCursor(list, beforeId, limit) {
  let lo = 0; // birinchi "id < beforeId" joyni ikkiga bo'lib topamiz
  let hi = list.length;
  while (lo < hi) {
    const mid = (lo + hi) >> 1;
    if (list[mid] >= beforeId) lo = mid + 1;
    else hi = mid;
  }
  return list.slice(lo, lo + limit);
}

const page1 = pageByOffset(feed, 0, 3);
console.log("1-sahifa:", page1);
feed = [11, ...feed]; // shu orada yangi vazifa qo'shildi
console.log("offset bilan 2-sahifa:", pageByOffset(feed, 3, 3));
const cursor = page1.at(-1); // oxirgi ko'rilgan id
console.log("kursor bilan 2-sahifa:", pageByCursor(feed, cursor, 3));

Konsolda:

1-sahifa: [ 10, 9, 8 ]
offset bilan 2-sahifa: [ 8, 7, 6 ]
kursor bilan 2-sahifa: [ 7, 6, 5 ]

Birinchi sahifadan keyin yangi vazifa (11) qo'shildi va hamma narsa bitta pastga surildi. Offset bilan 2-sahifada 8 takrorlandi. O'chirilsa, teskarisi bo'ladi: bitta element ko'rinmay qoladi. Kursor esa joyga emas, qiymatga tayanadi: "8 dan keyingilar". Shuning uchun qo'shish va o'chirish unga ta'sir qilmaydi.

Tezlik farqi ham bor. Kursorli sahifa saralangan ro'yxatda binary search bilan topiladi: O(log n + limit). Ma'lumotlar bazasida ham shunday — indeks bo'yicha sakrash. Offset esa birinchi offset ta qatorni sanab o'tishi kerak: 10 000-sahifa 10 000 × 20 qatorni o'tkazib yuboradi. Ma'lumotlar bazasi va SQL — backend qismida. Bugungi g'oya u yerda WHERE id < $1 ORDER BY id DESC LIMIT 20 ko'rinishida qaytadi.

8. Rate limiting: token bucket

8.1 Masala

Server cheksiz so'rovga dosh berolmaydi. Bitta foydalanuvchi (yoki skript) sekundiga yuzlab so'rov yuborsa, boshqalarga navbat yetmaydi. Shuning uchun so'rovlar cheklanadi: masalan, kursdagi «Bahor» mashq API daqiqasiga 120 tagacha so'rov qabul qiladi. Ortig'iga server 429 Too Many Requests javobini beradi.

"Daqiqasiga 120" ni qanday hisoblash mumkin? Eng sodda yo'l — har daqiqa boshida hisoblagichni nolga qaytarish. Lekin unda 0:59 da 120 ta va 1:00 da yana 120 ta — ikki soniyada 240 ta so'rov o'tib ketadi. Har so'rov vaqtini saqlab, oxirgi 60 soniyani suriluvchi oyna bilan sanash aniq ishlaydi, lekin har foydalanuvchi uchun 120 ta vaqtni saqlaydi.

8.2 Token bucket

Token bucket (jetonli chelak) — sodda va arzon muqobil. Chelakda jetonlar bor, eng ko'pi capacity ta. Har so'rov bitta jeton oladi. Jeton bo'lmasa — rad. Chelak doimiy tezlikda to'ladi: soniyasiga perSecond ta. Har foydalanuvchi uchun faqat ikki son saqlanadi: jetonlar soni va oxirgi vaqt.

class TokenBucket {
  constructor(capacity, perSecond) {
    this.capacity = capacity; // eng ko'p jeton (birdaniga portlash)
    this.perSecond = perSecond; // soniyasiga qancha to'ladi
    this.tokens = capacity;
    this.last = 0; // oxirgi hisob vaqti, ms
  }

  tryTake(now) {
    const added = ((now - this.last) / 1000) * this.perSecond;
    this.tokens = Math.min(this.capacity, this.tokens + added);
    this.last = now;
    if (this.tokens < 1) return false; // 429 Too Many Requests
    this.tokens -= 1;
    return true;
  }
}

// Daqiqasiga 120 so'rov = soniyasiga 2, portlash — 10 tagacha
const bucket = new TokenBucket(10, 2);
const at = (ms, count) => Array.from({ length: count }, () =>
  bucket.tryTake(ms) ? "✓" : "✗").join("");
console.log("0 ms, 15 so'rov:   ", at(0, 15));
console.log("1000 ms, 5 so'rov: ", at(1000, 5));
console.log("6000 ms, 12 so'rov:", at(6000, 12));

Konsolda:

0 ms, 15 so'rov:    ✓✓✓✓✓✓✓✓✓✓✗✗✗✗✗
1000 ms, 5 so'rov:  ✓✓✗✗✗
6000 ms, 12 so'rov: ✓✓✓✓✓✓✓✓✓✓✗✗

Birinchi qatorda 15 ta so'rov birdaniga keldi: 10 tasi o'tdi (chelak to'la edi), 5 tasi rad etildi. Bu portlash (burst): qisqa vaqtda capacity ta so'rovga ruxsat. Bir soniyadan keyin chelakka 2 ta jeton tushdi — 2 ta so'rov o'tdi. 5 soniya kutilgach, chelak yana to'ldi — 10 ta o'tdi, 11-chisi emas.

tryTake(now) vaqtni parametr sifatida oladi. Date.now() ni ichida chaqirmaydi. Shu tufayli testda vaqtni o'zimiz boshqaramiz va natija har safar bir xil. Bu — testlanadigan kodning muhim odati (Chegaraviy holatlar va algoritmni testlash).

Murakkablik: har so'rov O(1) vaqt, har foydalanuvchiga O(1) xotira. Shuning uchun token bucket ko'p joyda ishlatiladi: API shlyuzlari, Nginx so'rov cheklovi (u yaqin algoritm — leaky bucket asosida ishlaydi), bulut provayderlarining API'lari.

Hujumchi nigohi

Rate limiting — xavfsizlik vositasi ham. Hujumchi login formasiga sekundiga minglab parol yuborib ko'radi (brute force) yoki saytning hamma sahifasini skript bilan ko'chiradi. Token bucket buni sekinlashtiradi: chelak har foydalanuvchi yoki IP uchun alohida bo'ladi. Login uchun capacity kichik bo'ladi, masalan, 5.

Ikkinchi xavf — qimmat so'rov. Noaniq qidiruv O(N · L²): hujumchi 10 000 belgilik so'rov yuborsa, server har nomga ulkan DP jadvalini quradi. Himoya ikki qatlamli. Birinchisi — kirishni cheklash (so'rov uzunligi, masalan, ≤ 50 belgi). Ikkinchisi — qimmat amallarga alohida, qattiqroq cheklov. Bu ReDoS darsidagi g'oya: algoritm murakkabligi ham hujum yuzasi.

Chelak serverda bo'lishi shart. Brauzerdagi cheklov foydalanuvchi tajribasi uchun yaxshi, lekin hujumchi uni chetlab o'tadi — u brauzerdan emas, skriptdan so'rov yuboradi.

9. Ko'p uchraydigan xatolar

9.1 O'lchamasdan optimallashtirish

Qidiruvni Trie'ga o'tkazish, vaholanki vaqtni chizish yeydi. Tuzatish: avval o'lchov, keyin eng qimmat qism.

9.2 Indeksni kalit qilish

Diffda kalit sifatida massiv indeksini ishlatish: o'rtadan bitta qator o'chsa, undan keyingi hamma qatorning "kaliti" o'zgaradi va hammasi qayta chiziladi. Ba'zan esa noto'g'ri qatorga holat yopishadi. Tuzatish: barqaror, noyob id.

9.3 Offset bilan cheksiz lenta

Yangilari tepada bo'lgan lentada offset — takrorlanish va yo'qolishlar. Tuzatish: kursor (oxirgi ko'rilgan id yoki vaqt).

9.4 Rate limit'ni faqat frontendda qilish

Tuzatish: cheklov serverda, frontendda esa faqat foydalanuvchiga tushunarli xabar ("bir oz kuting").

10. Mashqlar

1-mashq (oson): Chelakni hisoblang

Token bucket: capacity 10, soniyasiga 2 jeton. Chelak bo'sh. 3 soniyadan keyin birdaniga 20 ta so'rov keldi. Nechtasi o'tadi? Javob: [:6]. Keyin 100 soniya kutildi va yana 20 ta so'rov keldi. Nechtasi o'tadi? Javob: [:10].

2-mashq (o'rta): Debounce va diff bilan hisob

Mijoz manti ni yozdi: tugmalar 0, 150, 300, 700 va 850-millisekundda. Debounce — 300 ms. debounceCalls nechta chaqiruv qaytaradi va qachon? Keyin diffById([1, 2, 3], [3, 1, 2]) uchun amallarni qo'lda toping.

3-mashq (qiyin): Token bucket'ni testlang

kurs/mashqlar/14/60-real-ish/cheklov.test.mjs faylida TokenBucket ni testlang:

1. Portlash: bir vaqtda 50 ta so'rovdan faqat capacity tasi o'tadi.
2. To'lish: bo'shatilgan chelakda 1 soniyadan keyin aynan 2 ta o'tadi. Bir soat kutilsa ham — capacity tadan ko'p emas.
3. Xususiyat: urug'li generator bilan 5 000 ta tasodifiy so'rov. Qabul qilinganlarning istalgan 60 soniyalik oynasida 10 + 120 dan ko'p so'rov yo'q. Ishora: tekshiruvning o'zi — suriluvchi oyna.

// kurs/mashqlar/14/60-real-ish/cheklov.test.mjs
import { test } from "node:test";
import assert from "node:assert/strict";

class TokenBucket {
  constructor(capacity, perSecond) {
    this.capacity = capacity;
    this.perSecond = perSecond;
    this.tokens = capacity;
    this.last = 0;
  }

  tryTake(now) {
    const added = ((now - this.last) / 1000) * this.perSecond;
    this.tokens = Math.min(this.capacity, this.tokens + added);
    this.last = now;
    if (this.tokens < 1) return false;
    this.tokens -= 1;
    return true;
  }
}

function makeRandom(seed) {
  return () => (seed = (seed * 16807) % 2147483647);
}

test("portlash: birdaniga faqat capacity ta", () => {
  const bucket = new TokenBucket(10, 2);
  let ok = 0;
  for (let k = 0; k < 50; k++) if (bucket.tryTake(0)) ok++;
  assert.equal(ok, 10);
});

test("to'lish: soniyasiga 2 ta, capacity'dan oshmaydi", () => {
  const bucket = new TokenBucket(10, 2);
  for (let k = 0; k < 10; k++) bucket.tryTake(0); // bo'shatamiz
  assert.equal(bucket.tryTake(1000), true);
  assert.equal(bucket.tryTake(1000), true);
  assert.equal(bucket.tryTake(1000), false);
  let ok = 0;
  for (let k = 0; k < 20; k++) if (bucket.tryTake(3_600_000)) ok++;
  assert.equal(ok, 10); // bir soat kutsa ham — 10 ta
});

test("xususiyat: istalgan 60 soniyada ≤ 10 + 120 so'rov", () => {
  const random = makeRandom(62);
  const bucket = new TokenBucket(10, 2);
  const accepted = [];
  let now = 0;
  for (let k = 0; k < 5000; k++) {
    now += random() % 400; // tasodifiy oraliq, 0–399 ms
    if (bucket.tryTake(now)) accepted.push(now);
  }
  let left = 0;
  for (let right = 0; right < accepted.length; right++) {
    while (accepted[right] - accepted[left] >= 60_000) left++;
    assert.ok(right - left + 1 <= 130, `oynada ${right - left + 1}`);
  }
});

✔ portlash: birdaniga faqat capacity ta (0.763ms)
✔ to'lish: soniyasiga 2 ta, capacity'dan oshmaydi (0.1463ms)
✔ xususiyat: istalgan 60 soniyada ≤ 10 + 120 so'rov (2.4772ms)
ℹ tests 3
ℹ suites 0
ℹ pass 3
ℹ fail 0
ℹ cancelled 0
ℹ skipped 0
ℹ todo 0
ℹ duration_ms 8.7924

4-mashq: Amaliy tajriba — vazifalar o'lchovini o'qing

vazifalar README faylidagi "Murakkablik" bo'limini oching (14-qismda qo'shilgan jadval). Kodga tegmang, faqat o'qing va kurs/mashqlar/14/60-real-ish/README.md ga uch savolga javob yozing:

1. 1 000 vazifada foydalanuvchi qidiruvda kutadigan vaqtning qanchasi algoritm, qanchasi chizish?
2. Qaysi o'zgarish foydalanuvchi uchun ko'proq foyda beradi: qidiruvni ikki baravar tezlashtirishmi yoki faqat o'zgargan qatorlarni chizishmi? Nega?
3. Trie teg takliflari nega vazifalar soniga bog'liq emas?

Oxirida MURAKKABLIK.md ga bugungi qatorlarni qo'shing.

| Masala | Yechim | Vaqt | Xotira |
|---|---|---|---|
| LRU kesh | Map tartibi | O(1) get/put | O(capacity) |
| Noaniq qidiruv | filtr + tahrir masofasi | O(N · L²) | O(L) |
| Ro'yxat diff | kalit + Map | O(n) | O(n) |
| Ro'yxat diff | indexOf | O(n²) | O(1) |
| Pagination | kursor + binary search | O(log n + limit) | O(1) |
| Rate limit | token bucket | O(1) | O(1) har foydalanuvchiga |

git add 14/MURAKKABLIK.md 14/60-real-ish
git commit -m "14/60: real ishda — token bucket testi, vazifalar o'lchovi"

11. Real ishda

• Frontend. Virtual ro'yxatlar (faqat ekranda ko'rinadigan qatorlarni chizish), kalitli diff, so'rov keshi va debounce'li qidiruv — katta ro'yxatli har ilovada. React, Vue va Svelte bularni ichida qiladi — 17-qismdan boshlab ko'rasiz.
• Backend. Kursorli pagination, Redis'dagi kesh va rate limiting — har API'da. Ish navbatlari (BullMQ, RabbitMQ, Kafka) navbat va priority queue g'oyasida ishlaydi: og'ir ishlar kelish yoki muhimlik tartibida bajariladi. Ular backend qismida, Node.js server bilan qaytadi.
• Kod ko'rib chiqish. "Bu sikl ichidagi find 10 000 elementda qancha turadi?", "pagination offset bilanmi?", "rate limit bormi?" — 14-qism bilimi shunday savollar ko'rinishida ishlaydi.

14-qism yakuni

Tabriklaymiz — 14-qismni tugatdingiz! Bu qism eng uzunlaridan biri edi: 60 ta dars, ma'lumot tuzilmalari va algoritmlarning deyarli hamma asosiy naqshlari. Bosib o'tgan yo'l:

flowchart TD
  A["1–6: Big-O<br/>sinflar, xotira, narx"] --> B["7–15: Massiv naqshlari<br/>ko'rsatkich, oyna, prefiks"]
  B --> C["16–22: Ro'yxat, stek,<br/>navbat, hash"]
  C --> D["23–26: Rekursiya,<br/>backtracking"]
  D --> E["27–35: Saralash<br/>va binary search"]
  E --> F["36–44: Daraxt, Trie,<br/>heap"]
  F --> G["45–49: Graflar"]
  G --> H["50–55: DP, greedy,<br/>intervallar"]
  H --> I["56–60: Jarayon<br/>va amaliyot"]
  B -. "qidiruv" .-> V["vazifalar v4.1"]
  E -. "saralash" .-> V
  F -. "Trie" .-> V

Diagrammaga qarang: chapda — mavzular zanjiri, har biri oldingisiga tayanadi. Punktir chiziqlar — vazifalar qaysi bloklarda o'sgani. Endi har blok haqida bir gap:

1. Big-O (1–6). Algoritm narxini n o'sganda baholash: dominant had, yettita sinf, sikllar va rekursiya daraxti, xotira va amortizatsiya, o'rnatilgan amallarning narxi.
2. Massiv naqshlari (7–15). Ikki ko'rsatkich, suriluvchi oyna, prefiks yig'indi, hash map bilan sanash, matn va matritsa, Kadane va Boyer–Moore, bitlar va sonlar nazariyasi.
3. Chiziqli tuzilmalar (16–22). Linked list, stek, navbat, monoton stek, hash jadval ichidan va LRU kesh.
4. Rekursiya (23–26). Rekursiv fikrlash, backtracking va kesish, bo'lib-yech.
5. Saralash va qidiruv (27–35). Saralash turlari, merge va quick sort, JavaScript sort ichidan, binary search variantlari, javob ustida qidiruv, quickselect.
6. Daraxtlar (36–44). Binar daraxt, DFS va BFS, BST va balanslash, Trie, heap va priority queue, segment tree.
7. Graflar (45–49). Graf ko'rinishlari, BFS/DFS, eng qisqa yo'l, topologik saralash, Union-Find.
8. Optimallash (50–55). Dinamik dasturlash (memoization, tabulation, 1D va 2D), greedy va intervallar.
9. Jarayon va amaliyot (56–60). UMPIRE, naqshni tanish, testlash va stress test, muntazam mashq, real ish.

O'zingizni tekshiring — quyidagilarni qila olasizmi?

• Kodga qarab uning vaqt va xotira murakkabligini aytib, o'z kichik o'lchov skriptim bilan n×2 o'lchovida tasdiqlay olaman.
• "Saralangan", "ketma-ket bo'lak", "hamma variantlar", "eng kam usul" so'zlaridan kerakli texnikani taniy olaman.
• Hash map, ikki ko'rsatkich, oyna va prefiks yig'indi bilan O(n²) yechimni O(n) ga tushira olaman.
• Stek, navbat, heap, Trie va grafni kerak joyda tanlab, o'zim yoza olaman.
• Rekursiv yechimni memoization yoki jadval bilan DP ga aylantira olaman va greedy'ni qarshi misol bilan tekshira olaman.
• Notanish masalani UMPIRE bilan yechib, tez yechimni brute force va stress test bilan himoyalay olaman.
• Haqiqiy ilovada avval o'lchab, vaqt algoritmga ketyaptimi yoki chizish/tarmoqqami — ajrata olaman.

vazifalar ham shu qism bilan birga o'sdi. 13-qism oxirida u tez va xavfsiz edi. Endi v4.1 da qidiruv bor: apostrof turlari birlashtiriladi, moslar belgilanadi. Ro'yxat bir nechta kalit bo'yicha barqaror saralanadi va tanlangan saralash manzilda saqlanadi. Teg yozilayotganda Trie takliflar beradi. README'da esa har amalning o'lchangan murakkablik jadvali bor.

Raqamlarda: 137 ta avtomatik test (13-qism oxirida 90 ta edi), brauzerda 159 ta tekshiruv, Lighthouse (mobil) — 98 / 100 / 100 / 100. Qism boshidagi maqsad — "algoritm yechimlari va murakkablik jadvali, vazifalar da qidiruv va saralash" — bajarildi.

Qaysidir band qiyin tuyulsa — o'sha darsga qayting va muntazam mashq rejasiga qo'shing. Algoritmlar bir o'qishda emas, takrorlashda mustahkamlanadi. 15-qismda kodga yangi himoya qatlami qo'shamiz: xatolarni ishga tushirishdan oldin, yozish paytidayoq topadigan tiplar — TypeScript.

Xulosa

• Real ishda algoritm kesh, qidiruv, diff, pagination va cheklov ko'rinishida keladi. Lekin birinchi qadam — o'lchov: vazifalar da qidiruv 2,2 ms, chizish ~50 ms.
• Debounce chaqiruvlar sonini kamaytiradi, narxini emas — tarmoq so'rovlari uchun kerak, arzon lokal qidiruv uchun shart emas.
• LRU — Map tartibi; noaniq qidiruv — arzon filtr + tahrir masofasi; kalitli diff — Map bilan O(n), indexOf bilan O(n²).
• Kursorli pagination qiymatga tayanadi va binary search bilan topiladi; offset lentada takror va yo'qolish beradi.
• Token bucket: har so'rov O(1), portlash capacity bilan cheklangan; cheklov serverda bo'lishi shart.

Keyingi dars: Nega TypeScript — 15-qism boshlanadi: JavaScript'ga tiplar qo'shib, xatolarni kod ishga tushmasdan topish.

Manbalar

• React hujjatlari: "Preserving and Resetting State", "Rendering Lists" (kalitlar) — react.dev
• Redis hujjatlari: "Key eviction" (allkeys-lru, taxminiy LRU) — redis.io/docs
• MDN: "429 Too Many Requests" — developer.mozilla.org
• Nginx hujjatlari: ngx_http_limit_req_module (leaky bucket) — nginx.org