공부하면서 알아간 내용을 정리한 글입니다.
틀린 내용이 있을 수 있으니 알려주신다면 감사히 수정하겠습니다 ^^
알고리즘 문제를 풀면 데크 자료구조를 사용할 일이 많다.
데크는 doubly-ended-queue의 약자로 왼쪽 끝과 오른쪽 끝에 pop, append 연산을 O(1)에 수행할 수 있는 자료구조이고, 이름에서 알 수 있듯이 이중 연결 리스트이다.
보통 이중 연결 리스트는 노드 객체를 하나씩 prev, next로 서로 연결해서 구현한다.
따라서 인덱스로 접근할 수 없고 앞에서부터 순차적으로 접근해야 하고, 접근하는데 O(N)의 시간 복잡도가 걸린다.
그리고 데이터 하나당 링크를 2개 사용하기 때문에 메모리를 2배로 사용한다.
대신 노드 사이의 삽입과 삭제연산이 시간 복잡도가 O(1)인 장점이 있다.
하지만 파이썬의 collections 모듈을 가져와 deque를 실제로 사용해 보면 [ i ] 접근 연산자를 사용해 마치 리스트처럼 인덱스 접근을 할 수 있다.
나는 이 인덱스 접근의 시간 복잡도가 리스트와 같이 O(1)인지 아니면 이중 연결 리스트의 O(N)인지 궁금해졌고, 이를 알기 위해 파이썬에서 deque를 어떻게 구현했는지 보려고 cpython 코드를 찾아봤다.
cpython의 deque 구현 코드 링크
https://hg.python.org/cpython/file/3.5/Modules/_collectionsmodule.c#l21
파이썬은 내부가 c언어로 구현되어 있고, 오픈 소스 프로젝트이므로 깃허브에 코드가 올라가있다.
데크를 어떻게 구현하는지 대략적인 방법을 주석으로 달아놨는데, 주석 내용을 읽어보면 답을 알 수 있을 것이다.
블락의 길이는 1보다 큰 수로 설정한다. 더 큰 숫자로 설정할수록 블락 메모리 할당 횟수가 줄어들고, 인덱싱과 회전이 더 빨라진다.
그리고 데이터에 대한 링크의 오버헤드 비율이 줄어든다. 블락의 길이를 2의 거듭제곱으로 만들면 모듈로 연산과 나누기 연산의 속도가 빨라진다.
블락 길이 상수를 64로 지정하고, 블락의 중앙 인덱스를 31로 지정한다.
고정된 크기의 블락들을 이중으로 연결한 리스트에 데이터를 집어넣는다.
이것은 (리스트처럼) 추가, 삭제되는 데이터 주변의 데이터가 이동하는 일이 일어나지 않게 해준다.
또다른 이점은 블락을 연결함으로써 (동적배열처럼) realloc 연산을 사용하지 않아도 되게 된다는 점이다. 이것은 작업을 더 예측 가능하게 해준다.
교과서에서는 이중 연결 리스트를 데이터 하나씩 연결해서 구현한다. 이방법은 데이터가 차지하는 메모리의 2배가 오버헤드로 발생한다. (prev, next 링크로 연결하므로) 그리고 데이터 하나당 malloc 연산을 실행해야 한다. 이는 비효율적이다.
하지만 블락 단위로 연결하면 데이터당 링크 연결 비용이 상당히 많이 줄어들고 malloc, free 연산 (메모리 할당, 해제 연산)을 사용하는 비율이 낮아진다.
(데이터 하나씩 연결하던 것을 데이터 블락 단위로 연결하므로, 블락 크기가 64라면 대략 1/64 배로 줄어든다.)
또한 연속적인 포인터가 들어있는 데이터 블록들이 캐시 접근성을 높여준다.
여기까지 주석을 읽은 결과,
파이썬의 데크는 데이터를 하나씩 연결한게 아니라 데이터를 묶은 블락 단위로 연결한 이중 연결 리스트임을 알 수 있다.
C언어로 구현한 블락의 구조를 보면
왼쪽과 오른쪽 블락을 가리키는 포인터 leftlink, rightlink가 있고, 블락의 크기만큼 데이터를 담을 data 배열이 있다.
dequeobject는 leftblock, rightblock을 가리키는 포인터 2개, 왼쪽 끝, 오른쪽 끝을 가리키는 leftindex, rightindex를 가진다.
주석들을 읽어본 결과 파이썬에서 c로 구현한 데크는 데이터를 64개 담은 블락들을 이중 연결해서 만든 자료구조임을 알 수 있다.
본질적으로는 이중 연결 리스트이므로 인덱스 접근이 가능하다 하더라도 시간복잡도가 리스트처럼 O(1)이 아닌 O(N)이 다.
예를 들어 1000개의 데이터가 저장된 데크에서 500번째 데이터에 접근하려면 블락단위로 이동해서 (500 / 64) 번, 대강 7번에서 8번 블락을 이동해서 접근하는 것이다.
따라서 인덱스 접근 연산의 시간복잡도는 O(N / BLOCK_LEN), 결과적으로 O(N)이 된다.
파이썬 공식 문서를 읽어보면 이를 설명하는 내용을 찾을 수 있다.
링크 : https://docs.python.org/3/library/collections.html#deque-objects
마지막 문장을 읽어보면
인덱스 접근은 양 끝에서 O(1), 하지만 중간 데이터에 접근한다면 O(N)으로 느려진다. 빠른 인덱스 접근을 원한다면, 리스트를 사용하라.
이는 cpython 주석에서 알아본 내용과 같다.
C++의 STL에도 파이썬의 데크와 연결리스트에 관련한 자료구조가 있다.
C++ STL에는 deque와 list 가 있는데, deque는 파이썬의 deque와 같이 데이터 블락단위로 연결한 자료구조고, list는 데이터를 하나씩 연결한 이중 연결 리스트다.
이 내용을 표로 잘 정리한 블로그가 있어 링크를 걸어두겠다.
https://blog.naver.com/yoochansong/221739086178
