[공식문서] 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
from collections import deque
Double-Ended Queue의 줄임말로, 양방향 데이터 처리가 가능한 Queue 자료형
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
[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의 경우 이중연결리스트로 구현되어있어 문제 없음
[PYTHON] 파이썬 collections 모듈(2) Counter (0) | 2021.10.30 |
---|---|
[PYTHON] 파이썬 collections 모듈(1) defaultdict (0) | 2021.10.30 |
[DJANGO] 파이썬의 list 자바스크립트에서 array로 받기 (0) | 2021.08.12 |
[PYTHON] pickle(.pkl) 데이터 저장 및 불러오기 (0) | 2021.07.16 |
[PYTHON] smtplib 이용한 간단한 Gmail 발송 (0) | 2021.06.28 |
댓글 영역