Linked List — pointer chasing-এর আসল দাম

লক্ষ্য: দুইটা structure-এর composition — dict-এর O(1) lookup + dll-এর O(1) reorder — একসাথে LRU দেয়; আর sentinel pattern দেখাবে edge-case elimination-এর কৌশল।

# lru_build.py — DLL + LRU with hit/miss ledger
# চালান: python3 lru_build.py

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


class DoublyLinkedList:
    """Sentinel-based — head.next প্রথম সদস্য, tail.prev শেষ।"""
    def __init__(self):
        self.head, self.tail = Node(), Node()
        self.head.next, self.tail.prev = self.tail, self.head
        self.size = 0

    def _link(self, a, b):
        a.next, b.prev = b, a

    def push_front(self, node):
        self._link(node, self.head.next)
        self._link(self.head, node)
        self.size += 1

    def unlink(self, node):
        self._link(node.prev, node.next)
        node.prev = node.next = None
        self.size -= 1
        return node

    def pop_tail(self):
        if self.size == 0:
            return None
        return self.unlink(self.tail.prev)


class LRUCache:
    def __init__(self, capacity):
        self.cap = capacity
        self.dll = DoublyLinkedList()
        self.map = {}            # key -> Node
        self.hits = 0
        self.misses = 0
        self.evictions = 0

    def get(self, key):
        node = self.map.get(key)
        if node is None:
            self.misses += 1
            return None
        self.hits += 1
        self.dll.unlink(node)
        self.dll.push_front(node)      # সদ্য-ব্যবহৃত = MRU
        return node.value

    def put(self, key, value):
        node = self.map.get(key)
        if node is not None:
            node.value = value
            self.dll.unlink(node)
            self.dll.push_front(node)
            return
        if self.dll.size >= self.cap:
            victim = self.dll.pop_tail()     # LRU শেষ প্রান্তে
            del self.map[victim.key]
            self.evictions += 1
        fresh = Node(key, value)
        self.map[key] = fresh
        self.dll.push_front(fresh)

    def report(self):
        total = self.hits + self.misses
        rate = self.hits / total * 100 if total else 0.0
        print(f'  size={self.dll.size:>3} hits={self.hits} '
              f'misses={self.misses} hit-rate={rate:5.1f}% '
              f'evictions={self.evictions}')


if __name__ == '__main__':
    cache = LRUCache(capacity=3)
    print('-- hot-key pattern (a,b ঘুরে ফেরে) --')
    for key in ('a', 'b', 'a', 'b', 'c', 'a', 'b'):
        if cache.get(key) is None:
            cache.put(key, f'val-{key}')
    cache.report()

    print('-- sequential flood (সব miss, সব evict) --')
    c2 = LRUCache(capacity=3)
    for i in range(10):
        k = f'k{i}'
        if c2.get(k) is None:
            c2.put(k, i)
    c2.report()

প্রত্যাশিত output:

-- hot-key pattern (a,b ঘুরে ফেরে) --
  size=  3 hits=3 misses=4 hit-rate= 42.9% evictions=1
-- sequential flood (সব miss, সব evict) --
  size=  3 hits=0 misses=10 hit-rate=  0.0% evictions=7

Reading: hot pattern-এ a,b promote হতে থাকায় তারা বাঁচে — hit-rate nonzero; flood pattern-এ প্রতিটা নতুন key ঠিক সবচেয়ে পুরনোটাকে evict করে — LRU-র worst-case adversary। দুই access pattern, একই policy — ফলাফল রাতদিন। এই সংবেদনশীলতাই LRU বেছে নেওয়ার বা না-নেওয়ার আসল বিচার।

নিজে বাড়ান:

1. move_to_back(key) যোগ করুন — MRU/LRU প্রান্ত swap করে LFU-lite experiment করুন
2. TTL support: node-এ timestamp রেখে get()-এ expire check — Redis- এর volatile-ttl-এর simplified রূপ
3. Benchmark: ১ লক্ষ random key access, capacity ১০,০০০ — Zipf-ish distribution বনাম uniform distribution-এ hit-rate তুলনা করুন; real-world hot-key skew-এর প্রভাব সংখ্যায় দেখুন