146. LRU Cache

https://leetcode.com/problems/lru-cache/

LRU Cache - LeetCode

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.

Implement the LRUCache class:

• LRUCache(int capacity) Initialize the LRU cache with positive size capacity.
• int get(int key) Return the value of the key if the key exists, otherwise return -1.
• void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key.

The functions get and put must each run in O(1) average time complexity.

 

Example 1:

Input

["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]

[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]

 

Output

[null, null, null, 1, null, -1, null, -1, 3, 4]

 

Explanation LRUCache lRUCache = new LRUCache(2);

lRUCache.put(1, 1); // cache is {1=1}

lRUCache.put(2, 2); // cache is {1=1, 2=2}

lRUCache.get(1); // return 1

lRUCache.put(3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3}

lRUCache.get(2); // returns -1 (not found)

lRUCache.put(4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3}

lRUCache.get(1); // return -1 (not found)

lRUCache.get(3); // return 3

lRUCache.get(4); // return 4

 

Constraints:

• 1 <= capacity <= 3000
• 0 <= key <= 104
• 0 <= value <= 105
• At most 2 * 105 calls will be made to get and put.

 

Solution

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity: int):
        self.cache = OrderedDict()
        self.capacity = capacity

    def get(self, key: int) -> int:
        if key in self.cache:
            self.cache.move_to_end(key)
            return self.cache[key]
        return -1

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            del self.cache[key]

        self.cache[key] = value

        if len(self.cache) > self.capacity:
            self.cache.popitem(last=False)

• OrederedDict를 이용하여, 딕셔너리의 순서를 활용한다.
• get( ) : 인자로 받은 key가 있으면, 그 key의 데이터를 마지막 순서로 보내고 반환한다. 없으면 -1 반환.
• put( ) : 인자로 받은 key가 있으면, 그 key를 삭제한다. 데이터를 넣고, 용량을 초과하면 가장 오래동안 쓰지 않은 데이터를 삭제한다.
• put( ) 에서 데이터를 덮어쓰지 않고, 이미 존재하는 데이터를 삭제하는 이유는, 덮어쓸 때 순서가 최신화되지 않기 때문이다. 

another

class LRUCache(OrderedDict):

    def __init__(self, capacity):
        self.capacity = capacity

    def get(self, key):
        if key not in self:
            return - 1
        
        self.move_to_end(key)
        return self[key]

    def put(self, key, value):
        if key in self:
            self.move_to_end(key)
        self[key] = value
        if len(self) > self.capacity:
            self.popitem(last = False)

• 방법은 동일하지만, 참신하다.
• OrderedDict 를 import해서 사용하는 것이 아니라, class의 상속으로 가져온다.
• 그래서 딕셔너리에 접근할 때도 self[key] 로 접근한다.

---

OrderedDict

from collections import OrderedDict

collections 모듈의 OrderedDict 클래스에 대해 정리해보자.

 

기존의 dict는 삽입된 데이터의 순서를 기억하지 않았고, 반면 ordereddict를 사용하면 삽입된 데이터의 순서를 저장한다. 그래도 3.6부터는 기본 dict도 순서를 기억하게 되어서 현재는 이를 위해 ordereddict를 사용하진 않는다.

 

ordereddict의 함수를 살펴보며, 왜 사용하는지 보자.

popitem(last)

요소 하나를 반환하고 해당 데이터를 삭제하는 함수이다.

last = True 일 때, LIFO(Last In / First Out) 방식으로 반환하고 데이터를 삭제한다.

last = False 일 때, FIFO(First In / First Out) 방식으로 반환하고 데이터를 삭제한다. 

 

기본 딕셔너리에도 pop 함수가 있다. 인자로 받은 key의 value를 리턴하고 삭제한다.

popitem 함수는 임의의 값을 리턴하고 삭제한다.

따라서 마지막 혹은 첫 요소를 불러오고 삭제하는 기능까지는 수행하지 못한다.

 

move_to_end(key, last)

요소 하나의 순서를 끝으로 이동시킨다.

last =True 일 때, key에 해당하는 데이터를 맨 뒤로 보낸다.

last = False일 때, key에 해당하는 데이터를 맨 앞으로 보낸다.

 

비교

기본 dict는 순서가 다르더라도 key:value의 쌍이 같으면 같은 딕셔너리라고 판단한다.반면 odereddict는 순서까지 같아야 같은 딕셔너리라고 판단한다.