파이썬은 ordereddict 클래스가 있습니다. 이 클래스에 있는 함수들을 적절하게 이용하면 python lru 클래스를 구현할 수 있습니다. 이 방법을 간단하게 알아보고 직접 구현해 봅니다. 아래 글을 이해하시면 이 글을 더 쉽게 이해하실 수 있습니다.
클래스 정의하기
먼저, python lru 기능을 구현할 클래스는 아래와 같습니다.
필드는 2개를 가집니다.
- cache
- cache_size
cache랑 cache_size가 있네요. 여기서 cache는 ordereddict입니다. 포장된 객체라고 이해하면 편합니다. 다음에, cache_size는 캐시의 capacity를 의미합니다. 이 capacity보다 size가 더 커졌을 때에는, 가장 오래된 key를 제거하는 로직을 수행하게 됩니다.
LRU 객체가 위와 같은 상태라고 해 보겠습니다. 현재 cache에는 3개가 들어있고, capacity가 4이므로 더 들어갈 수 있습니다. 여기서 “e”를 넣어보겠습니다.
그러면 cache의 size가 4가 됩니다. 다음에, “f”를 넣는다고 해 볼게요. 이 경우, 들어갈 자리가 없습니다. 따라서, 가장 오래된 “a”가 제거되고, “f”가 맨 뒤에 추가되게 됩니다.
결국, 새로운 원소가 추가되려고 할 때, 이 cache_size, capacity 값을 가지고 오래된 것을 제거할지, 그렇게 하지 않을지 결정합니다. 이 정도만 있으면 될 듯 합니다. 즉, last에는 가장 최근에 추가하거나 접근한 키가, first에는 가장 오래 전에 접근한 키가 있습니다.
키가 있을 때 처리하기
key가 있을 때에는 어떻게 처리해야 할까요? 바로 최근에 접근했다는 표시를 하는 것입니다. 즉 키 k에 접근하면 아래와 같은 일이 일어납니다.
- key의 접근 시각이 가장 최신이 됩니다.
- 즉 key는 맨 뒤로 이동합니다.
이를 순서도로 표현하면 아래와 같습니다.
가장 적절한 함수는 move_to_end입니다. 이 함수가 무엇을 하는 것인가?
cache에 “a”, “c”, “d” 순서로 추가되었다는 정보가 들어가 있어요. move_to_end에 “c”를 넘겨주면, “c”를 맨 뒤로 보내버립니다.
그러면 위와 같이 그려지게 됩니다. begin이 가장 오래 전에 추가된 것이고, last가 가장 최근에 접근한 노드를 가리킬 때, move_to_end 만으로 키에 access 한 효과를 가지게 된 것입니다. 아래 그림 2에 있는 함수 access_station_data 함수를 볼게요. 이 station_data는 역 정보를 lru 캐시로 관리합니다.
그림 2의 access_station_data에서 key in self.cache 조건을 봅시다. cache에 key가 있는 경우를 처리한 것입니다. 이 때에는 key를 맨 뒤로 보내버리면 됩니다.
키가 없을 때 처리하기
그러면 키가 없을 때에는 어떻게 해야 할까요? 이 경우, 케이스를 나누어서 볼 수 있어요.
- 이미 capacity 만큼 cache에 키가 있을 때
- 가장 오래 전에 추가된 key를 제거합니다.
- 새로운 key를 추가합니다.
- 추가할 수 있을 정도의 여유가 있을 때
- 새로운 key를 추가합니다.
공통점은, 새로운 key를 추가하는 일입니다. 그렇다면, capacity만큼 cache에 키가 이미 있는 경우, 가장 오래 전에 추가된 key를 제거하는 일을 수행해야 합니다. 그 다음에, 새로운 키를 추가합니다. 이를 순서도로 나타내면 아래와 같습니다.
파란색의 조건 판단과 노란색 코드를 어떻게 구현해야 할까요?
- len(self.cache)는 cache에 있는 키의 개수입니다.
- self.cache_size는 cache의 capacity입니다.
- len(self.cache)가 self.cache_size보다 같거나 크다면을 코드로 구현하면 됩니다.
다음 노란색 조건은 pop_item 함수입니다. 이 함수는 default로 가장 뒤에 있는 원소를 제거하기 때문에, last 키워드 인자를 False로 주어야 합니다. 이를 순서도로 정리하면 아래와 같습니다.
키가 존재하면 그냥 key를 맨 뒤로 이동시킵니다. 그렇지 않으면 키가 추가되어야 하는 상황인데요. 이미 용량만큼 키가 들어가 있다면 가장 오래 전의 키를 제거합니다. 그 다음에 새로운 key를 맨 뒤에 추가합니다.
이를 코드로 구현하면 아래와 같습니다.
22번째 줄을 봅시다. len(self.cache)는 캐시에 들어있는 키의 개수를 의미해요. 다음에 self.cache_size는 캐시의 capacity를 의미해요. 추가하기 전에, 22번째 줄의 조건이 걸렸다는 의미는 이미 꽉 찬 상태라는 것이지요.
그렇기 때문에, cache에서 키 하나를 제거해야 하는데, popitem 함수는 아이템을 하나 제거해요. last를 False로 두면 가장 첫 번째 원소를 제거합니다. 가장 첫 번째 원소는 오래 전에 추가한 것이고, 이를 제거하는 것은 lru의 동작과 맞아 떨어집니다. 그 다음에, key를 추가해 주면 됩니다. 이는 26번째 줄에서 하고 있습니다.