JavaScript memoization: natijani keshlash, Map, WeakMap va LRU

Qisqacha: Memoizatsiya — toza funksiyaning har argumenti uchun javobni bir marta hisoblab, keyingi safar keshdan berish. Kesh odatda Map (primitiv kalit) yoki WeakMap (obyekt kalit). U faqat toza va og'ir funksiyada foyda beradi: fib(35) taxminan 150 ms dan 0,01 ms dan ham kamga tushadi, x * 2 kabi arzon funksiya esa keshdan sekinlashadi. Kesh cheksiz o'smasligi uchun hajmi cheklanadi — eng ko'p ishlatiladigan usul LRU.

Bu darsda

• Map bilan universal memoize yozasiz va 10-qismdagi oddiy keshlangan ning uch kamchiligini tuzatasiz.
• Bir nechta argument uchun kesh kalitini to'g'ri yasaysiz va join/JSON.stringify tuzoqlarini bilasiz.
• Rekursiv funksiyani (Fibonacci) to'g'ri memoizatsiya qilasiz va nega "tashqaridan o'rash" ishlamasligini tushuntira olasiz.
• Obyekt argumentli funksiyani WeakMap bilan keshlaysiz va u nega immutable ma'lumot talab qilishini bilasiz.
• Kesh hajmini LRU bilan cheklaysiz va memoizatsiya qachon yutishini o'lchab ko'rsata olasiz.

Oldin bilishingiz kerak: Closure amaliyotda, Map, WeakMap, WeakSet, WeakRef, Immutability chuqur, Currying va partial application.

1. Nega bu kerak?

Bu dars uchun kursda to'rtta va'da yig'ilgan. Birinchisi — Rekursiya asoslari darsida fib(40) qotib qolgan edi. Ikkinchisi — Pure funksiya darsida "bir marta hisoblangan javobni saqlab qo'yish mumkin" degan edik. Uchinchisi — Closure amaliyotda darsida oddiy keshlangan funksiyani yozdik va uning uch shartini sanadik. To'rtinchisi — WeakMap darsida obyektga bog'langan kesh yasadik va "bu kesh savat o'zgarmaydi deb hisoblaydi" deb ogohlantirdik.

Bugun shularning hammasini bir joyga yig'amiz. Avval Fibonacci sonlarini eslang: har son oldingi ikkitasining yig'indisi — 0, 1, 1, 2, 3, 5, 8, 13… Oddiy rekursiya fib(n) ni fib(n - 1) + fib(n - 2) deb hisoblaydi. Endi bitta raqamga qarang — u o'zini necha marta chaqiradi:

let chaqiruvlar = 0;
function fib(n) {
  chaqiruvlar++;
  return n < 2 ? n : fib(n - 1) + fib(n - 2);
}

console.log(fib(25)); // 75025
console.log(chaqiruvlar); // 242785

25-son uchun — chorak milliondan ko'p chaqiruv. 35-son uchun esa 29 860 703 ta. Sabab: fib(23) ham, fib(22) ham va boshqalar ham qayta-qayta, har safar noldan hisoblanadi. Javob esa har safar bir xil.

Hayotdan o'xshatish: o'qituvchi doskaga ko'paytirish jadvalini yozib qo'ydi. O'quvchi 7 × 8 ni har safar barmoqda sanamaydi — jadvalga qaraydi. Jadval bir marta tuziladi, keyin faqat o'qiladi. Memoizatsiya — funksiya uchun shunday jadval.

2. Universal memoize

2.1 Eslab olamiz

Memoizatsiya (memoization) — funksiyaning har argumenti uchun javobni bir marta hisoblab, keyin keshdan berish. Kesh (cache) — tayyor javoblar saqlanadigan joy. Bu ta'riflar Closure amaliyotda darsidan.

O'sha darsdagi keshlangan oddiy obyektni kesh qilgan edi. Unda uchta muammo bor edi: obyekt kalitlari doim satr (3 va "3" bitta kalit), argument faqat bitta, kesh esa cheksiz o'sadi. Birinchisini Map darhol hal qiladi — u kalit turini saqlaydi:

function memoize(funksiya) {
  const kesh = new Map();
  return (arg) => {
    if (!kesh.has(arg)) {
      kesh.set(arg, funksiya(arg));
    }
    return kesh.get(arg);
  };
}

let hisoblar = 0;
const kvadrat = memoize((x) => {
  hisoblar++;
  return x * x;
});

console.log(kvadrat(3), kvadrat(3), kvadrat("3")); // 9 9 9
console.log(hisoblar); // 2

kvadrat(3) ikkinchi marta keshdan keldi. kvadrat("3") esa alohida hisoblandi: Map uchun 3 va "3" — har xil kalit. Obyektli keshda ular bitta bo'lib qolardi.

2.2 Qaror qanday qabul qilinadi

Har chaqiruvda memoize qilingan funksiya bitta savol beradi: "bu kalit keshdami?" Diagrammada ikki yo'lni kuzating:

flowchart TD
  A["kvadrat(arg)"] --> B{"kesh.has(arg)?"}
  B -- "ha" --> C["kesh.get(arg)"]
  B -- "yo'q" --> D["funksiya(arg) — og'ir hisob"]
  D --> E["kesh.set(arg, natija)"]
  E --> C
  C --> F["natija"]

Chap yo'l — tez: faqat Map dan o'qish. O'ng yo'l — sekin, lekin har kalit uchun bir marta. Memoizatsiyaning butun foydasi shu: o'ng yo'l qanchalik og'ir va chap yo'l qanchalik ko'p bo'lsa, yutuq shunchalik katta.

2.3 Faqat toza funksiya

Kesh "bir xil argument — bir xil javob" degan ishonchga tayanadi. Shuning uchun memoizatsiya faqat toza funksiyaga qo'yiladi. Agar funksiya vaqtga, tasodifga, tashqi o'zgaruvchiga yoki serverdagi ma'lumotga bog'liq bo'lsa — kesh eski javobni berib "muzlab" qoladi. Xato xabari chiqmaydi, javob shunchaki noto'g'ri.

Yon ta'sirli funksiyani keshlash ham xato: ikkinchi chaqiruvda yon ta'sir bo'lmaydi. memoize(xabarYubor) ikkinchi marta xabar yubormaydi — bu siz kutgan narsa emas.

Tekshirib ko'ring: const bugun = memoize(() => new Date().getDay()); — kechasi soat 00:00 dan keyin bugun() nima qaytaradi?

3. Kesh kaliti

3.1 Bir nechta argument

memoize faqat birinchi argumentga qaraydi. masofaNarxi(km, tarif) ni shunday keshlasak, (4, "ekonom") va (4, "komfort") bitta javob olib qoladi. Bizga argumentlardan bitta kalit yasash kerak.

Birinchi xayolga keladigani — join:

const kalitA = ["a|b", "c"].join("|");
const kalitB = ["a", "b|c"].join("|");

console.log(kalitA, kalitB, kalitA === kalitB); // a|b|c a|b|c true

Ikki xil argumentlar to'plami bitta kalit berdi — bu to'qnashuv. Ajratuvchi belgi argumentning o'zida bo'lsa, join ishonchsiz. Ishonchliroq yo'l — JSON.stringify: u satrlarni qo'shtirnoq bilan o'raydi va turlarni farqlaydi:

console.log(JSON.stringify(["a|b", "c"])); // ["a|b","c"]
console.log(JSON.stringify([1, "1"])); // [1,"1"]
console.log(JSON.stringify([undefined, NaN])); // [null,null]

Oxirgi qatorga qarang: undefined va NaN ikkalasi ham null ga aylandi (JSON chuqur). Odatdagi son va satr argumentlarida bu muammo emas, lekin chegarasini bilib qo'ying.

3.2 Kalit yasovchini tashqaridan berish

Eng moslashuvchan yechim — kalitni qanday yasashni chaqiruvchiga topshirish. Standart holatda JSON.stringify ishlatamiz:

function memoize(funksiya, kalitYasa = (...a) => JSON.stringify(a)) {
  const kesh = new Map();
  return (...argumentlar) => {
    const kalit = kalitYasa(...argumentlar);
    if (!kesh.has(kalit)) {
      kesh.set(kalit, funksiya(...argumentlar));
    }
    return kesh.get(kalit);
  };
}

let hisoblar = 0;
const masofaNarxi = memoize((km, tarif) => {
  hisoblar++;
  return km * (tarif === "komfort" ? 3000 : 2000);
});

console.log(masofaNarxi(4, "ekonom")); // 8000
console.log(masofaNarxi(4, "komfort")); // 12000
console.log(masofaNarxi(4, "ekonom")); // 8000
console.log(hisoblar); // 2

Bitta argumentli funksiya uchun kalitYasa ni (x) => x qilib berish mumkin — JSON.stringify ga vaqt sarflanmaydi. Lodash'ning _.memoize ham shunday ikkinchi parametr (resolver) oladi.

3.3 Obyekt argument — JSON.stringify emas

Argument obyekt bo'lsa, JSON.stringify yana ikki muammo beradi. Birinchidan, kalitlar tartibi: { a: 1, b: 2 } va { b: 2, a: 1 } — bir xil ma'lumot, lekin har xil satr. Ikkinchidan, katta obyektni har chaqiruvda satrga aylantirish qimmat — ba'zan hisobning o'zidan ham qimmat.

Obyekt uchun boshqa yo'l bor: kalit — obyektning o'zi, uning mazmuni emas. Bu haqda «WeakMap bilan» bo'limida.

Tekshirib ko'ring: memoize(fn) ni ikkinchi parametrsiz ishlatib, fn(1) va fn("1") chaqirilsa, kesh nechta yozuv saqlaydi?

4. Rekursiv funksiyani memoizatsiya qilish

4.1 Tuzoq: tashqaridan o'rash

Fibonacci'ga qaytamiz. Birinchi urinish — tayyor memoize bilan o'rash:

function memoize(funksiya) {
  const kesh = new Map();
  return (arg) => {
    if (!kesh.has(arg)) {
      kesh.set(arg, funksiya(arg));
    }
    return kesh.get(arg);
  };
}

let chaqiruvlar = 0;
function fib(n) {
  chaqiruvlar++;
  return n < 2 ? n : fib(n - 1) + fib(n - 2);
}

const tezFib = memoize(fib);
console.log(tezFib(25)); // 75025
console.log(chaqiruvlar); // 242785

Chaqiruvlar soni o'zgarmadi! Sabab: fib ichida o'zini chaqiradi — fib(n - 1), tezFib(n - 1) emas. Kesh faqat eng tashqi chaqiruvni tutdi. Ichkaridagi chorak million chaqiruv keshni umuman ko'rmadi. Faqat tezFib(25) ni ikkinchi marta chaqirsangiz, u darhol keladi.

4.2 To'g'ri yo'l: ichki chaqiruvlar ham keshdan

Rekursiv chaqiruvlar ham keshdan o'tishi kerak. Eng sodda yo'l — keshni funksiyaning ichiga qurish. Shunda fib har safar — ichki chaqiruvlarda ham — avval keshga qaraydi:

const kesh = new Map();
let chaqiruvlar = 0;

function fib(n) {
  chaqiruvlar++;
  if (n < 2) {
    return n;
  }
  if (!kesh.has(n)) {
    kesh.set(n, fib(n - 1) + fib(n - 2));
  }
  return kesh.get(n);
}

console.log(fib(25)); // 75025
console.log(chaqiruvlar); // 49
console.log(fib(90)); // 2880067194370816000

242 785 o'rniga 49 ta chaqiruv. Har n uchun javob bir marta hisoblanadi, qolgan safar keshdan olinadi.

Naqshni toping: keshlangan fib(25) — 49 chaqiruv, fib(35) — 69 chaqiruv. Demak, fib(10) uchun — chaqiruv. fib(90) ham bir zumda chiqdi — oddiy rekursiya bilan uni hayotingiz davomida kutib bo'lmasdi.

fib(90) ning javobiga diqqat qiling: oxiri 000 bilan tugagan. Haqiqiy javob 2880067194370816120. Son Number.MAX_SAFE_INTEGER dan katta, shuning uchun aniqligi yo'qoldi (Son yozish shakllari). Bunday katta sonlar uchun BigInt kerak — bu memoizatsiyaga emas, son turiga tegishli masala.

Bu usulning algoritmlardagi nomi — "yuqoridan pastga dinamik dasturlash". Uni Dinamik dasturlash g'oyasi va memoization darsida chuqur o'rganamiz.

4.3 O'lchov

Qancha tez bo'ldi? Bir nechta funksiyani Node 24 da o'lchadik — har biri 5–9 marta, grafikda — o'rtadagi (mediana) natija:

Uch xulosa:

• fib(35) — taxminan 150 ms dan 0,005 ms gacha — grafikda ustun ko'rinmaydi ham. Bu yerda memoizatsiya algoritmni o'zgartirdi. Oddiy fib da n bittaga oshsa, ish taxminan 1,6 barobar ko'payadi — bunday o'sish eksponensial deyiladi. Keshlangan fib da esa n bittaga oshsa, atigi ikkita chaqiruv qo'shiladi — bu chiziqli o'sish. O'sish tezligini o'lchash tilini (Big-O) 14-qismda o'rganamiz.
• tubSoni (n gacha tub sonlarni sanaydigan og'ir funksiya) — 100 chaqiruvda faqat 10 xil argument bor edi. Keshlangani 10 marta hisobladi, va taxminan 10 barobar tez bo'ldi.
• x * 2 — keshlangani 2,5 barobar sekin. Map dan qidirish ko'paytirishdan qimmat. Arzon funksiyani keshlash zarar.

O'lchov kodi — o'z kompyuteringizda sinang, raqamlar boshqacha chiqadi, lekin nisbat o'xshash bo'ladi:

// O'lchov: vaqt har kompyuterda har xil, shuning uchun tekshirilmaydi
const ikkiBaravar = (x) => x * 2;
const ikkiBaravarKesh = memoize(ikkiBaravar);
const sonlar = Array.from({ length: 1_000_000 }, (_, i) => i % 100);

const variantlar = [
  ["oddiy", ikkiBaravar],
  ["kesh", ikkiBaravarKesh],
];
for (const [nom, fn] of variantlar) {
  const boshi = performance.now();
  sonlar.reduce((s, x) => s + fn(x), 0);
  console.log(nom, `${(performance.now() - boshi).toFixed(1)} ms`);
}

Bitta o'lchovga ishonmang: birinchi ishga tushirishda JavaScript dvigateli kodni hali "qizdirmagan" bo'ladi. To'g'ri benchmark qilishni Performansni o'lchash va benchmarking darsida o'rganamiz.

Tekshirib ko'ring: Qaysi funksiyani keshlash foydali: (narx) => narx * 1.12 yoki (matn) => matn.split(" ").length (100 KB lik maqola uchun, bir xil maqola ko'p marta)?

5. WeakMap bilan: obyekt kalit

5.1 Obyektga bog'langan kesh

WeakMap darsining 3-mashqida obyektKeshi yozgan edik. Endi uni memoizatsiya ko'zi bilan qayta ko'ramiz:

function obyektKeshi(funksiya) {
  const kesh = new WeakMap();
  return (obyekt) => {
    if (!kesh.has(obyekt)) {
      kesh.set(obyekt, funksiya(obyekt));
    }
    return kesh.get(obyekt);
  };
}

let hisoblar = 0;
const savatJami = obyektKeshi((savat) => {
  hisoblar++;
  return savat.reduce((s, taom) => s + taom.narx * taom.soni, 0);
});

const savat = [
  { nom: "Osh", narx: 35000, soni: 2 },
  { nom: "Ko'k choy", narx: 5000, soni: 1 },
];

console.log(savatJami(savat)); // 75000
console.log(savatJami(savat)); // 75000
console.log(hisoblar); // 1

Kalit — savat obyektining o'zi (havolasi). JSON.stringify yo'q, kalitlar tartibi muammosi yo'q. Va eng muhimi: WeakMap kalitni kuchsiz ushlaydi. Savat kerak bo'lmay qolsa, axlat yig'uvchi uni javobi bilan birga o'chiradi — kesh xotirani to'ldirmaydi.

5.2 Shart: ma'lumot o'zgarmasin

Bu kesh obyektning havolasiga qaraydi, mazmuniga emas. Savat ichi o'zgarsa-yu, havola o'sha-o'sha qolsa, kesh eski javobni beradi:

function obyektKeshi(funksiya) {
  const kesh = new WeakMap();
  return (obyekt) => {
    if (!kesh.has(obyekt)) {
      kesh.set(obyekt, funksiya(obyekt));
    }
    return kesh.get(obyekt);
  };
}

const savatJami = obyektKeshi((savat) =>
  savat.reduce((s, taom) => s + taom.narx * taom.soni, 0),
);

const savat = [{ nom: "Osh", narx: 35000, soni: 2 }];
console.log(savatJami(savat)); // 70000

savat.push({ nom: "Manti", narx: 30000, soni: 1 });
console.log(savatJami(savat)); // 70000 — eski javob!

const yangiSavat = [...savat];
console.log(savatJami(yangiSavat)); // 100000

push savatni joyida o'zgartirdi — havola o'zgarmadi, kesh 70 000 ni berdi. Haqiqiy javob esa 100 000. Spread bilan yasalgan yangi massiv esa yangi kalit — to'g'ri hisoblandi.

Mana nega Immutability chuqur darsi bu darsdan oldin keldi. Immutable yangilashda har o'zgarish yangi obyekt beradi. "Havola o'zgardi" esa "ma'lumot o'zgardi" degani bo'ladi. Kesh uchun bundan qulay shart yo'q: tekshiruv bitta has — ichiga kirish shart emas. React'dagi useMemo va Redux'dagi selektorlar aynan shu g'oyaga qurilgan.

Tekshirib ko'ring: obyektKeshi ga savatJami(5) deb son bersak nima bo'ladi?

6. Kesh hajmini cheklash: LRU

6.1 Cheksiz kesh — xotira sizishi

Map li kesh har yangi argumentni abadiy saqlaydi. Million xil argument — million yozuv. Kun bo'yi ishlaydigan server yoki brauzer sahifasida bu sekin-asta xotirani to'ldiradi — xotira sizib chiqishi (memory leak) (Closure tuzoqlari). Uni topishni Xotira sizishlari va ularni topish darsida o'rganamiz.

Yechim — keshga chegara qo'yish: masalan, ko'pi bilan 100 ta yozuv. Joy tugasa, qaysi birini o'chirish kerak? Eng mashhur javob — LRU (Least Recently Used, "eng uzoq vaqt ishlatilmagan"): eng uzoq vaqtdan beri hech kim so'ramagan yozuv chiqariladi.

O'xshatish: kiyim javoni. Joy tugasa, eng uzoq vaqt kiyilmagan ko'ylakni olib chiqasiz. Kecha kiygan ko'ylagingiz qoladi — ehtimol ertaga ham kiyasiz.

6.2 Map tartibi yordam beradi

Map bitta qulay xususiyatga ega: u kalitlarni qo'shilgan tartibda saqlaydi. Demak:

• eng eski yozuv — kesh.keys().next().value (birinchi kalit);
• yozuvni "yangi" qilish — uni o'chirib, qayta qo'shish (u oxiriga o'tadi).

Shu ikki fokus bilan LRU bir necha qatorda yoziladi. Qadamlarda kesh dagi tartibni kuzating — chegara 2:

Uchinchi qadamga e'tibor bering. osh so'ralgani uchun u "yoshardi" va chiqarib yuborilmadi. Agar bu qadam bo'lmaganida (oddiy "birinchi kelgan — birinchi chiqadi" navbati), choy kelganda osh o'chgan bo'lardi.

Bu yerda hisob funksiyasi konsolga yozadi — faqat qachon hisoblanganini ko'rish uchun. Haqiqiy keshlangan funksiya toza bo'ladi.

6.3 Chegarani qanday tanlash

Aniq formula yo'q. Chegara katta bo'lsa — xotira ko'p ketadi, kichik bo'lsa — yozuvlar tez chiqib ketib, kesh foydasiz bo'ladi. Amalda shunday qilinadi: taxminiy son qo'yiladi (100, 500, 1000), keyin "keshga tushish" ulushi o'lchanadi. So'rovlarning ko'pi keshdan kelsa — chegara yetarli.

Tayyor kutubxona ham bor: npm'dagi lru-cache paketi chegara, yozuvning yashash muddati (TTL — "time to live") va hajm bo'yicha cheklashni biladi. Paketlar bilan ishlashni 16-qismda chuqur ko'ramiz. Bugun o'zimiz yozganimiz — g'oyani tushunish uchun.

7. Asinxron funksiyani keshlash

Funksiya Promise qaytarsa-chi? Masalan, serverdan menyu turkumini oluvchi menyuniOl(turkum). Sahifaning ikki qismi (masalan, menyu ro'yxati va "tavsiya" bloki) bir vaqtda menyuniOl("milliy") ni chaqirsa, ikkita bir xil so'rov ketadi.

Yechim — keshga natijani emas, Promise'ning o'zini yozish. Ikkinchi chaqiruvchi hali tugamagan o'sha Promise'ni oladi va birga kutadi. Bitta qo'shimcha qoida bor: Promise rad etilsa, uni keshdan o'chirish kerak, aks holda xato abadiy keshda qoladi:

function vadaKeshi(funksiya) {
  const kesh = new Map();
  return (kalit) => {
    if (!kesh.has(kalit)) {
      const vada = funksiya(kalit).catch((xato) => {
        kesh.delete(kalit);
        throw xato;
      });
      kesh.set(kalit, vada);
    }
    return kesh.get(kalit);
  };
}

let urinish = 0;
const menyuniOl = vadaKeshi(async (turkum) => {
  urinish++;
  console.log(`so'rov ${urinish}: ${turkum}`);
  if (urinish === 1) {
    throw new Error("Tarmoq xatosi");
  }
  return ["Osh", "Manti"];
});

try {
  await menyuniOl("milliy");
} catch (xato) {
  console.log("Xato:", xato.message);
}

const [a, b] = await Promise.all([
  menyuniOl("milliy"),
  menyuniOl("milliy"),
]);
console.log(a, a === b);

Konsolda:

so'rov 1: milliy
Xato: Tarmoq xatosi
so'rov 2: milliy
[ 'Osh', 'Manti' ] true

Birinchi so'rov muvaffaqiyatsiz — u keshdan o'chirildi. Keyingi ikki parallel chaqiruv bitta so'rov yubordi (so'rov 2) va bir xil massivni oldi. catch ichidagi throw xato xatoni chaqiruvchiga qaytaradi — busiz xato "yutilib" ketardi (Xato strategiyasi).

Bir ogohlantirish. Serverdagi ma'lumot vaqt o'tib o'zgaradi — bu toza funksiya emas. Shuning uchun bunday keshga yashash muddati (TTL) qo'yiladi yoki ma'lumot o'zgarganda kesh tozalanadi. Bu kesh invalidatsiyasi deyiladi va dasturlashdagi eng qiyin masalalardan biri hisoblanadi. 11-qismdagi vazifalar da localStorage keshi shu sababli server bilan solishtirilardi (localStorage va sessionStorage).

8. Ko'p uchraydigan xatolar

8.1 Toza bo'lmagan funksiyani keshlash

Vaqt, tasodif yoki tashqi holatga bog'liq funksiya keshlansa, u eski javobni beraveradi. Yon ta'sirli funksiya esa ikkinchi chaqiruvda ishini qilmaydi. Tuzatish: keshni faqat toza funksiyaga qo'ying; server ma'lumoti uchun — TTL yoki aniq tozalash.

8.2 Rekursiyani tashqaridan o'rash

memoize(fib) — faqat tashqi chaqiruv keshlanadi, ichkaridagi millionlab chaqiruv keshni ko'rmaydi. Xato chiqmaydi, faqat tezlik o'zgarmaydi. Tuzatish: ichki chaqiruvlar ham keshlangan funksiyaga borsin — «Rekursiv funksiyani memoizatsiya qilish» bo'limidagidek.

8.3 Obyektni joyida o'zgartirish

WeakMap yoki Map keshida kalit obyekt bo'lsa-yu, uni push yoki obj.narx = ... bilan o'zgartirsangiz — kesh eski javobni beradi. Tuzatish: immutable yangilash — har o'zgarishda yangi obyekt.

8.4 Kalit to'qnashuvi

args.join("|") yoki String(arg) bilan yasalgan kalit ikki xil argumentga bir xil chiqishi mumkin. Natijada bir argument boshqasining javobini oladi. Tuzatish: JSON.stringify(args) yoki ma'lumotga mos aniq kalitYasa.

8.5 Cheksiz kesh va arzon funksiya

Chegarasiz kesh vaqt o'tib xotirani to'ldiradi; arzon funksiyani keshlash esa uni sekinlashtiradi. Tuzatish: avval o'lchang. Funksiya haqiqatan sekin va argumentlar haqiqatan takrorlanayotgan bo'lsagina keshlang — va chegara qo'ying.

9. Mashqlar

1-mashq (oson): Necha marta hisoblandi?

Darsdagi memoize (bitta argumentli, Map bilan) ni ko'chiring. yetkazishNarxi(km) funksiyasini yozing: 3 km gacha 10 000, undan keyin har km uchun 2 000 qo'shiladi. Uni keshlang va [2, 5, 2, 5, 8] masofalar uchun narxlarni chiqaring. Funksiya necha marta hisobladi?

function memoize(funksiya) {
  const kesh = new Map();
  return (arg) => {
    if (!kesh.has(arg)) {
      kesh.set(arg, funksiya(arg));
    }
    return kesh.get(arg);
  };
}

let hisoblar = 0;
const yetkazishNarxi = memoize((km) => {
  hisoblar++;
  return km <= 3 ? 10000 : 10000 + (km - 3) * 2000;
});

console.log([2, 5, 2, 5, 8].map(yetkazishNarxi));
console.log(hisoblar); // 3

[ 10000, 14000, 10000, 14000, 20000 ]
3

2-mashq (o'rta): Ko'p argumentli kesh

Darsdagi ikki parametrli memoize(funksiya, kalitYasa) ni ishlating. buyurtmaJami(narx, soni, chegirmaFoizi) ni keshlang. kalitYasa ni o'zingiz yozing: argumentlarni JSON.stringify siz, lekin to'qnashuvsiz birlashtiring. Ishora: hamma argument son — sonlarda | belgisi bo'lmaydi, demak join("|") bu yerda xavfsiz.

function memoize(funksiya, kalitYasa = (...a) => JSON.stringify(a)) {
  const kesh = new Map();
  return (...argumentlar) => {
    const kalit = kalitYasa(...argumentlar);
    if (!kesh.has(kalit)) {
      kesh.set(kalit, funksiya(...argumentlar));
    }
    return kesh.get(kalit);
  };
}

let hisoblar = 0;
const buyurtmaJami = memoize(
  (narx, soni, foiz) => {
    hisoblar++;
    return (narx * soni * (100 - foiz)) / 100;
  },
  (...sonlar) => sonlar.join("|"),
);

console.log(buyurtmaJami(35000, 2, 10)); // 63000
console.log(buyurtmaJami(35000, 2, 10)); // 63000
console.log(buyurtmaJami(35000, 21, 0)); // 735000
console.log(hisoblar); // 2

3-mashq (qiyin): LRU va hisoblagich

Darsdagi lruKesh ni takomillashtiring: qaytgan funksiyaning holat() metodi bo'lsin. U { yozuvlar, tushdi, otkazdi } ni qaytarsin: keshdagi kalitlar (tartibda), keshdan necha marta javob berilgani va necha marta hisoblangani. Ishora: funksiya — obyekt, unga xususiyat qo'shish mumkin (fn.holat = () => ...).

function lruKesh(funksiya, chegara) {
  const kesh = new Map();
  let tushdi = 0;
  let otkazdi = 0;
  const keshli = (kalit) => {
    if (kesh.has(kalit)) {
      tushdi++;
      const qiymat = kesh.get(kalit);
      kesh.delete(kalit);
      kesh.set(kalit, qiymat);
      return qiymat;
    }
    otkazdi++;
    const qiymat = funksiya(kalit);
    kesh.set(kalit, qiymat);
    if (kesh.size > chegara) {
      kesh.delete(kesh.keys().next().value);
    }
    return qiymat;
  };
  keshli.holat = () => ({
    yozuvlar: [...kesh.keys()],
    tushdi,
    otkazdi,
  });
  return keshli;
}

const kvadrat = lruKesh((x) => x * x, 3);
for (const x of [1, 2, 3, 1, 4, 5, 1]) {
  kvadrat(x);
}
console.log(kvadrat.holat());

{ yozuvlar: [ 4, 5, 1 ], tushdi: 2, otkazdi: 5 }

4-mashq: Vazifalar qadami — statistika keshi

vazifalar dagi statistika() har render da hamma vazifalarni Object.groupBy bilan qayta guruhlaydi. Kanon kodni o'zgartirmaymiz. kurs/mashqlar/12/26-memo/statistika.mjs da obyektKeshi bilan keshlangan statistikaHisobla(vazifalar) yozing. Ro'yxat immutable yangilansa (yangi massiv) — qayta hisoblansin, aks holda keshdan kelsin. Ishora: vazifa holatini almashtirish — map bilan yangi massiv (Ichma-ich ma'lumotni immutable yangilash).

function obyektKeshi(funksiya) {
  const kesh = new WeakMap();
  return (obyekt) => {
    if (!kesh.has(obyekt)) {
      kesh.set(obyekt, funksiya(obyekt));
    }
    return kesh.get(obyekt);
  };
}

let hisoblar = 0;
const statistikaHisobla = obyektKeshi((vazifalar) => {
  hisoblar++;
  const guruhlar = Object.groupBy(vazifalar, (v) =>
    v.bajarildi ? "bajarilgan" : "faol",
  );
  return {
    qoldi: guruhlar.faol?.length ?? 0,
    bajarildi: guruhlar.bajarilgan?.length ?? 0,
  };
});

let vazifalar = [
  { id: 1, matn: "Non olish", bajarildi: false },
  { id: 2, matn: "DOM darsini takrorlash", bajarildi: true },
];

console.log(statistikaHisobla(vazifalar));
console.log(statistikaHisobla(vazifalar));

vazifalar = vazifalar.map((v) =>
  v.id === 1 ? { ...v, bajarildi: true } : v,
);
console.log(statistikaHisobla(vazifalar));
console.log(`hisoblandi: ${hisoblar} marta`);

{ qoldi: 1, bajarildi: 1 }
{ qoldi: 1, bajarildi: 1 }
{ qoldi: 0, bajarildi: 2 }
hisoblandi: 2 marta

git add 12/26-memo/statistika.mjs
git commit -m "12/26: statistika keshi WeakMap bilan"

10. Real ishda

• React. useMemo (qiymatni keshlash), useCallback (funksiyani keshlash) va React.memo (komponentni keshlash) — hammasi memoizatsiya. Ular argumentlarni havola bo'yicha solishtiradi — shuning uchun React'da immutable yangilash majburiy. 17–18-qismlarda ko'rasiz.
• Selektorlar. Redux'dagi reselect kutubxonasi holatdan hisoblangan qiymatlarni keshlaydi: kirish havolasi o'zgarmasa, qayta hisoblamaydi.
• Kutubxonalar. Lodash _.memoize (ikkinchi parametri — kalit yasovchi), npm'dagi lru-cache (LRU + TTL). Serverda Redis — butun dastur uchun umumiy kesh (27-qismda).
• Algoritmlar. Dinamik dasturlash masalalari — yo'llar soni, eng uzun umumiy qism, tanga almashtirish — memoizatsiya bilan yechiladi. Intervyularda juda ko'p so'raladi.
• Intervyu. "memoize ni yozing", "rekursiv funksiyani qanday keshlaysiz?", "kesh qachon zarar?", "LRU ni qanday yozasiz?" — klassik savollar.

Xulosa

• Memoizatsiya — toza funksiyaning javobini argument bo'yicha keshlash; faqat toza va og'ir funksiyada foydali, arzonida — zarar (x * 2 2,5 barobar sekinlashdi).
• Kesh kaliti: bitta primitiv — Map kaliti; bir nechta argument — JSON.stringify yoki ajratuvchili join; kalitYasa ni tashqaridan berish mumkin.
• Rekursiv funksiyada ichki chaqiruvlar ham keshdan o'tishi kerak — shunda fib(25) 242 785 emas, 49 chaqiruv.
• Obyekt kalit — WeakMap: xotirani to'ldirmaydi, lekin faqat immutable ma'lumot bilan to'g'ri ishlaydi.
• LRU — kesh chegarasi; Map ning qo'shilish tartibi bilan: o'chirib qayta qo'shish — "yoshartirish", birinchi kalit — eng eskisi.
• Asinxron kesh Promise'ni saqlaydi va rad etilganini o'chiradi.

Keyingi dars: Xato va bo'sh qiymatlar bilan FP uslubida ishlash — null va throw o'rniga natijani Result va Maybe qutilarida qaytarishni o'rganamiz.

Manbalar

• MDN: "Map", "WeakMap", "Memoization" (Glossary) — developer.mozilla.org
• Lodash hujjatlari: _.memoize — lodash.com/docs
• lru-cache paketi — npmjs.com/package/lru-cache
• React hujjatlari: useMemo — react.dev/reference/react/useMemo