[Python] Collections - deque

Python Collections

• List, Tuple, Dict에 대한 Python Built-in 확장 자료 구조(모듈)
• 편의성, 실행 효율 등을 사용자에게 제공함
• 다음과 같은 모듈이 존재한다.

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

 

Deque

• Stack과 Queue를 지원하는 모듈
• List에 비해 효율적인 자료 저장방식을 지원함
• collections로 부터 import하여 사용

from collections import deque

 

deque의 append()

deque의 appendleft()

deque의 pop()

 

deque의 popleft()

기본적으로 list의 앞, 뒤에 데이터를 추가하고 삭제하는 기능을 제공하므로 Queue나 Stack의 구현에 용이하다.

 

• rotate, reverse 등 Linked List의 특성을 지원한다.
• 또한 기존 List 형태의 함수를 모두 지원한다.

deque의 rotate

rotate()는 정수를 입력을 받아서 요소들의 순서를 회전시켜주는 함수이다.

양수 입력의 경우 시계 방향 ( 마지막 요소가 처음에 삽입되도록 회전 ) 회전

음수 입력의 경우 시계 반대 방향 ( 첫 번째 요소가 마지막에 삽입이 되도록 회전) 회전

 

deque의 reversed

reversed()에 deque를 입력으로 주게 되면 기존 deque의 요소들의 순서가 반전된 deque가 반환된다.

기존의 deque의 순서가 바뀌게 되는 것은 아니다.

deque_list의 extend, extendleft

deque의 extend()는 리스트를 입력받아 기존의 deque에 추가하는 함수이다.

extendeft()는 deque의 새 리스트를 기존의 deque의 앞 부분에 추가한다.

이 때 삽입 순서에 주의하자

 

deque_list.extendleft([-3,-2,-1])

위의 코드를 실행 하였을 때 deque의 요소에

[ -3, -2, -1, 0, 1 ...] 처럼 삽입될 거라 생각할 수 있지만 통째로 추가하는 것이 아니라

입력으로 준 리스트를 하나 씩 삽입하기 때문에

[-1, -2, -3, 0, 1 ...] 과 같은 결과가 나오게 된다.

 

---

 

마지막으로 기존의 List와 deque의 속도를 비교해보자.

 

각각 10000x10000 개의 데이터를 append 하고 pop하는 예제이다.

 

deque

from collections import deque
import time

start_time = time.clock()
deque_list = deque()

for i in range(10000):
    for j in range(10000):
        deque_list.append(i)
        deque_list.pop()

print(time.clock() - start_time, "seconds")

실행결과

 

list

import time

start_time = time.clock()
just_list = []

for i in range(10000):
    for j in range(10000):
        just_list.append(i)
        just_list.pop()

print(time.clock() - start_time, "seconds")

실행결과

 

deque가 약 18초, list가 약 43초로 두 배 이상의 성능차이를 보인다.

---

 

deque는 기존 list 보다 효율적인 자료구조를 제공하여 처리 속도를 향상 시킨 자료구조이다.

큰 데이터를 다룰 때는 특히 이렇게 효율적인 자료구조를 사용하는 것이 중요하다고 생각한다.