[Python] dequeue 연산의 시간 복잡도 비교 (list vs collections.deque)

냥린이·2022년 1월 26일
0

파이썬

목록 보기
2/2

python은 리스트라는 아주 강력한 동적 배열 자료 구조가 있어서 스택를 모두 구현할 수 있다.

하지만 파이썬은 deque 라는 자료구조가 별도로 존재하며,

를 구현할 때 사실상 리스트 보다는 deque 를 더 많이 사용한다.

의 가장 큰 특징인 첫번째 원소 반환 에서 시간 복잡도 차이가 나기 때문이다.

리스트의 주요 연산 시간 복잡도

연산시간 복잡도
len(list)O(1)
list[i]O(1)
list[i:j]O(k)
a in listO(n)
list.count(elem)O(n)
list.index(elem)O(n)
list.append(elem)O(1)
list.pop()O(1)
list.pop(0)O(n)
del list[i]O(n)
list.sort()O(n log n)
min(list), max(list)O(n)
list.reverse()O(n)

리스트의 인덱스 접근은 O(1)의 속도를 가진다.

연산의 경우 인덱스 위치에 따라 차이가 나는데, 마지막 원소 반환은 O(1) 의 시간이 걸리는 반면 첫번째 원소 반환은 O(n) 의 시간이 걸린다.

첫번째 원소로 접근하는 건 O(1) 밖에 안 걸리지만 남은 원소들을 복사해주어야 하므로 결국 O(n)이 된다.

따라서 리스트는 LIFO인 스택의 연산 처리에는 적합하지만, FIFO인 큐 연산에는 불리하다.

어떻게 Python collections.deque의 pop는 O(1)이 가능한가?

리스트와 다르게 collections 라이브러리에서 제공하는 deque는 첫번째 원소를 반환하는 dequeue 연산을 O(1) 만에 처리할 수 있다. 왜 그럴까?

cpython: 2cb530243943 Modules/_collectionsmodule.c

collections 모듈 코드를 살펴보면, deque는 블럭 단위로 연결된 링크드 리스트 형태임을 알 수 있다.

typedef struct BLOCK {
    struct BLOCK *leftlink;
    PyObject *data[BLOCKLEN];
    struct BLOCK *rightlink;
} block;

typedef struct {
    PyObject_VAR_HEAD
    block *leftblock;
    block *rightblock;
    Py_ssize_t leftindex;       /* 0 <= leftindex < BLOCKLEN */
    Py_ssize_t rightindex;      /* 0 <= rightindex < BLOCKLEN */
    size_t state;               /* incremented whenever the indices move */
    Py_ssize_t maxlen;
    PyObject *weakreflist;
} dequeobject;

static PyTypeObject deque_type;

블럭을 앞 뒤로 잇는 leftlink와 rightlink가 블록 구조체에 정의되어 있다.

이러한 블록이 모여서 dequeobject를 만들며, dequeobject는 전체 오브젝트의 양 끝을 leftindex, rightindex에 따로 저장하고 있다.

첫번째 원소를 날려버리는 dequeue 연산 시, 첫번째 블록을 끊어버리고, 연결 노드 인덱스만 갱신하면 되기 때문에 dequeue 연산이 O(1) 만에 가능한 것이다.

이렇게 양끝을 저장하는 구조인 deque의 full name은 double-ended queue 이다.

다만, 연결리스트로 구현되었기 때문에 특정 인덱스로의 임의 접근은 O(n)이 걸린다. O(1) 번에 가능한 리스트와의 대척점에 있기 때문에 자료구조 선택 이전에 문제 정의가 중요하다.

임의 접근보다 dequeue 연산을 자주 수행해야 한다면 리스트보다는 deque가 좋은 선택지이다.

profile
홀로서기 기록장

0개의 댓글