[파이썬] 덱 vs 리스트 속도 차이? (deque vs list speed 차이)

덱과 리스트?

여러분은 어떤 차이를 두고 두 자료구조를 적절하게 사용하시나요?

둘 다 사용상에는 큰 차이가 없어 보입니다.

그렇지만, 이 자료구조를 어떤 상황에서 어떻게 사용하느냐에 따라서 굉장히 큰 속도 차이가 발생합니다.

 

덱과 리스트의 시간 복잡도를 비교한 테이블입니다.

	Deque	List
Time Complexity

deque에는 appendleft() 함수와 popleft() 함수가 있습니다. 평균적인 시간복잡도는 O(1)입니다.

List는 insert() 함수가 있는데 O(n)의 시간 복잡도입니다. 

왜 이런 시간 차이가 발생할까요???

 

Deque

덱은 어떤 형식으로 자료의 형태를 유지할까요?

이름은 뭔가 큐와 비슷해보입니다. FIFO 형식을 유지할 것 같습니다.

 

Deque은

A Double-ended Queue

 

Double-ended는 양 끝에 elements를 추가/삭제를 지원한다는 의미입니다.

Deque - 출처 : https://dev.to/v_it_aly/python-deque-vs-listwh-25i9

내부적으로 deque은 double-linked list로 구현되어 있습니다.

그래서 양 끝의 요소의 추가/삭제가 O(1)을 만족하게됩니다.

 

주요 함수:

• append() : deque의 right end에 요소 추가
• appendleft() :  deque의 lef end에 요소 추가
• pop() : deque의 right end의 요소 삭제
• popleft() : deque의 left end의 요소 삭제

 

 

List

덱과는 다르게 python의 리스트는 fixed size memory blocks(array)로 구현되어 있습니다.

이름은 List여서 링크드 리스트처럼 보이지만 고정된 사이즈의 메모리를 갖는 array 형태입니다.

 

리스트의 마지막 원소를 삭제는 O(1)이지만, 아래 그림처럼 첫번째 원소를 삭제하면 삭제 후 모든 원소를 앞으로 이동시키기 때문에 시간 복잡도가 O(n)입니다. 

 

자료구조 뒤에서 추가/삭제는 덱과 리스트는 속도 차이가 없지만, 첫번째 원소를 추가 삭제한다면 극명한 속도 차이가 발생합니다.

 

천만개의 요소를 삽입하고 1000개의 요소를 삭제하는 코드를 list vs deque 비교 코드 입니다.

 

list vs deque:

import time
from collections import deque


def insert_and_pop(container, desc):
    arr = range(10000000)

    start = time.time()
    for n in arr:
        container.append(arr)
    print(f'{desc}, 삽입 수행 시간, {time.time() - start} 초')

    start = time.time()
    for i in range(1000):
        if type(container) is list:
            container.pop(0)
        else:
            container.popleft()
    print(f'{desc}, pop(0) 수행 시간, {time.time() - start} 초')



l = list()
d = deque()

insert_and_pop(l, 'list')
print()
insert_and_pop(d, 'deque')

수행 결과

list, 삽입 수행 시간, 0.5615091323852539 초
list, pop(0) 수행 시간, 4.844250679016113 초

deque, 삽입 수행 시간, 0.43166375160217285 초
deque, pop(0) 수행 시간, 0.0 초

1000개 요소를 삭제하는데 list는 4.8초가 걸리지만 덱은 0초에 가깝습니다.

 

삽입, 삭제의 operation()이 앞, 뒤, 중간 등에서 발생한다면 list 보다는 deque 사용을 우선적으로 고려하는 것이 속도 측면에서는 훨씬 좋을 것입니다.