Vaqt murakkabligi
Eng yaxshi: O(1)
O'rtacha: O(1)
Eng yomon: O(n)
LRU keshi belgilangan miqdordagi yozuvlarni saqlaydi. Joy tugaganda, eng uzoq vaqt davomida foydalanilmagan yozuvni o‘chiradi. Asosiy vazifa — get va put amallarini O(1) vaqt ichida bajarish.
Nima uchun bitta ma’lumotlar tuzilmasi yetarli emas:
1. Faqat xesh-jadval O(1) vaqt ichida murojaat qilish imkonini beradi, ammo qaysi yozuv eng eski ekanini aniqlay olmaydi
2. Faqat tartiblangan ro‘yxat eng eski yozuvni aniqlaydi, ammo kalitni qidirish O(n) vaqt oladi
3. Shu sababli ular birlashtiriladi: xesh-jadval «qayerda?», ro‘yxat esa «qachon?» degan savolga javob beradi
Tuzilishi:
Xesh-jadval: key → tugunga ko‘rsatkich, O(1)
Ikki tomonlama bog‘langan ro‘yxat: head = eng so‘nggi ishlatilgan, tail = keyingi o‘chiriladigan tugun
E’tibordan chetda qolishi mumkin bo‘lgan ikki jihat:
Har bir tugun o‘z kalitini saqlaydi. O‘chirish jarayonida
tugun ro‘yxatning oxiridan olinadi va xesh-jadvaldagi
yozuvni o‘chirish uchun uning kaliti kerak bo‘ladi.
Aks holda, jadvalda mavjud bo‘lmagan tugun yozuvi qoladi.
Ro‘yxat ikki tomonlama bog‘langan bo‘lishi kerak. Tugunni
boshiga ko‘chirish uchun uni o‘rtadagi joyidan uzish kerak,
buning uchun esa prev ko‘rsatkichi zarur. Bir tomonlama
bog‘langan ro‘yxatda bu amal O(n) vaqt oladi.
Vaqt murakkabligi:
Eng yaxshi: O(1) — get va put amallari uchun
O‘rtacha: O(1) — xesh-jadvaldan qidirish va ko‘rsatkichlarni doimiy sondagi qayta bog‘lash amallari
Eng yomon: O(n) — faqat barcha kalitlar xesh-jadvalda bir xil joyga to‘qnashganda
Xotira murakkabligi: O(capacity)
Qo‘llanilishi: ma’lumotlar bazasi va veb-keshlar, Redis tizimida yozuvlarni o‘chirish (tanlab olishga asoslangan taxminiy usul), protsessor keshidagi ma’lumotlarni almashtirish, brauzerning oldinga va orqaga o‘tish tarixi, cheklangan xotira bilan memoizatsiya
O'xshash algoritmlar
Ko'p beriladigan savollar
- LRU keshi (Least Recently Used) nima?
- LRU keshi belgilangan miqdordagi yozuvlarni saqlaydi. Joy tugaganda, eng uzoq vaqt davomida foydalanilmagan yozuvni o‘chiradi. Asosiy vazifa — get va put amallarini O(1) vaqt ichida bajarish.
- LRU keshi (Least Recently Used) murakkabligi qanday?
- Vaqt (o'rtacha): O(1) — xesh-jadvaldan qidirish va ko‘rsatkichlarni doimiy sondagi qayta bog‘lash amallari · Xotira: O(capacity)
- Ushbu LRU keshi (Least Recently Used) vizualizatori kimlar uchun?
- LRU keshi (Least Recently Used) vizualizatsiyasi "Ma'lumotlar tuzilmalari" kategoriyasida yuqori darajadagi o'rganuvchilar uchun mo'ljallangan. Talabalar, texnik suhbatlarga tayyorgarlik va amaliy takrorlash uchun foydali.
- LRU keshi (Least Recently Used) ga o'xshash qanday algoritmlar bor?
- Shu kategoriyada (Ma'lumotlar tuzilmalari) quyidagilarni ko'rishingiz mumkin: Stack, Queue, Linked List. Har biri interaktiv vizualizatsiyaga ega.