deque.popleft()는 왜 빠른가?

BFS 알고리즘을 공부하던 중, 한결 같이 python에서는 list를 이용한 풀이보다는 Collections에 있는 deque 를 사용하는 것이 빠르다고 합니다.

예전에는 저도 그냥 deque를 사용해서 풀이를 했었는데 갑자기 왜 deque가 list 보다 빠른 것인지 의문이 들었습니다.
(정확히는 deque.popleft() 가 list.pop(0) 빠른 이유에 대한 의문)

list.pop(0) vs deque.popleft()

비교를 위해서는 우선 deque가 어떤 구조로 되어 있는지부터 알아야 하겠네요.

Double-ended queue로, 큐의 앞과 뒤 모두에서 삽입 및 삭제가 가능한 큐를 의미한다. 덱은 원형 큐(Circular Queue)를 확장하면 손쉽게 구현할 수 있다.

deque

class Deque:

    rear = 0
    front = 0
    MAX_SIZE = 100
    deq = list()
    
    def __init__(self):
    	self.rear = 0
        self.front = 0
        self.deq = [0 for i in range(self.MAXSIZE)]

출처 : https://codingsmu.tistory.com/124

deque는 위와 같이 rear와 front를 가리키는 변수를 내부에 가지고 있어 해당 포인터 조정을 통해 앞과 뒤 모두에서 삽입이 가능한 구조입니다!
결과적으로 deque.popleft()는 front += 1 의 형태의 연산만을 수행하여 O(1)의 빠른 복잡도로 큐 앞에 있는 자료 삭제가 가능합니다.

반면 list의 경우에는 우리가 보통 아는 배열 구조로 가장 앞에 있는 자료를 삭제 시 (list.pop(0)) 배열에 있는 모든 데이터를 조회하여 한칸 씩 옮겨주는 작업이 필요하므로 O(n)의 시간 복잡도로 수행하게 됩니다.

그러면 무조건 deque를 쓰는 것이 좋은가?

Queue 용도로 사용할 때는 그렇습니다! Stack 등 다른 용도로 사용하는 경우에는 deque.pop() 이나 list.pop() 이나 별반 수행 시간에 차이가 없습니다. (deque.append(i), list.append(i)도 마찬가지로 큰 차이가 없음)

오히려 deque는 list처럼 index를 통한 접근(array[i])가 불가능하기 때문에 중간에 있는 값에 접근하려면 list를 사용하는 것이 훨씬 효율입니다.

용도에 맞게 사용하기 위해서는 이러한 내용을 잘 기억하고 있어야 할 것 같습니다 😀

# 추가. 실제 수행 시간 측정

start = time.time()
list.append(1)
end = time.time()
print(f"{end - start:.5f} sec")

start = time.time()
queue.append(1)
end = time.time()
print(f"{end - start:.5f} sec")

start = time.time()
queue.popleft()
end = time.time()
print(f"{end - start:.5f} sec")

start = time.time()
list.pop(0)
end = time.time()
print(f"{end - start:.5f} sec")

위와 같이 list와 deque에 대해서 각 연산의 시간을 측정해보았습니다.

데이터의 수	list.append()	queue.append()	list.pop(0)	queue.popleft()
100,000	0.0000009537 sec	0.0000026226 sec	0.0023679733 sec	0.0000021458 sec
1,000,000	0.0000021458 sec	0.0000026226 sec	0.0015821457 sec	0.0000019073 sec
10,000,000	0.0000040531 sec	0.0000090599 sec	0.0140690804 sec	0.0000116825 sec
100,000,000	0.0000247955 sec	0.0000159740 sec	0.3077902794 sec	0.0000140667 sec

확실히 list.pop(0) 연산이 다른 연산에 비해 데이터의 수에 따라 수행 시간이 영향을 받는 것을 볼 수 있습니다.
원래는 여러 번 측정해봐야 하나, 한번 밖에 측정을 안해본 자료이니 참고만 해주세요 😀