LeetCode: 146. LRU Cache

LRU(Least Recently Used) 알고리즘은 캐시나 메인 메모리에서 '메모리 관리 알고리즘'으로 많이 사용된다.

LRU 알고리즘에 대한 자세한 설명은 아래 링크를 참고하라.

https://focalpoint.tistory.com/137

쉽게 배우는 운영체제 내용 정리 - Chapter 09 가상 메모리 관리

간단히 말하자면, 메모리가 가득차면 가장 사용한지 오래 지난 부분을 버리는 것이다.

여기서 '사용'은 해당 부분에 접근하거나, 수정한 경우를 의미한다.

 

파이썬은 딕셔너리를 사용하여 LRU 알고리즘을 쉽게 구현가능하다.

파이썬 3.7부터 딕셔너리는 입력된 순서를 기억하며 저장한다. (마치 queue처럼)

즉, 딕셔너리에 원소를 추가하면 큐처럼 딕셔너리의 꼬리로 저장된다.

 

class LRUCache:

    def __init__(self, capacity: int):
        self.cache = dict()
        self.capacity = capacity
        self.cnt = 0
        
    def get(self, key: int) -> int:
        if key in self.cache:
            self.cache[key] = self.cache.pop(key)
            return self.cache[key]
        return -1

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.cache.pop(key)
            self.cache[key] = value
        else:
            if self.cnt == self.capacity:
                self.cache.pop(next(iter(self.cache)))
                self.cnt -= 1
            self.cache[key] = value
            self.cnt += 1

        


# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)

 

Doubly Linked List + Hash Solution

class DLinkedNode():
    def __init__(self, key=None, val=None, prv=None, nxt=None):
        self.key = key
        self.val = val
        self.prv = prv
        self.nxt = nxt

class DLinkedList():
    def __init__(self):
        self.head, self.tail = DLinkedNode(), DLinkedNode()
        self.head.nxt, self.tail.prv = self.tail, self.head

    def insertHead(self, node):
        node.prv, node.nxt = self.head, self.head.nxt
        self.head.nxt.prv = node
        self.head.nxt = node
        return node

    def removeNode(self, node):
        node.nxt.prv = node.prv
        node.prv.nxt = node.nxt
        return node

    def removeTail(self):
        return self.removeNode(self.tail.prv)

    def movetoHead(self, node):
        return self.insertHead(self.removeNode(node))


class LRUCache:
    def __init__(self, capacity: int):
        self.list = DLinkedList()
        self.address = dict()
        self.capacity = capacity
        self.cnt = 0

    def get(self, key: int) -> int:
        if key not in self.address:
            return -1
        node = self.address[key]
        self.address[key] = self.list.movetoHead(node)
        return node.val

    def put(self, key: int, value: int) -> None:
        if key in self.address:
            node = self.address[key]
            node.val = value
            self.address[key] = self.list.movetoHead(node)
        else:
            if self.cnt == self.capacity:
                self.address.pop(self.list.removeTail().key)
                self.cnt -= 1
            self.address[key] = self.list.insertHead(DLinkedNode(key, value))
            self.cnt += 1


# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)