LRU Cache Yazımı

Today at 05:50 OP

Thread Starter #0

Bir LRU (Least Recently Used) cache, en son kullanılan verileri saklayarak, bellek alanını optimize eden bir veri yapısıdır. Amaç, bellek sınırlarını aşmamak ve en sık erişilen verileri hızlı bir şekilde geri getirmektir. Bu yazıda, LRU cache'in nasıl yazılacağına dair temel bir rehber sunacağım.

LRU cache genellikle iki temel veri yapısı kullanır: bir hash tablosu ve bir çift yönlü bağlantılı liste. Hash tablosu, anahtar-değer çiftlerini hızlı bir şekilde erişebilmemizi sağlar. Çift yönlü bağlantılı liste ise, en son erişilen öğeleri başta tutarak, en az kullanılan öğeleri kolayca çıkarmamıza olanak tanır.

Veri Yapıları:

Hash Tablosu: Anahtarlar, liste düğümlerine işaret eder. Bu, belirli bir anahtarın değerine O(1) sürede erişmemizi sağlar.
Çift Yönlü Bağlantılı Liste: Liste başında en son erişilen öğeleri tutar. En son erişilen öğe eklenirken başa eklenir, en az erişilen öğe ise en sona eklenir.

Temel İşlemler:

Ekleme (put):
Eğer anahtar mevcutsa, değeri güncellenir ve değeri liste başına taşınır.
Eğer anahtar mevcut değilse ve kapasite aşılmışsa, en son öğe (liste sonundaki) silinir. Yeni öğe başa eklenir.

Erişim (get):
Eğer anahtar mevcutsa, değeri döndürülür ve öğe liste başına taşınır.
Anahtar mevcut değilse, -1 döner.

Örnek Uygulama:
Aşağıda, Python dilinde basit bir LRU cache uygulaması örneği verilmiştir:

CODE

123456789101112131415161718192021222324252627282930313233343536373839404142434445
class Node:
    def [b]init[/b](self, key, value):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None

class LRUCache:
    def [b]init[/b](self, capacity: int):
        self.capacity = capacity
        self.cache = {}
        self.head = Node(0, 0)
        self.tail = Node(0, 0)
        self.head.next = self.tail
        self.tail.prev = self.head

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

    def _add_to_head(self, node):
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node

    def get(self, key: int) -> int:
        if key in self.cache:
            node = self.cache[key]
            self._remove(node)
            self._add_to_head(node)
            return node.value
        return -1

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self._remove(self.cache[key])
        node = Node(key, value)
        self.cache[key] = node
        self._add_to_head(node)
        if len(self.cache) > self.capacity:
            lru = self.tail.prev
            self._remove(lru)
            del self.cache[lru.key]

Bu yapı, LRU cache'in temel mantığını ve nasıl implementasyonunu göstermektedir. LRU cache, özellikle bellek yönetimi ve veri erişim hızının kritik olduğu uygulamalarda oldukça faydalıdır.

Similar threads

Report Content