leetcode : LFU Cache

LFU Cache - LeetCode

LFU Cache - LeetCode

 

너무 어려웠다..

전체적인 발상은 첨부터 맞게 했다. Doubly Linked List가 있어야 LRU도 구현 가능하고 O(1)타임에 삭제가 가능하겠구나 라는 생각이 들었고 노드에 연결된 dict와 LRU에 연결된 dict가 필요할거라고 생각했다. LRU에 연결된 dict는 frequency(내 코드에서는 count라고 표시했음)를 key로 갖고 참조수가 같은 노드들을 한 LRU, 즉 Doubly Linked List에 모아놓는다. 업데이트가 일어나면 노드를 LRU에서 빼고 lru dict [count + 1]인 lru를 찾아너 넣어주면 된다. 내가 구현이 오래걸렸던 이유는 용량이 다 차서 lfu(and lru) 노드를 pop하는 경우였는데 min frequency의 특성을 생각을 못해서 굉장히 복잡하게 생각했다.

min frequency는 다음과 같은 특성을 갖는다.

1. 새로운 key를 가지는 노드가 put되면 min frequency는 무조건 1로 초기화 된다.

2. 기존 요소에 get이나 put을 해서 카운트가 업데이트될때 min frequency에 해당하는 lru가 비어버렸으면 min frequency를 하나만 올려주면된다. 기존에 min frequency의 lru에 있던 노드가 min frequency + 1로 갔을거기때문.

즉 1로 초기화 하거나 1을 올리기만 하는것으로 최소값을 추적할수가 있다. 이 간단한걸 왜 생각을 못했을까.

 

근데 이것들을 알아도 구현은 까다롭다. 버그 없이 한번에 구현하기는 불가능에 가깝고 코드 실행 돌려보면서 잔버그들 좀 잡아야된다. get과 put모두 count를 업데이트하는 것을 포함하기 때문에 해당 코드는 따로 빼서 함수로 만들었다.

 

class Node:
    def __init__(self, key = None, value = None, count = 1, prev = None, next = None):
        self.key = key
        self.value = value
        self.count = count
        self.prev = prev
        self.next = next
        

class LRU: #Doubly Linked List
    def __init__(self):
        self.head = Node()
        self.tail = Node()
        self.head.next = self.tail
        self.tail.prev = self.head
        self.size = 0
        
    def __len__(self):
        return self.size

    def pop(self, node=None):
        if not node:
            node = self.head.next
        node.prev.next = node.next
        node.next.prev = node.prev
        self.size -= 1
        return node
    
    def append(self, node):
        node.next = self.tail
        node.prev = self.tail.prev
        self.tail.prev.next = node
        self.tail.prev = node
        self.size += 1
        

class LFUCache:

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.size = 0
        self.key_to_node = {}
        self.count_to_lru = {}
        self.min_count = 1
        
    def _count_up(self, node):
        count = node.count
        self.count_to_lru[count].pop(node)
        
        if not count+1 in self.count_to_lru:
            self.count_to_lru[count+1] = LRU()
        self.count_to_lru[count+1].append(node)
        
        if len(self.count_to_lru[count]) == 0:
            del self.count_to_lru[count]
            if count == self.min_count:
                self.min_count += 1
        
        node.count += 1
        
    def get(self, key):
        if key not in self.key_to_node:
            return -1
        node = self.key_to_node[key]
        self._count_up(node)
        return node.value

    def put(self, key, value):  
        if key in self.key_to_node:
            node = self.key_to_node[key]
            self._count_up(node)
            node.value = value
        elif self.capacity:
            if self.size == self.capacity:
                popped = self.count_to_lru[self.min_count].pop()
                del self.key_to_node[popped.key]
                self.size -= 1
                
            node = Node(key, value)
            self.key_to_node[key] = node
            
            if 1 not in self.count_to_lru:
                self.count_to_lru[1] = LRU()
                
            self.count_to_lru[1].append(node)
            self.min_count = 1
            self.size += 1
            

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

 

 

나중에 찾아보니까 LRU를 직접 구현하는 대신에 입력 순서를 고려하는 자료구조인 OrderedDict를 써도 된다고 한다. 그리고 파이썬 버전이 업뎃됨에 따라 기본 dict에 ordered dict기능이 생겼다고 함.