파이썬 ordereddict move_to_end에 대해 알아봅시다.

 파이썬의 orderedDict에 대해 조금 더 알아봅시다. 이전에 이 글에서 popitem에 대해 간략하게만 설명드리고 넘어갔습니다. 여기 조금 더 심화된 내용을 학습해 보겠습니다.

 

---

 OrderedDict의 경우, 들어온 순서가 유지되는 딕셔너리입니다. 고로 lru와 같은 것과 잘 맞는다고 했습니다. 예제 하나를 볼 건데요. 자세히 분석해 보겠습니다.

 

 먼저, OrderedDict 객체를 하나 선언할 거에요. 그리고 "a", "b", "c" 순서대로 넣었습니다.

 

 다음에 lru를 출력하고, 가장 첫 번째 원소를 출력할 거에요.

 

 그러면 출력 결과가 이렇게 나와요. 이것에 대해서 먼저 해석해 보겠습니다. 들어온 순서를 유지하는 것이 OrderedDict이라고 했어요. 고로, 이 때 그림은 아래와 같이 그려집니다.

 

 

 여기까지는 대강 이해되시리라 믿습니다. next(iter(lru)) 이 부분은 무엇일까요? 일단, lru 역시 순회 가능한 무언가이기 때문에 이터레이터가 있습니다. 순방향 이터레이터는 처음부터 끝까지 탐색하는 것이고, 역방향은 역순으로 탐색하는 것입니다. next(iter)는 현재 이터레이터가 가리키는 원소를 리턴하게 되는데요.

 

 

 처음 녀석인 "a"를 가리키므로 a를 돌려줍니다. 만약에 또 다시 next를 호출하면, b, c 순으로 순회가 이루어질 겁니다.

 

---

 lru.move_to_end("a")가 있는데요. 오늘의 핵심입니다. 이것이 대체 무엇인가? 특정 키 값을 맨 마지막으로 보내버립니다. 즉, "a"가 제일 마지막에 추가된 것처럼 해 버린다는 의미입니다. LRU에서는 더 이상 캐시에 저장할 수 없을 때 가장 오래 전에 접근한 것을 제거해 버립니다.

 

 키가 없으면 KeyError를 떨구기 때문에, lru를 구현한 경우, 이미 있는 키에 access 하는 용도로 쓰이게 됩니다.

 

 

 move_to_end("a")를 하면 어떤 일이 일어나는가? a를 맨 뒤로 보낸다고 했지요? 그러면, a를 제거한 다음에 가장 마지막 위치에 보내버립니다.

 

 요렇게요. 이 작업을 매우 빠르게 끝낼 수 있어요. 왜냐? 키 "a"가 있는 위치를 hash로 빠르게 찾을 수 있습니다. 그리고, 위치만 알면 List는 원소를 제거하고 추가하는 연산을 매우 빠르게 끝내버릴 수 있습니다. lru 효율적으로 구현 뚝딱 했습니다. 이 문제 풀 수 있겠습니다.

 

 이제 next(iter(lru))와 next(reversed(lru))의 결과값은 예측할 수 있습니다. 전자는 b이고, 후자는 a입니다.

 

 요기까지도 별로 어렵지 않습니다. 이제 popitem의 last 인자는 무엇을 의미할까요? 어느 것의 last일까요?

 

 

 7번째 줄까지 수행하면, b, c, a 순으로 오래된 순입니다. 고로 b가 먼저 올 겁니다. last가 False라는 의미는 맨 처음의 원소인 'b'가 제거된다는 것입니다. 즉, 가장 오랫동안 접근하지 않은 원소가 제거되는 것과 동일합니다. 8번째 줄이 수행된 후 상태는 아래와 같이 변합니다.

 

 

 이제 lru.popitem(last=True)를 호출합니다. last는 위 그림에서 "a"입니다.

 

 따라서 "a"가 제거되게 됩니다.