[파이썬/python] collections 모듈, deque, Counter, defaultdict

파이썬의 collections에서는 큐, 스택, 사전 등의 자료구조와 관련된 모듈들을 제공한다. deque, Counter, defaultdict 외에도 OderedDict, namedtuple 등도 있지만 유용해보이는 앞의 세 개만 간단히 정리해본다.

(OderedDict은 파이썬 3.6에서 dictionary가 순서를 보장하도록 업데이트 되면서 필요가 적어졌고, namedtuple은 보통 클래스로 구현해 사용성이 떨어진다고 한다.)

 

1) deque

큐, 스택의 구현을 위해 정말 빈번하게 사용되는 모듈이다. 파이썬의 기본 list로도 두 자료구조를 모두 구현할 수 있긴하지만, deque가 훨씬 더 빠른 계산 효율을 보여주기도 하고 원형 큐 등의 자료구조들까지도 구현할 수 있어 사용성이 좋다. 이것이 가능한 것은 deque의 경우 내부적으로 linked list로 구현되었기 때문이다.

(linked list 관련 글: https://mingchin.tistory.com/127)

 

%%timeit은 주피터노트북에서 해당 셀에 대한 실행을 여러 번 반복했을 때 평균적으로 걸리는 시간을 계산해주는 매직 명령어이다. 이를 통해 deque()와 일반 리스트에 원소를 넣다 빼는 행위의 걸리는 시간을 비교해보면 아래와 같다.

일반 리스트가 제공하는 append, pop, extend를 포함한 attrubure 뿐만 아니라 appendleft, popleft, extendleft 등도 제공한다. 추가로 rotate이라는 것을 지원하는데 아래와 같이 작동한다.

deque().rotate(n)은 deque를 양수면 오른쪽으로, 음수면 왼쪽으로 n칸 회전시킨다. 0번째 index를 기준으로 원형으로 생각하면 '오른쪽 = 시계방향, 왼쪽 = 반시계방향'으로 생각할 수 있다.

 

extendleft()의 경우 다음과 같이 작동하는데, 왼쪽에 붙일 때는 입력한 순서의 반대로 붙는 것을 알 수 있다. 이는 stack자료 구조의 LIFO, queue 자료 구조의 FIFO이 제대로 작동할 수 있도록 한다.

(stack, queue 관련 글: https://mingchin.tistory.com/112)

 

2) Counter

iterator 객체를 넣어주었을 때, 객체가 포함하는 인자들의 갯수들을 세어주는 모듈이다.

이런 식으로 정의할 수 있다. 사전화된 Counter 객체를 다시 원래 iterator 객체의 구성으로 되돌릴 수 있다. (순서는 보장되지 않는다.)

또한 set의 교집합, 합집합, 차집합 연산도 같은 원리로 제공한다.

3) defaultdict

이 역시 dict.get()을 적절하게 활용하면 없이 해결할 수 있긴 하지만, dict에 존재하지 않을 수 있는 값에 대해 int(0), list([]), set({}) 등의 빈 값들을 적절하게 default로 지정할 수 있다는 장점이 있는 자료구조다.

이렇게 지정하지 않은 값에 대한 호출을 하면, error를 반환하는 것이 아니라 지정한 default 값을 반환한다. int를 지정하면 0, list를 지정하면 [], set을 지정하면 {}이 default로 정해진다. 아래는 같은 기능을 할 수 있는 get을 활용한 코드다.

 

추가로 0, [], {}외에 특정 값을 지정하고 싶다면, 함수 형태를 사용하면 된다.