파이썬 ordereddict 클래스는 얼핏 보면 딕셔너리와 별 차이가 없어 보입니다. 딕셔너리가 있는데 왜 이 클래스를 쓸까요? 이는, 몇 가지 추가 함수들을 제공해 주기 때문입니다. 대표적인 두 가지는 아래와 같습니다.
- move_to_end
- popitem
- last keyword parameter
이 글에서는 이들에 대해 알아봅니다.
파이썬 ordereddict 간단한 구조 보기
먼저, 코드를 보면서 간단한 구조부터 파악해 봅시다.
__init__를 보면, __root와 __hardroot, __map이 있습니다. 여기서 __map은, ordereddict 내부에 있는, 진짜 데이터를 저장해 놓은 map이라고 할 수 있어요. 다음에, __root의 prev와 next는 각각 root를 가리키는 것을 볼 수 있는데요. 이는 원형 링크드 리스트를 구현하기 위함입니다.
이를 그림으로 그리면 아래와 같습니다.
이제, “c”, “a”가 파이썬 ordereddict 자료구조에 순서대로 추가되었습니다. 상황이 어떻게 변할까요?
이 그림을 보세요.
- 노란색 부분
- root를 의미합니다.
- 원형으로 순환하는 양방향 리스트입니다.
- 따라서 처음 원소와 마지막 원소가 root와 연결되어 있습니다.
- 회색 부분
- last를 의미합니다.
즉, root, 노드 “a”, 노드 “c”, root 순으로 양방향 연결되어 있는 링크드 리스트가 하나 나올 겁니다. 그리고, 키 “a”와 키 “c”가 각각 값 노드 “a”, 노드 “c”와 연관되게 됩니다. 이 구조 다 그리셨으면, 이제 아래 세 개의 함수를 간략하게 보겠습니다.
- __setitem__
- move_to_end
- popitem
__setitem__ 알아보기
먼저 __setitem__ 함수를 보겠습니다. 이 함수는 o가 ordereddict 객체라고 할 때, o[‘b’] = ‘b’를 호출하면 일어나는 일입니다.
먼저, key가 ordereddict에 없는 경우 아래와 같은 일이 일어납니다. “b”가 추가되었다고 해 보겠습니다. 그러면, 새로운 노드 “b”가 추가될 겁니다. 그리고 어떻게 되는가?
- 노드 “b”의 prev는 기존의 last와 연결됩니다.
- last의 next는 노드 “b”와 연결됩니다.
- 노드 “b”의 next는 root와 연결됩니다. root의 prev는 노드 “b”와 연결되겠네요.
따라서, 아래 그림과 같이 연결됩니다.
여기서 조심해야 할 것은 이 함수는 key값이 이미 있다고 했을 때, 대응되는 값만 업데이트 할 뿐이지, 접근 시각을 갱신해 주지는 않는다는 것입니다. 이 말은 last의 변화가 일어나지 않는다는 것입니다. 접근 시각을 갱신하려면 key가 이미 self에 있는 경우 맨 아래에 있는 dict_setitem만 호출하게 되는데, 여기서 link를 건드리지 않습니다.
만약에 access time까지 업데이트 하게 하려면 두 방법 중 하나를 써야 합니다.
- key를 제거하고 다시 추가한다.
- move_to_end를 사용한다.
move_to_end 알아보기
move_to_end 함수를 보겠습니다. 이 함수는 key를 인자로 받고 last를 키워드로 받습니다.
이 함수는, last가 참인 경우 현재 원소를 맨 뒤로, 아니라면 맨 앞으로 보냅니다. default로 True 값을 가집니다. 이게 무슨 소리인지 예제를 보겠습니다.
예제를 보면, ordereddict에 “c”, “a”, “b” 순서로 추가했습니다. 그렇다면 처음 위치부터 마지막 위치까지 “c”, “a”, “b” 순서대로 저장되어 있을 겁니다. 저는, “a”를 맨 뒤로 보내기로 했습니다. 즉, last의 위치로 보내므로, 7번째 줄을 수행한 후 아래와 같이 상태가 바뀌게 됩니다.
즉, ordereddict에는 “c”, “a”, “b” 순서가 아닌, “c”, “b”, “a” 순서로 저장되게 됩니다. 실행 결과를 보겠습니다.
“c”, “b”, “a” 순으로 나옴을 볼 수 있습니다. 반면에, last를 False로 주면 어떻게 될까요?
아까와 같이 “c”, “a”, “b” 순으로 넣었습니다. 다음에 move_to_end를 호출하는데요. last를 False로 넘겨주었습니다. 그리고 키 값은 “a”를 넘겨주었습니다. 이 경우, “a”를 맨 앞으로 보내버리게 됩니다.
따라서, 이 경우 “a”가 순서의 맨 앞으로 옮겨졌으므로 “a”, “c”, “b” 순서대로 저장되게 됩니다. 보통, lru를 이 클래스로 구현한다면, last 옵션을 주지 않습니다. 다음에 popitem을 봅시다.
popitem 알아보기
popitem은, 맨 앞, 혹은 맨 뒤에 있는 원소를 제거합니다. 링크드 리스트는 head, 혹은 tail의 위치만 알고 있으면 두 연산을 상수 복잡도로 수행할 수 있습니다.
last가 True이면 LIFO, 즉 stack의 pop처럼 수행되고, False이면 FIFO, queue의 pop처럼 수행됩니다. 이것도 그림으로 보는 편이 낫겠네요.
예제 3번을 보면, “c”, “a”, “b” 순서로 넣었습니다. 그리고, 7번째 줄을 수행합니다. last는 default로 True를 가지는데요. 이 경우, 맨 마지막에 추가된 “b”가 제거됩니다.
그러면 위 그림과 같이 그려질 겁니다. 이제, 9번째 줄에서 다시 popitem이 호출되는데요. last가 False로 되어 있습니다. 이 경우에는, 회색 노드가 아닌 맨 처음 노드인 “c”가 제거되게 됩니다.
따라서 최종적으로 요렇게 남게 됩니다. 결과를 보겠습니다.
처음에 “c”, “a”, “b” 순서대로 들어갔습니다.
- 맨 먼저 popitem이 호출되었는데, 맨 마지막에 있던 “b”가 제거되었습니다.
- 다음에 last가 False인 popitem이 호출되었기 때문에 맨 처음에 있던 “c”가 없어졌어요.
따라서, “a”만 남게 됩니다. 이 글에서 파이썬 ordereddict 클래스를 알아보았어요. dictionary와 어떤 차이가 있는지, 어떤 함수들을 추가로 제공하는지 정도만 알아도 유용하게 쓸 수 있을 거라 생각합니다. 다음에, 이를 이용해서 lru를 구현해 봅시다.