როგორ ოქმნი LRU ქეშს O(1) get და put ოპერაციებით?

Question

Accepted Answer

**LRU (Least Recently Used) ქეშ** აშორებს ელემენტს, რომელიც ყველაზე დიდი ხნის განმავლობაში არ იყო მოწვდომილი, როდესაც მის ტევადობას აღწევს. კლასიკური დიზაინი აერთიანებს **hash map**-ს (O(1) ძებნა) და **doubly linked list**-ს (O(1) გადაწყობა), რაც იძლევა **O(1) get და put**. ## ორი სტრუქტურის დიზაინი ```text HashMap: key -> node DLL (recency order): MRU <-> ... <-> LRU get/put: map finds node move touched node to front (MRU) in O(1); DLL splices it evict the tail (LRU) when full to the front in O(1) ``` ## Code ```python from collections import OrderedDict class LRUCache: def __init__(self, capacity): self.cap = capacity self.cache = OrderedDict() # preserves access order def get(self, key): # O(1) if key not in self.cache: return -1 self.cache.move_to_end(key) # mark as most recently used return self.cache[key] def put(self, key, value): # O(1) if key in self.cache: self.cache.move_to_end(key) self.cache[key] = value if len(self.cache) > self.cap: self.cache.popitem(last=False) # evict least recently used ``` `OrderedDict` თავისთავად hash map-ი და doubly linked list-ია, ზუსტად ზემოთ აღწერილი სტრუქტურა. | ოპერაცია | დრო | |---|---| | get | O(1) | | put | O(1) | | space | O(capacity) | ## რატომ doubly linked list Douubly linked list საშუალებას გვაძლევს **ახსნათ ნოდი შუა ნაწილიდან O(1)**-ში (თქვენ გააჩნთ მის `prev`/`next`), რაც შეუძლებელია singly linked list-ით ან მასივით O(n) shift-ის გარეშე. ## რატომ არის მნიშვნელოვანი LRU ქეშები დგანან მონაცემთა ბაზების, ვებ სერვერებისა და CPU-ს წინ, რათა კვამლი მონაცემები სწრაფი იყოს და მეხსიერება შეზღუდული. ეს პრობლემა უფროსი დონის ინტერვიუს სტანდარტი ტესტია, რადგან ის ტესტავს ორი სტრუქტურის გაერთიანებას ისე, რომ *ერთეულის სისუსტე დაშუა იყოს მეორეს* — სისტემის დიზაინის ძირითადი უნარი.