69-dars

Memoization

Memoization — funksiya natijasini **kesh (cache)**da saqlab qo'yish, va agar o'sha funksiya xuddi shu argumentlar bilan qayta chaqirilsa — qaytadan hisoblamasdan, saqlangan natijani darhol qaytarish texnikasi.

function memoize(fn) {
  const kesh = new Map();

  return function (...args) {
    const kalit = JSON.stringify(args); // argumentlarni bitta "kalit"ga aylantiramiz

    if (kesh.has(kalit)) {
      return kesh.get(kalit); // KESHDAN qaytaramiz — hisoblanmaydi
    }

    const natija = fn.apply(this, args);
    kesh.set(kalit, natija);
    return natija;
  };
}

function ogirHisob(n) {
  console.log("Hisoblanyapti:", n);
  let natija = 0;
  for (let i = 0; i < 1000000000; i++) natija += i % n;
  return natija;
}

const memoized = memoize(ogirHisob);

memoized(5); // "Hisoblanyapti: 5" — chinakam hisoblanadi (sekin)
memoized(5); // hech narsa chop etilmaydi — KESHDAN darhol qaytadi (tez)

---

1. Nega bu kerak?

Ba'zi funksiyalar hisoblash jihatidan qimmat (og'ir tsikl, rekursiya, murakkab matematik amal), lekin ular pure function (sof funksiya) bo'lsa — ya'ni bir xil argument har doim bir xil natija beradi va tashqi holatga ta'sir qilmaydi — bunday funksiyani bir marta hisoblab, keyin faqat eslab qolish mantiqan to'g'ri, chunki qayta hisoblash — behuda ish takrorlash.

Muhim shart: memoization faqat pure (sof) funksiyalar uchun to'g'ri ishlaydi:

// PURE — memoization uchun mos
function kvadrat(x) {
  return x * x; // faqat x'ga bog'liq, tashqi holatga ta'sir qilmaydi
}

// PURE EMAS — memoization xato natija berishi mumkin
function tasodifiyQoshish(x) {
  return x + Math.random(); // har chaqiruvda BOSHQA natija
}

// PURE EMAS — tashqi holatga bog'liq
let chegirma = 0.1;
function narxHisobla(narx) {
  return narx * (1 - chegirma); // agar `chegirma` o'zgarsa, eski kesh XATO bo'ladi
}

Agar funksiya tashqi o'zgaruvchan holatga (global o'zgaruvchi, tarmoq, DOM) bog'liq bo'lsa yoki side effect (yon ta'sir) qilsa — memoize qilinganda, kesh eskirgan (stale) natijalarni qaytarishi mumkin, bu xatoga olib keladi.

---

2. Klassik misol — Fibonacci (rekursiv hisoblash portlashi muammosi)

Memoization foydasini eng yaqqol ko'rsatadigan misol:

function fib(n) {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2);
}

fib(35); // JUDA sekin — chunki fib(30) o'nlab marta QAYTA hisoblanadi

fib(35) chaqirilganda, rekursiya daraxti ichida fib(30) minglab marta, fib(20) esa millionlab marta qayta hisoblanadi — bir xil natija, har safar boshidan. Bu — eksponensial vaqt murakkabligi (O(2^n)).

function fibMemo(n, kesh = new Map()) {
  if (n <= 1) return n;
  if (kesh.has(n)) return kesh.get(n); // avval hisoblanganmi — tekshiramiz

  const natija = fibMemo(n - 1, kesh) + fibMemo(n - 2, kesh);
  kesh.set(n, natija);
  return natija;
}

fibMemo(35); // DEYARLI DARHOL — chunki har bir n faqat BIR MARTA hisoblanadi

Memoization bilan murakkablik O(2^n)dan O(n)ga tushadi — bu dasturlashda eng yorqin performance yutuqlaridan biri, va "dynamic programming" deb ataladigan yondashuvning asosi aynan shu.

---

3. Kalitni aniqlash muammosi (JSON.stringify cheklovi)

Yuqoridagi oddiy implementatsiyada JSON.stringify(args) ishlatildi, lekin bu har doim ishonchli emas:

memoize(fn)(1, 2);         // kalit: "[1,2]"
memoize(fn)({ a: 1 });     // kalit: '[{"a":1}]' — ishlaydi
memoize(fn)(undefined);    // kalit: "[null]" — undefined YO'QOLADI!
memoize(fn)(() => {});     // kalit: "[null]" — funksiyalar JSON'ga aylanmaydi!

Ko'proq ishonchli yondashuv — bitta argument uchun, obyekt/funksiya kalitlar uchun WeakMap:

function memoizeBir(fn) {
  const kesh = new WeakMap(); // faqat OBYEKT kalitlar uchun ishlaydi

  return function (obj) {
    if (kesh.has(obj)) return kesh.get(obj);

    const natija = fn(obj);
    kesh.set(obj, natija);
    return natija;
  };
}

WeakMap ishlatilishi — bevosita Memory leak mavzusida ko'rgan mexanizm bilan bog'liq: agar kalit sifatida ishlatilgan obyekt boshqa hech qayerda ishlatilmasa, GC uni avtomatik tozalaydi, va kesh yozuvi ham shu bilan birga yo'qoladi. Oddiy Map ishlatilganda esa, kesh abadiy o'sha obyektni ushlab turgan bo'lardi — bu memoization'ning o'zi memory leak manbaiga aylanib qolishi mumkinligini ko'rsatadi.

---

4. V8 darajasida — memoization va JIT/hidden class bilan bog'liqlik

1. Monomorphic chaqiruv ustunligi

Oldingi mavzularda ko'rganimizdek, V8 (TurboFan) funksiyani bir xil turdagi argumentlar bilan qayta-qayta chaqirilganda optimallashtiradi. Memoize qilingan funksiya — kesh tekshiruvi + shartli branch qo'shadi:

function memoized(...args) {
  const kalit = /* ... */;
  if (kesh.has(kalit)) return kesh.get(kalit); // qo'shimcha branch
  // ...
}

Bu qo'shimcha Map.has()/Map.get() chaqiruvi — o'zi ham CPU vaqti sarflaydi. Shuning uchun memoization faqat asl hisoblash keshlashdan qimmatroq bo'lgandagina foyda beradi:

// YOMON foydalanish — memoize qilish o'zi hisoblashdan qimmatroq
const memoizedQoshish = memoize((a, b) => a + b);
// Map orqali kalit yaratish, tekshirish — oddiy qo'shishdan SEKINROQ!

// YAXSHI foydalanish — asl hisob juda og'ir
const memoizedFib = memoize(ogirRekursivHisob);

2. Kesh o'zi — Old Generation'ga o'tib qoladigan obyekt

Map/obyekt sifatidagi kesh — vaqt o'tishi bilan kattalashib boradi (har yangi argument kombinatsiyasi uchun yangi yozuv). Bu kesh uzoq umr ko'radi (odatda modul darajasida, komponent umri davomida saqlanadi), shuning uchun V8 GC uni tezda Young Generation'dan Old Generation'ga ko'chiradi (Garbage Collection mavzusida ko'rgan "promotion" jarayoni). Agar kesh cheklanmagan holda o'sishda davom etsa — bu, aslida, nazoratsiz memoization = memory leak degani (chunki kesh — root'ga bog'liq, GC uni tozalay olmaydi).

Yechim — kesh hajmini cheklash (LRU — Least Recently Used strategiyasi):

function memoizeLRU(fn, maksHajm = 100) {
  const kesh = new Map();

  return function (...args) {
    const kalit = JSON.stringify(args);

    if (kesh.has(kalit)) {
      const qiymat = kesh.get(kalit);
      kesh.delete(kalit);
      kesh.set(kalit, qiymat); // eng oxiriga qayta qo'yamiz ("yangi ishlatilgan")
      return qiymat;
    }

    const natija = fn.apply(this, args);

    if (kesh.size >= maksHajm) {
      const engEski = kesh.keys().next().value; // Map — kiritilish tartibini saqlaydi
      kesh.delete(engEski); // eng kam ishlatilganini chiqarib tashlaymiz
    }

    kesh.set(kalit, natija);
    return natija;
  };
}

Bu yerda Mapning muhim xususiyatidan foydalanilyapti: JavaScript'da Map — kiritilish tartibini saqlaydi (oddiy obyektdan farqli, obyektda tartib kafolatlanmaydi), shuning uchun kesh.keys().next().value — har doim eng birinchi (eng eski) qo'shilgan kalitni beradi.

---

Amaliy xulosa

Holat	Memoization foydali
Rekursiv hisoblashlar (Fibonacci, dynamic programming)	✅ Ha, katta yutuq
React'da useMemo/useCallback — qimmat hisob-kitob	✅ Ha, qayta render'larda tejaydi
API javoblarini keshlash (bir xil so'rov)	✅ Ha, tarmoq so'rovini kamaytiradi
Sodda arifmetik amal (a + b)	❌ Yo'q, kesh tekshiruvi hisoblashdan qimmatroq
Tasodifiy natija beruvchi funksiya	❌ Mutlaqo yo'q — noto'g'ri natija beradi
Argumentlar deyarli hech qachon takrorlanmaydigan funksiya	❌ Yo'q — kesh faqat xotira band qiladi, foyda bermaydi