파이썬 deque 사용하는 이유 / popleft

 

파이썬 deque는 list와 dictionary와 거의 동일하게 생각하면 된다.

 

차이는 popleft의 시간 차이다.

 

list의 경우 pop()으로 마지막 값을 꺼내는 경우 O(1) (일정한 시간) 시간이 걸리는데, pop(0)으로 가장 앞단에 값을 꺼낼때는 list 크기에 따라 읽어 오는 시간이 달라진다. O(n) 시간이 걸린다.

 

하지만 deque를 사용할 경우 popleft()를 사용하면 리스트의 pop(0)과 같은 기능을 주면서 걸리는 시간은 O(1)이 걸린다.

 

pop을 사용하는 경우 말고 index로 값을 읽어 오는 경우는 리스트나 deque 모두 O(1)로 일정한 시간만 걸린다. 즉, index의 주소 값으로 바로 값을 찾는 것이다.

 

아래 코드는 각 상황에 따라 시간을 측정한 값이다. 0.001 시간 이하는 O(1) 시간이 걸린것으로 생각하면 되고 거의 동일하다고 보면 된다.

 

코드 >>

 

from collections import deque
import time


a_var = deque([x for x in range(10000000)])
cur_time0 = time.time()
print(a_var.popleft())
print(time.time()-cur_time0)


b_var = deque([x for x in range(10000000)])
cur_time1 = time.time()
print(b_var[0])
print(time.time()-cur_time1)


c_var = [x for x in range(10000000)]
cur_time2 = time.time()
print(c_var[0])
print(time.time()-cur_time2)

d_var = [x for x in range(10000000)]
cur_time3 = time.time()
print(d_var.pop(0))
print(time.time()-cur_time3)

 

결과 >>

0
0.0009970664978027344
0
0.0
0
0.0009970664978027344
0
0.013949394226074219