[Python] Stack, 스택
❓ deque가 구체적으로 어떻게 list 보다 연산을 빠르게 한다는거지?? 똑같은 append 연산인데도 deque로 구현했을 때 연산이 빠르게 진행된다는 건가?
list와 deque의 연산 성능 비교
당연~하게도 나와 같은 질문을 한 사람이 있었다. 아래 stackoverflow 포스팅을 참고하였다.
python docs 사이트를 보면, Deque에 대해 아래와 같이 설명하고 있다.
Deques support thread-safe, memory efficient appends and pops from eiher side of the deque with approximately the same O(1) performance in either direction.
Though list objects support similar operations, they are optimized for fast fixed-length operations and incur O(n) memory movement costs for pop(0) and insert(0, v) operations which change both the size and position of the underlying data representation.
그렇구나.. 그래서 실질적으로 어떤 면에서 성능적으로 차이가 있다는 거냐?
-
Deque는 appendleft()와 popleft() 연산 시 O(1) 속도를 보이는 반면,
list는 insert(0, value) 와 pop(0) 연산 시 O(n) 속도를 보인다. -
List append performance is hit and miss because it uses realloc() under the hood. As a result, it tends to have over-optimistic timings in simple code (because the realloc doesn't have to move data) and really slow timings in real code (because fragmentation forces realloc to move all the data). In contrast, deque append performance is consistent because it never reallocs and never moves data.
두 번째 문장은,, 좀 더 천천히 이해해보도록 하고,, 😂 일단 성능 비교 테스트 결과를 보자!
In [1]: from collections import deque
In [2]: s = list(range(1000))
In [3]: d = deque(s)
In [4]: s_append, s_pop = s.append, s.pop
In [5]: d_append, d_pop = d.append, d.pop
In [6]: %timeit s_pop(); s_append(None)
10000000 loops, best of 3: 115 ns per loop
In [7]: %timeit d_pop(); d_append(None)
10000000 loops, best of 3: 70.5 ns per loop결과를 보면,
- list 에서 pop 연산 및 append 연산을 수행하는 데 걸린 시간이 대략 115초
- deque 에서 pop 연산 및 append 연산을 수행하는 데 걸린 시간이 대략 70.5초
기본적인 pop 연산과 append 연산 시에도 deque가 속도가 빠르다는 것 같은데,,
그렇지만 Deque의 시간 복잡도가 O(1)가 나오는 건 appendleft()와 popleft()이기 때문에 !
Deque를 사용할 시에는 append(), pop() 연산이 아니라
appendleft(), popleft() 연산을 사용하는게 적합한 것이..겠죠..?
그럼 다시 원래 문제로 돌아가서.. 시간초과가 발생한 백준 스택 문제를 deque와 deque의 appendleft(), popleft()를 사용하여 풀어보고 오도록 하겠다.
