🔔 آموزش یکی از ترسناک‌ترین الگوریتم‌ها در پایتون: 🕵️‍♂️🔍

سلام دوستان! می‌خوام درباره یکی از پیچیده‌ترین و ترسناک‌ترین الگوریتم‌ها در پایتون صحبت کنم:

الگوریتم صفحه‌بندی LRU (Least Recently Used).

این الگوریتم به خصوص در مدیریت حافظه و کش‌ها کاربرد داره. ممکنه در ابتدا ترسناک به نظر برسه، اما با فهم دقیق و تمرین، می‌تونید این الگوریتم رو به راحتی پیاده‌سازی کنید. پس بریم سراغ آموزش!

1. الگوریتم LRU چیه؟

الگوریتم LRU برای مدیریت حافظه و کش‌ها استفاده می‌شه. این الگوریتم قدیمی‌ترین آیتم‌های استفاده نشده را از حافظه حذف می‌کند تا جا برای آیتم‌های جدید باز شود.

2. ساختار داده‌های مورد نیاز

برای پیاده‌سازی LRU از یک دیکشنری و یک لیست دوطرفه استفاده می‌کنیم. دیکشنری برای جستجوی سریع و لیست دوطرفه برای نگهداری ترتیب استفاده از آیتم‌ها.

3. پیاده‌سازی LRU Cache

بیایید با هم یک LRU Cache را پیاده‌سازی کنیم:

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

class LRUCache:
    def __init__(self, capacity: int):
        self.cache = {}
        self.capacity = capacity
        self.size = 0
        self.head = DLinkedNode()
        self.tail = DLinkedNode()
        self.head.next = self.tail
        self.tail.prev = self.head

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

    def _remove_node(self, node):
        prev = node.prev
        new = node.next
        prev.next = new
        new.prev = prev

    def _move_to_head(self, node):
        self._remove_node(node)
        self._add_node(node)

    def _pop_tail(self):
        res = self.tail.prev
        self._remove_node(res)
        return res

    def get(self, key: int) -> int:
        node = self.cache.get(key, None)
        if not node:
            return -1
        self._move_to_head(node)
        return node.value

    def put(self, key: int, value: int) -> None:
        node = self.cache.get(key)
        if not node:
            newNode = DLinkedNode(key, value)
            self.cache[key] = newNode
            self._add_node(newNode)
            self.size += 1
            if self.size > self.capacity:
                tail = self._pop_tail()
                del self.cache[tail.key]
                self.size -= 1
        else:
            node.value = value
            self._move_to_head(node)

4. نحوه استفاده از LRU Cache

حالا بیایید یک نمونه از استفاده از LRU Cache را ببینیم:

lru_cache = LRUCache(2)

lru_cache.put(1, 1)
lru_cache.put(2, 2)
print(lru_cache.get(1))    # 1
lru_cache.put(3, 3)        # حذف کلید 2
print(lru_cache.get(2))    # -1 (کلید 2 حذف شده)
lru_cache.put(4, 4)        # حذف کلید 1
print(lru_cache.get(1))    # -1 (کلید 1 حذف شده)
print(lru_cache.get(3))    # 3
print(lru_cache.get(4))    # 4

نتیجه‌گیری

الگوریتم LRU یکی از پیچیده‌ترین و کارآمدترین الگوریتم‌ها برای مدیریت حافظه و کش است. با استفاده از دیکشنری و لیست دوطرفه، می‌توانید این الگوریتم را به راحتی در پایتون پیاده‌سازی کنید.

الگوریتم های بیشتر توی کانال ما

#برنامه‌نویسی #پایتون #آموزش #الگوریتم #LRU