[파이썬] LRU Cache 구현 (Least Recently Used Cache)

LRU Cache란?

• 가장 오랫동안 사용되지 않은 (참조되지 않은) 페이지(데이터)를 교체하는 기법
• 캐시의 크기는 한정적이기 때문에 자주 사용되는 데이터는 캐시에 남기고, 자주 사용되지 않는 캐시는 삭제해서 제한된 리소스내에서 데이터를 빠르게 접근할 수 있게 합니다.

구현 방법 1) OrderedDict 활용

파이썬에서 OrderedDict 클래스를 제공합니다.  OrderedDict는 사전(해시) 자료구조인데 데이터를 삽입한 순서를 보장합니다. 이러한 OrderedDict 클래스의 특징을 이용해 LRU Cache를 구현할 수 있습니다.

from collections import OrderedDict


class LRUCache:
    def __init__(self, capacity):
        # 최대 캐시 크기
        self.capacity = capacity

        # 캐시 역할
        self.cache = OrderedDict()

    def get(self, key):
        if key not in self.cache:
            # 캐시에 키가 없으므로 return None
            return None
        else:
            # 캐시에 이미 존재
            # 사용되 었으므로 캐시의 제일  뒤로 옮기기
            self.cache.move_to_end(key)
            return self.cache[key]

    def put(self, key, value):
        # 캐시에 추가. 캐시에 이미 존재 했다면 value를 업데이트 수행
        self.cache[key] = value

        # 사용되 었으므로 캐시의 제일  뒤로 옮기기
        self.cache.move_to_end(key)

        # 캐시 사이즈가 최대 크기가 넘어섰다면
        if len(self.cache) > self.capacity:
            # 가장 오랫동안 참조되지 않은 아이템을 캐시에서 제거
            self.cache.popitem(last=False)


cache = LRUCache(capacity=3)
print(cache.cache)

cache.put(1, 1)
print(cache.cache)
cache.put(2, 2)
print(cache.cache)
cache.put(3, 3)
print(cache.cache)
cache.get(1)
print(cache.cache)
cache.get(3)
print(cache.cache)
cache.put(4, 4)
print(cache.cache)
cache.put(5, 5)
print(cache.cache)

출력

OrderedDict()
OrderedDict([(1, 1)])
OrderedDict([(1, 1), (2, 2)])
OrderedDict([(1, 1), (2, 2), (3, 3)])
OrderedDict([(2, 2), (3, 3), (1, 1)])
OrderedDict([(2, 2), (1, 1), (3, 3)])
OrderedDict([(1, 1), (3, 3), (4, 4)])
OrderedDict([(3, 3), (4, 4), (5, 5)])

위의 LRU Cache의 get(), put() 오퍼레이션을 도식화 하였습니다.

LRU Cache get(), put() 동작

구현 방법 2) dict 활용

파이썬 3.7 이상 버전 부터는 built-in dict 클래스 또한 삽입 순서를 보장합니다. 자신의 환경이 python3.7 이상이라면 OrderedDict가 아닌 built-in dict를 사용해서 LRU Cache를 구현할 수 있습니다.

Ordered dictionaries are just like regular dictionaries but have some extra capabilities relating to ordering operations. They have become less important now that the built-in dict class gained the ability to remember insertion order (this new behavior became guaranteed in Python 3.7). 
 ref. by - https://docs.python.org/3/library/collections.html

 

class LRUCache:
    def __init__(self, capacity):
        # 최대 캐시 크기
        self.capacity = capacity

        # 캐시 역할
        self.cache = dict()

    def get(self, key):
        value = self.cache.get(key, None)
        if value:
            # 캐시에 존재 했다면, 삭제하고 뒤에 추가
            del self.cache[key]
            self.cache[key] = value
        return value

    def put(self, key, value):
        # 캐시에 이미 존재한다면 삭제
        if key in self.cache:
            del self.cache[key]

        # 캐시에 추가
        self.cache[key] = value

        # 캐시 사이즈가 최대 크기가 넘어섰다면
        if len(self.cache) > self.capacity:
            # 가장 오랫동안 참조되지 않은 아이템을 캐시에서 제거
            first_item_key = next(iter(self.cache))
            del self.cache[first_item_key]


cache = LRUCache(capacity=3)
print(cache.cache)

cache.put(1, 1)
print(cache.cache)
cache.put(2, 2)
print(cache.cache)
cache.put(3, 3)
print(cache.cache)
cache.get(1)
print(cache.cache)
cache.get(3)
print(cache.cache)
cache.put(4, 4)
print(cache.cache)
cache.put(5, 5)
print(cache.cache)

출력

{}
{1: 1}
{1: 1, 2: 2}
{1: 1, 2: 2, 3: 3}
{2: 2, 3: 3, 1: 1}
{2: 2, 1: 1, 3: 3}
{1: 1, 3: 3, 4: 4}
{3: 3, 4: 4, 5: 5}

참고 자료

https://docs.python.org/3/library/collections.html

https://www.geeksforgeeks.org/lru-cache-in-python-using-ordereddict/

https://www.geeksforgeeks.org/lru-cache-in-python-using-ordereddict/