상세 컨텐츠

본문 제목

[PYTHON] 파이썬 collections 모듈(3) deque

PYTHON/기본

by ranlan 2021. 10. 30. 22:42

본문

728x90

[공식문서] https://docs.python.org/3/library/collections.html#collections.deque

 

collections — Container datatypes — Python 3.10.0 documentation

collections — Container datatypes Source code: Lib/collections/__init__.py This module implements specialized container datatypes providing alternatives to Python’s general purpose built-in containers, dict, list, set, and tuple. namedtuple() factory f

docs.python.org

 

 

deque란

from collections import deque

Double-Ended Queue의 줄임말로, 양방향 데이터 처리가 가능한 Queue 자료형

 

https://www.geeksforgeeks.org/implementation-deque-using-circular-array/

 

 

dequeue.메서드()

list = ['a', 'b', 'c']
Q = deque(['A', 'B', 'C'])

append(): 오른쪽(마지막)에 삽입

list.append('d') # ['a', 'b', 'c', 'd']
Q.append('D') # ['A', 'B', 'C', 'D']

appendleft(): 왼쪽(앞)에 삽입

Q.appendleft('X') # ['X', 'A', 'B', 'C', 'D']

extend(iterable): 리스트나 문자열 등 iterable 객체 오른쪽(마지막)에 삽입

list.extend('ef')  # ['a', 'b', 'c', 'd', 'e', 'f']
Q.extend('EF') # ['X', 'A', 'B', 'C', 'D', 'E', 'F']

## append와 비교
list.append('ef')  # ['a', 'b', 'c', 'd', 'ef']

extendleft(iterable): 리스트나 문자열 등 iterable 객체 왼쪽(앞)에 삽입

Q.extendleft('YZ') # ['Z', 'Y', 'X', 'A', 'B', 'C', 'D', 'E', 'F']

pop(): 오른쪽(마지막)부터 하나씩 요소 제거 후 반환

# pop
lst = ['a', 'b', 'c']
while True:
    try:
        print(lst.pop(), end=' ') # c b a
    except IndexError:
        break

q = deque(['A', 'B', 'C'])
while True:
    try:
        print(q.pop(), end=' ') # C B A
    except IndexError:
        break

popleft(): 왼쪽(앞)부터 하나씩 요소 제거 후 반환

q = deque(['A', 'B', 'C'])
while True:
    try:
        print(q.popleft(), end=' ') # A B C
    except IndexError:
        break

rotate(n): n만큼 회전, 양수일 때는 오른쪽으로 음수일 경우 왼쪽으로 회전

deq = deque(['a', 'b', 'c', 'd', 'e'])

deq.rotate(1) # e a b c d
deq.rotate(2) # d e a b c
deq.rotate(-1) # b c d e a
deq.rotate(-2) # c d e a b

 

 

deque.popleft와 list.pop(0) 시간복잡도

[stackoverflow] https://stackoverflow.com/questions/32543608/deque-popleft-and-list-pop0-is-there-performance-difference

 

deque.popleft() and list.pop(0). Is there performance difference?

deque.popleft() and list.pop(0) seem to return the same result. Is there any performance difference between them and why?

stackoverflow.com

deque.popleft() is faster than list.pop(0)
because the deque has been optimized to do popleft() approximately in O(1),
while list.pop(0) takes O(n) (see deque objects).

 deque.popleft() 의 시간복잡도는  O(1) 이고  list.pop(0) 는  O(n) 으로, deque.popleft()가 성능이 더 좋다.

CPython list implementation is array-based.
list.pop(0) removes the first item from the list and it requires to shift left len(lst) - 1 items to fill the gap.
deque() implementation uses a doubly linked list. No matter how large the deque, deque.popleft() requires a constant (limited above) number of operations.

리스트의 경우 가장 맨 앞의 요소 제거 후 앞으로 요소들을 n-1번 당겨야하기 때문에 O(n) 소요, deque의 경우 이중연결리스트로 구현되어있어 문제 없음

728x90

관련글 더보기

댓글 영역