LRU keşinin layihələndirilməsi

LRU (Least Recently Used) keşi doludursa, ən uzun müddətdir istifadə olunmayan elementi çıxarır. Fikir sadədir: yaxın zamanda işlədilmiş element yenə işlədiləcək. Praktikada tələb: həm get(key), həm put(key, value) O(1) olmalıdır. Hazır funksiya keşi üçün memoizasiya və lru_cache mövzusuna baxın; burada keşin özünü quracağıq.

Niyə bir struktur kifayət etmir

• dict açarla O(1) tapır, amma «ən köhnə»ni bilmir.
• Siyahı sırani saxlayır, amma açarı tapmaq O(n)-dir.

Həll: dict + ikitərəfli əlaqəli siyahı (ikitərəfli siyahı).

• dict: açar → siyahı düyünü.
• Siyahı: baş tərəf «ən təzə», quyruq tərəf «ən köhnə» element.
• get: düyünü tapıb siyahının əvvəlinə köçürür.
• put: düyünü əvvələ qoyur, tutum aşılsa quyruqdakını çıxarır.

Siyahı ikitərəfli olmalıdır: ortadakı düyünü O(1)-də çıxarmaq üçün onun prev göstəricisi lazımdır. Gözətçi düyünlər (head, tail) kənar halları aradan qaldırır: siyahı heç vaxt «boş göstərici» ilə qarşılaşmır (dummy ideyası).

Reallaşdırma

class Node:
    def __init__(self, key=None, value=None):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None

class LRUCache:
    def __init__(self, capacity):
        if capacity <= 0:
            raise ValueError("capacity must be positive")
        self.capacity = capacity
        self.map = {}
        self.head = Node()
        self.tail = Node()
        self.head.next = self.tail
        self.tail.prev = self.head

    def _remove(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev