[Python] Collections (deque, OrderedDict, defaultdict, Counter)

Collections은 자료구조에 대한 기본 모듈을 포함하고 있다.

from collections import deque
from collections import OrderedDict
from collections import defaultdict
from collections import Counter

1. deque

효율적 메모리 구조로 기존 list보다 처리 속도가 빠르다.

Deque는 Double-ended Queue이다.

Double-ended는 양 끝에 elements를 추가/삭제를 지원한다는 의미이다.

사진 출처: https://dev.to/v_it_aly/python-deque-vs-listwh-25i9

내부적으로 deque는 double-lined list로 구현되어 있다. 그래서 양 끝의 요소의 추가/삭제가 O(1)을 만족한다.

 

덱과 다르게 python의 리스트는 fixed size memory blocks(array)로 구현되어 있다.

이름은 List여서 링크드 리스트처럼 보이지만 고정된 사이즈의 메모리를 갖는 array형태이다.

 

리스트의 마지막 원소를 삭제하는 경우에 대한 시간복잡도는 O(1)이지만, 아래 그림처럼 첫번째 원소를 삭제하는 경우 삭제 후 모든 원소를 앞으로 이동시키기 때문에 시간 복잡도가 O(n)이다.

이미지 출처: https://wellsw.tistory.com/122

자료구조 뒤에서 추가/삭제는 덱과 리스트의 속도차이가 없지만, 첫번째 원소를 추가/삭제 한다면 극명한 속도 차이가 발생한다.

appendleft()

deque의 left end에 요소를 추가한다.

평균적인 시간복잡도는 O(1)이다. O(n)의 시간복잡도를 가지는 list의 insert()함수보다 훨씬 빠르다.

append()

deque의 right end에 요소를 추가한다.

pop()

deque의 right end의 요소를 삭제한다.

popleft()

deque의 left end의 요소를 삭제한다.

from collections import deque

deque_list = deque()
for i in range(5):
    deque_list.append(i)
print(deque_list)
# deque([0, 1, 2, 3, 4])

deque_list.appendleft(10)
print(deque_list)
# deque([10, 0, 1, 2, 3, 4])

deque_list.pop()
print(deque_list)
# deque([10, 0, 1, 2, 3])

deque_list.popleft()
print(deque_list)
# deque([0, 1, 2, 3])

 

rotate()

deque를 오른쪽으로 돌린다.

[10, 0, 1, 2, 3, 4]를 한번 rotate하면 [4, 10, 0, 1, 2, 3]이 되고

두 번 rotate하면 아래와 같은 결과가 나온다.

deque_list = [10, 0, 1, 2, 3, 4]
deque_list.rotate(2)
print(deque_list)
# deque([3, 4, 10, 0, 1, 2])

reversed()

deque안의 element위치를 반대로 한다.

deque_list = [4, 3, 10, 0, 1, 2]
print(deque(reversed(deque_list)))
#deque([2, 1, 0, 10, 3, 4])

2. OrderedDict

사전순으로 반환하는 dict와 달리, 데이터를 입력한 순서대로 dict를 반환한다. 

from collections import OrderedDict

d = {}
d['x'] = 100
d['y'] = 200
d['z'] = 300
d['l'] = 500

for k, v in d.items():
    print(k, v)

#x 100
#y 200
#z 300
#l 500​

 

dict type의 값을 value 또는 key값으로 정렬할 때 유용하다.

for k, v in OrderedDict(sorted(d.items(), key=lambda t: t[0])).items():
    print(k, v)
#l 500
#x 100
#y 200
#z 300


for k, v in OrderedDict(sorted(d.items(), key=lambda t: t[1])).items():
    print(k, v)
#x 100
#y 200
#z 300
#l 500

3. defaultdict

dict type의 값에 기본 값을 지정해준다. 신규값 생성시 사용하는 방법이다.

 

다음과 같이 작성하고 실행하면 KeyError가 발생한다. "first"라는 key값이 존재하지 않기 때문이다.

d=dict()
print(d["first"])​

 

하지만 defaultdict를 사용하면 "first"라는 key값이 존재하지 않지만 화면에 1을 출력해준다.

from collections import defaultdict
int_d = defaultdict(int)     # Default dictionary를 생성
print(int_d["first"]) # 0

d = defaultdict(lambda: 1)  # Default 값을 1으로 설정합
print(d["first"]) # 1

4. Counter

Sequence type의 data element들의 갯수를 dict형태로 반환해준다.

갯수가 큰 순으로 나타난다.

알고리즘 문제 예시로는 "가장 많이 등장하는 알파벳 찾기"가 있다.

시간복잡도는 O(N)이다.

from collections import Counter

c = Counter()                           # a new, empty counter
c = Counter('gallahad')                 # a new counter from an iterable
print(c)

#Counter({'a': 3, 'l': 2, 'g': 1, 'd': 1, 'h': 1})​

elements 메소드: 카운터 숫자만큼 요소 반환

cnt = Counter(a=5, b=3)
print(cnt) # Counter({'a': 5, 'b': 3})

print(list(cnt.elements())) # ['a, 'a', 'a', 'a', 'a', 'b', 'b', 'b']

print(list(cnt)) # ['a', 'b']

 

산술 연산자를 사용할 수 있다.

counter1 = Counter(["A", "A", "B"])
counter2 = Counter(["A", "B", "B"])

print(counter1 + counter2) # Counter({'A': 3, 'B': 3})
print(counter1 - counter2) # Counter({'A': 1})
print(counter1 & counter2) # Counter({'A': 1, 'B': 1})
print(counter1 | counter2) # Counter({'A': 2, 'B': 2})

 

missing item에 대해서 KeyError를 raise하는 대신 0을 return 한다.

c = Counter(['eggs', 'ham'])
c['bacon']                              # count of a missing element is zero

 

Reference:
부스트코스, 머신러닝을 위한 파이썬
프로그래머스, 파이썬을 파이썬답게
[파이썬 기초] Counter를 이용한 항목 계산,

[파이썬] 덱 vs 리스트 속도 차이? (deque vs list speed 차이)

파이썬 공식 문서 collections.Counter