LRU Eviction

LRU orqali chiqarib tashlash

Kichik kiyim shkafingizga yangi kiyim sig'dirish uchun, ENG UZOQ vaqtdan beri kiymagan kiyimingizni chiqarib tashlaysiz — eng yaqinda kiygan kiyimni EMAS. LRU (Least Recently Used — "eng uzoq ishlatilmagan") — kesh xotirasi TO'LGANDA, aynan shu mantiqni qo'llaydi: eng UZOQ vaqt murojaat qilinmagan yozuvni chiqarib tashlaydi, joy ochish uchun.

example.go

package main

import (
	"container/list"
	"fmt"
)

type lruEntry struct {
	key   string
	value string
}

// LRUCache — container/list (ikki tomonlama bog'langan ro'yxat) + xarita orqali
type LRUCache struct {
	capacity int
	order    *list.List               // eng oxirgi ishlatilgan OLDINDA turadi
	items    map[string]*list.Element // kalit -> ro'yxatdagi element
}

func NewLRUCache(capacity int) *LRUCache {
	return &LRUCache{
		capacity: capacity,
		order:    list.New(),
		items:    make(map[string]*list.Element),
	}
}

func (c *LRUCache) Set(key, value string) {
	if elem, ok := c.items[key]; ok {
		c.order.MoveToFront(elem)
		elem.Value.(*lruEntry).value = value
		return
	}

	if c.order.Len() >= c.capacity {
		oldest := c.order.Back()
		if oldest != nil {
			c.order.Remove(oldest)
			delete(c.items, oldest.Value.(*lruEntry).key)
		}
	}

	elem := c.order.PushFront(&lruEntry{key: key, value: value})
	c.items[key] = elem
}

func (c *LRUCache) Get(key string) (string, bool) {
	elem, ok := c.items[key]
	if !ok {
		return "", false
	}
	c.order.MoveToFront(elem)
	return elem.Value.(*lruEntry).value, true
}

func main() {
	cache := NewLRUCache(2)
	cache.Set("a", "1")
	cache.Set("b", "2")
	cache.Get("a")        // "a" endi eng yaqinda ishlatilgan
	cache.Set("c", "3")   // xotira to'lgan, "b" ENG uzoq ishlatilmagan -> chiqariladi

	_, okA := cache.Get("a")
	_, okB := cache.Get("b")
	_, okC := cache.Get("c")
	fmt.Println(okA, okB, okC)
}

container/list — Go standart kutubxonasidagi ikki tomonlama bog'langan ro'yxat ("Data Structures in Go" kursida ko'rgan tuzilmalarning standart kutubxona ko'rinishi): ro'yxat BOSHIDA "eng yaqinda ishlatilgan", OXIRIDA "eng uzoq ishlatilmagan" yozuvlar turadi. MoveToFront — istalgan elementni BOSHGA ("eng yangi" o'ringa) darhol ko'chiradi.

items map[string]*list.Element — kalit orqali ro'yxatdagi elementga TO'G'RIDAN-TO'G'RI kirish imkonini beradi (aks holda har safar butun ro'yxatni AYLANIB chiqish kerak bo'lardi). Bu ikki tuzilmaning (ro'yxat + xarita) BIRGALIKDA ishlatilishi — LRU keshining klassik, samarali (O(1) vaqt murakkabligi) implementatsiyasi.

>_ Exercise

LRUCache'ga joriy elementlar sonini bilish imkonini qo'shing.

•Len() int metodini yozing: c.order.Len()ni qaytaring
•capacity=3 bilan cache yaratib, 5 ta kalitni ketma-ket Set qiling
•Len() natijasini chop eting (capacity'dan oshib ketmasligi kerak)

Stuck? Reveal a hint to help you.

Hints (0/3)

Key Takeaway

Key Takeaway:

LRU eviction — ikki tomonlama bog'langan ro'yxat va xaritani birlashtirib, xotira to'lganda eng uzoq vaqt ishlatilmagan yozuvni samarali (O(1)) tarzda chiqarib tashlash orqali, kesh hajmini nazorat ostida ushlab turadi.

NEXT UP

Concurrent Access Patterns

OUTPUT

$ go run main.go
Kodingizni ishga tushiring