Home » 레퍼런스 » PYTHON » 파이썬 ordereddict 클래스가 dict와 어떻게 다른지 알아봅시다.

파이썬 ordereddict 클래스가 dict와 어떻게 다른지 알아봅시다.

파이썬 ordereddict 클래스는 얼핏 보면 딕셔너리와 별 차이가 없어 보입니다. 딕셔너리가 있는데 왜 이 클래스를 쓸까요? 이는, 몇 가지 추가 함수들을 제공해 주기 때문입니다. 대표적인 두 가지는 아래와 같습니다.

  • move_to_end
  • popitem
    • last keyword parameter

이 글에서는 이들에 대해 알아봅니다.


파이썬 ordereddict 간단한 구조 보기

먼저, 코드를 보면서 간단한 구조부터 파악해 봅시다.

[그림 1] __init__ 함수

__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’를 호출하면 일어나는 일입니다.

[그림 2] __setitem__ 함수

먼저, 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를 키워드로 받습니다.

[그림 3] move_to_end 설명

이 함수는, last가 참인 경우 현재 원소를 맨 뒤로, 아니라면 맨 앞으로 보냅니다. default로 True 값을 가집니다. 이게 무슨 소리인지 예제를 보겠습니다.

[그림 4] 예제 1번 프로그램

예제를 보면, ordereddict에 “c”, “a”, “b” 순서로 추가했습니다. 그렇다면 처음 위치부터 마지막 위치까지 “c”, “a”, “b” 순서대로 저장되어 있을 겁니다. 저는, “a”를 맨 뒤로 보내기로 했습니다. 즉, last의 위치로 보내므로, 7번째 줄을 수행한 후 아래와 같이 상태가 바뀌게 됩니다.

즉, ordereddict에는 “c”, “a”, “b” 순서가 아닌, “c”, “b”, “a” 순서로 저장되게 됩니다. 실행 결과를 보겠습니다.

[그림 5] 예제 1번의 실행 결과

“c”, “b”, “a” 순으로 나옴을 볼 수 있습니다. 반면에, last를 False로 주면 어떻게 될까요?

[그림 6] 예제 2번 프로그램

아까와 같이 “c”, “a”, “b” 순으로 넣었습니다. 다음에 move_to_end를 호출하는데요. last를 False로 넘겨주었습니다. 그리고 키 값은 “a”를 넘겨주었습니다. 이 경우, “a”를 맨 앞으로 보내버리게 됩니다.

[그림 7] 예제 2번의 실행 결과

따라서, 이 경우 “a”가 순서의 맨 앞으로 옮겨졌으므로 “a”, “c”, “b” 순서대로 저장되게 됩니다. 보통, lru를 이 클래스로 구현한다면, last 옵션을 주지 않습니다. 다음에 popitem을 봅시다.


popitem 알아보기

popitem은, 맨 앞, 혹은 맨 뒤에 있는 원소를 제거합니다. 링크드 리스트는 head, 혹은 tail의 위치만 알고 있으면 두 연산을 상수 복잡도로 수행할 수 있습니다.

[그림 8] popitem 함수

last가 True이면 LIFO, 즉 stack의 pop처럼 수행되고, False이면 FIFO, queue의 pop처럼 수행됩니다. 이것도 그림으로 보는 편이 낫겠네요.

[그림 9] 예제 3번 프로그램

예제 3번을 보면, “c”, “a”, “b” 순서로 넣었습니다. 그리고, 7번째 줄을 수행합니다. last는 default로 True를 가지는데요. 이 경우, 맨 마지막에 추가된 “b”가 제거됩니다.

그러면 위 그림과 같이 그려질 겁니다. 이제, 9번째 줄에서 다시 popitem이 호출되는데요. last가 False로 되어 있습니다. 이 경우에는, 회색 노드가 아닌 맨 처음 노드인 “c”가 제거되게 됩니다.

따라서 최종적으로 요렇게 남게 됩니다. 결과를 보겠습니다.

[그림 10] 예제 3번의 결과

처음에 “c”, “a”, “b” 순서대로 들어갔습니다.

  • 맨 먼저 popitem이 호출되었는데, 맨 마지막에 있던 “b”가 제거되었습니다.
  • 다음에 last가 False인 popitem이 호출되었기 때문에 맨 처음에 있던 “c”가 없어졌어요.

따라서, “a”만 남게 됩니다. 이 글에서 파이썬 ordereddict 클래스를 알아보았어요. dictionary와 어떤 차이가 있는지, 어떤 함수들을 추가로 제공하는지 정도만 알아도 유용하게 쓸 수 있을 거라 생각합니다. 다음에, 이를 이용해서 lru를 구현해 봅시다.

Leave a Comment

4 × 1 =