Project: LRU Cache တစ်ခု ဆောက်ခြင်း

နားလည်ထားရမယ့် အချက်

Cache တစ်ခုမှာ လိုအပ်ချက်နှစ်ခု တပြိုင်တည်း လိုတယ်: key နဲ့ ချက်ချင်း ရှာတွေ့နိုင်ရမယ်၊ ပြီးတော့ ဘယ် entry က အနှောင့်အကြာဆုံး မသုံးခဲ့ဘူးဆိုတာ သိနေရမယ် (full ဖြစ်ရင် ဖျက်ချဖို့)။ hash map တစ်ခုတည်းဆို O(1) lookup ရပေမယ့် order concept မရှိလို့ least-recently-used ကို ရှာဖို့ entry အားလုံး scan လုပ်ရမယ်—eviction က O(n) ဖြစ်သွားမယ်။ linked list တစ်ခုတည်းဆိုလည်း node ကို front ကို O(1) နဲ့ ရွှေ့လို့ရပေမယ့် key နဲ့ ရှာဖို့ list တစ်ခုလုံး လျှောက်ကြည့်ရလို့ O(n) ဖြစ်တယ်။ LRU cache design က ဒီနှစ်ခုကို ပေါင်းစပ်ခြင်းနဲ့ naive approach နှစ်ခုစလုံးကို အနိုင်ယူတယ်: hash map က key ကနေ node reference ကို instant ရှာပေးတယ်၊ doubly linked list က recency order ကို ထိန်းထားတယ်၊ node ရဲ့ pointer တွေကြောင့် ဘာမှ shift မလုပ်ဘဲ O(1) နဲ့ unlink/relink လုပ်လို့ရတယ်။ `get` တိုင်း access လုပ်တဲ့ node ကို front ကို O(1) နဲ့ ရွှေ့တယ်၊ `put` တိုင်း update လုပ်တာ ဒါမှမဟုတ် capacity ကျော်ရင် tail (least recently used) ကို O(1) နဲ့ evict လုပ်တယ်။ Python ရဲ့ `OrderedDict` က ဒီ hybrid ကို အတွင်းပိုင်းမှာ အတိအကျ implement လုပ်ထားလို့ `move_to_end()` နဲ့ `popitem(last=False)` က O(1) ဖြစ်နေတာပါ။

လက်တွေ့ scenario နဲ့ ချိတ်ကြည့်မယ်

ဒါက Tutorial Platform ရဲ့ lesson-loading logic ရှေ့မှာ တကယ်ထားရမယ့် mechanism ပါပဲ: learner အများကြီးက ထပ်ခါထပ်ခါ တောင်းတဲ့ hot lesson တွေ (popular Python intro, trending JS tutorial) ကို fixed capacity နဲ့ memory ထဲ cache ထားလိုက်ရင် ထပ်တောင်းလာတဲ့အခါ file ကို ပြန်ဖတ်တာ ဒါမှမဟုတ် database ကို ပြန် hit တာ လုံးဝ ကျော်သွားနိုင်တယ်။ lesson အသစ် တောင်းလာပြီး cache ပြည့်နေရင် LRU policy က ကြာကြာ မတွေ့ခဲ့တဲ့ cached lesson ကို evict လုပ်တယ်—ဒါက ရှေ့ကို ပြန်တောင်းနိုင်ခြေ အနည်းဆုံးဖြစ်တယ်ဆိုတဲ့ ယုတ္တိကျတဲ့ ခန့်မှန်းချက်ပါ၊ random evict လုပ်တာ ဒါမှမဟုတ် လုံးဝ evict မလုပ်တာ (site ရဲ့ lesson catalog က tutorial 55 ကျော် ကြီးထွားလာရင် memory leak ဖြစ်မယ့်ကိစ္စ) နဲ့ ယှဉ်ရင်။

Hash map တစ်ခုတည်းက order မထိန်းနိုင်လို့ eviction က O(n) ဖြစ်သွားတယ်
Doubly linked list တစ်ခုတည်းက key lookup အတွက် O(n) ဖြစ်နေတယ်
Hash map + doubly linked list ပေါင်းလိုက်မှ get/put နှစ်ခုစလုံး O(1) ရရှိတယ်

အတူတူ စမ်းရေးကြည့်မယ်

python

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        # OrderedDict internally pairs a hash map with a doubly linked list:
        # move_to_end() and popitem(last=False) are both O(1) because of it.
        self.cache = OrderedDict()

    def get(self, key):
        if key not in self.cache:
            return -1
        # Accessing a key counts as "recently used" -> move it to the front
        self.cache.move_to_end(key)
        return self.cache[key]

    def put(self, key, value):
        if key in self.cache:
            # Refresh existing entry's position before updating
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.capacity:
            # Evict the least-recently-used entry (front of the OrderedDict)
            self.cache.popitem(last=False)

if __name__ == "__main__":
    cache = LRUCache(2)
    cache.put("python-basics", "<lesson html>")
    cache.put("js-intro", "<lesson html>")
    print(cache.get("python-basics"))  # hit -> becomes most recently used
    cache.put("rust-ownership", "<lesson html>")  # evicts "js-intro"
    print(cache.get("js-intro"))  # -1, was evicted
    print(list(cache.cache.keys()))  # remaining cached lesson slugs

You should see

`<lesson html>`, `-1`, ပြီးတော့ ကျန်ရှိနေတဲ့ cache key list `['python-basics', 'rust-ownership']` ကို print ထုတ်တယ်—`js-intro` ကို evict လုပ်ခဲ့တာကို ပြသတယ်။

၅ မိနစ် စမ်းကြည့်

Cache hit rate ကို track လုပ်ပေးမယ့် `stats()` method ထပ်ထည့်ပါ — get calls စုစုပေါင်း၊ hit အရေအတွက်၊ miss အရေအတွက်ကို ပြန်ပေးပါ။

သတိလေးတစ်ချက်

`get` ခေါ်တဲ့အခါ `move_to_end()` ခေါ်ဖို့ မေ့တတ်တယ် — ဒါဆို read လုပ်တာက recency order ကို update မလုပ်တော့ဘဲ LRU semantics ပျက်သွားတယ်

Capacity check ကို `put` အစမှာ လုပ်မယ့်အစား နောက်ဆုံးမှာ လုပ်ရင် သို့မဟုတ် `>` အစား `>=` သုံးမိရင် off-by-one ဖြစ်ပြီး cache size လွဲသွားနိုင်တယ်

Python Docs — functools.lru_cache — Data Structures & Algorithms