[알고리즘] 덱 (deque)

덱은 double-ended queue를 줄인것이다. 이름에서 알 수 있듯이 양쪽으로 넣고 뺄 수 있는 큐를 의미한다. 기초 자료구조이지만 여기에 숨어있는 신기한 사실이 있다.
 

시간복잡도

덱의 장점은 앞, 뒤 어디서든지 삽입삭제가 $O(1)$이라는 것이다. 보통 학부 과정에서 덱을 구현하라는 과제를 받으면 리스트로 구현하여 삽입삭제를 $O(1)$로 끝내고 random access를 $O(N)$에 동작하도록 구현하게 된다. 하지만 실제로 내장된 deque를 사용해보면 어떨까?

# python
from collections import deque
import time
N = 1000000
arr = [i for i in range(N)]
s = 0
start = time.time()
for i in range(N):
    s += arr[i]
print("vector", time.time() - start, s)

q = deque([i for i in range(N)])
s = 0
start = time.time()
for i in range(N):
    s += q[i]
print("deque", time.time() - start, s)

// cpp
#include <bits/stdc++.h>
using namespace std;

int main()
{
    long long n = 1000000;
    [=]()
    {
        vector<int> arr(n);
        for (int i = 0; i < n; i++)
        {
            arr[i] = i;
        }
        chrono::system_clock::time_point start = chrono::system_clock::now();

        long long s = 0;
        for (int i = 0; i < n; i++)
            s += arr[i];

        chrono::duration<double> duration = chrono::system_clock::now() - start;
        cout << "vector " << duration.count() << " seconds, result: " << s << endl;
    }();

    [=]()
    {
        deque<int> dq;
        for (int i = 0; i < n; i++)
        {
            dq.push_back(i);
        }
        chrono::system_clock::time_point start = chrono::system_clock::now();

        long long s = 0;
        for (int i = 0; i < n; i++)
            s += dq[i];

        chrono::duration<double> duration = chrono::system_clock::now() - start;
        cout << "deque " << duration.count() << " seconds, result: " << s << endl;
    }();
}

파이썬과 C++로 비교하며 실험해보았다. (C++는 변수 공유를 막기 위해 람다로 감쌌다.) 100만개의 데이터가 들어있으므로 덱에서 합을 구하는 코드는 $O(N^2)$으로 굉장히 오래걸려야 한다. 

python

c++

c++는 $O(N^2)$이라기엔 굉장히 빠른 속도를 기록했고 파이썬도 $10^{12}$번 계산했다기엔 빠른 기록이었다. 즉 내장 라이브러리에 있는 deque는 random access도 상당히 빠른 것을 알 수 있다. 어떻게 이게 가능할까?
 

Chunk

인터넷에 deque의 구현을 찾아보면 chunk라는 개념이 나온다. 덱이 하나의 리스트나 벡터처럼 구현되어있어 앞뒤로 삽입 삭제하는 것이 아니라 chunk단위로 나눠져 저장되는 것이다.

 
대충 그림으로 보면 이런 느낌이다. 비트집합과 유사하다. 만약 chunk 3이 가득 찬 상태에서 데이터를 뒤로 삽입한다면? chunk 4를 생성한 뒤 그곳에 넣으면 된다. 앞으로 삽입도 마찬가지로 chunk 0을 생성한 뒤 넣으면 된다. 
 
각각의 chunk는 고정 길이 배열로 두고 위와 같은 경우는 5번째 데이터에 접근할 때 2번 chunk로  들어가서 2번째 데이터를 불러오면 된다. 그렇다면 chunk개수는 계속 변하는데 5번째 데이터가 2번 chunk에 있다는 건 어떻게 알까?
 

$k$ 번째 값 구하기

random access를 하기 위해 필요한 정보는 다음과 같다.

• chunk중 가장 작은 번호 $n_s (=1)$
• 가장 앞에 있는 chunk의 시작 데이터 인덱스 $i_s (=1)$
• chunk중 가장 큰 번호 $n_e (=3)$
• 가장 뒤에 있는 chunk의 끝 데이터 인덱스 $i_e (=1)$
• chunk 크기 $N (=4)$

괄호 안의 값은 위 그림에서의 값이다. 그럼 이제 $k$번째 값이 몇번째 chunk에 있는지 구해보자. 구하려는 chunk 번호를 $n_k$라고 하면 $n_k = n_s + \lfloor\frac{k + i_s - 1}{N}\rfloor$이 된다. (-1은 k가 1-based index여서 빼준다.) chunk 번호를 구했으니 해당 chunk에서 몇 번째 인덱스인지는 $i_k = (k - (N - i_s) - 1)\% N $이 된다. (-1은 마찬가지로 1-based index여서 뺀다.) 
 

삽입 삭제

삽입 삭제는 이제 쉽다. 앞에 삽입하는 과정을 보자. $i_s$가 0이라면 가장 앞 chunk가 가득 찼으므로 $n_s$를 하나 줄이고 chunk를 하나 생성한 후 맨 뒤에 넣는다. 그렇지 않으면 $i_s$를 하나 빼고 그곳에 넣는다. 뒤에 삽입하는 과정은 유사하게 진행하면 된다.
삭제도 $i_s$가 $N - 1$이라면 해당 chunk를 삭제하고 $n_s$를 늘린다. 그렇지 않으면 $i_s$를 늘린다.
 

구현

구현은 위의 원리를 그대로 코드에 적용하면 된다.

class deque:
    def __init__(self):
        self.chunkmap = {}
        self.n = 4
        self.n_s = 0
        self.n_e = 0
        self.i_s = 0
        self.i_e = 0
        self.size = 0
        self.ix = 0  # iterator index

    def __getitem__(self, k):
        if k >= self.size or k < 0:
            raise IndexError
        n_k = self.n_s + (k + self.i_s) // self.n
        i_k = (k - self.n - self.i_s) % self.n
        return self.chunkmap[n_k][i_k]

    def append(self, x):
        if self.n_e not in self.chunkmap:
            self.chunkmap[self.n_e] = [None]*self.n
        self.chunkmap[self.n_e][self.i_e] = x
        if self.i_e == self.n-1:
            self.n_e += 1
            self.i_e = 0
        else:
            self.i_e += 1
        self.size += 1

    def pop(self):
        if self.size == 0:
            raise IndexError
        if self.i_e == 0:
            self.chunkmap.pop(self.n_e)
            self.n_e -= 1
            self.i_e = self.n-1
        else:
            self.i_e -= 1
        x = self.chunkmap[self.n_e][self.i_e]
        self.chunkmap[self.n_e][self.i_e] = None
        self.size -= 1
        return x

    def appendleft(self, x):
        if self.i_s == 0:
            self.n_s -= 1
            self.i_s = self.n-1
        else:
            self.i_s -= 1
        if self.n_s not in self.chunkmap:
            self.chunkmap[self.n_s] = [None]*self.n
        self.chunkmap[self.n_s][self.i_s] = x
        self.size += 1

    def popleft(self):
        if self.size == 0:
            raise IndexError
        x = self.chunkmap[self.n_s][self.i_s]
        self.chunkmap[self.n_s][self.i_s] = None
        if self.i_s == self.n-1:
            self.chunkmap.pop(self.n_s)
            self.n_s += 1
            self.i_s = 0
        else:
            self.i_s += 1
        return x

    def __len__(self):
        return self.size

    def __iter__(self):
        self.ix = -1
        return self

    def __next__(self):
        self.ix += 1
        if 0 <= self.ix < self.size:
            return self[self.ix]
        raise StopIteration

 

성능 분석

당연히 앞 뒤 삽입삭제는 $O(1)$이고 인덱스할 때 chunk번호 계산, 인덱스 번호 계산, map 참조 연산이 추가되어 일반보단 느릴것이다. 그래도 $O(1)$에 준하는 성능을 보장할 수 있고 실제로 위에서 실험한 코드를 그대로 적용해보면 

collections에 있는 deque보다 훨씬 빠르다. C++의 deque는 chunk기반인 것같고 파이썬은 chunk기반으로 구현된건 아닌것같다.
그리고 chunk size도 지금은 4로 설정했지만 이 값을 변경해보며 최적의 값을 찾으면 더 나은 성능을 가질 수 있을 것 같다.

 

다만 주의할 점은 chunk에 데이터가 가득 찬 상태에서 추가할 경우 새로운 chunk를 만들기 위해 시간복잡도가 $O(size)$가 된다. (size는 chunk의 크기) 파이썬 list이나 C++ vector에서의 array doubling과 유사하게 이런 경우가 자주 있는 입력이라면 기존 연결리스트 덱보다 성능이 저하된다. 따라서 앞 뒤 삽입삭제의 시간복잡도는 amortization을 하여 amortized $O(1)$이라고 보는게 합리적이다.
 
또한 벡터의 고질병 중 하나인 중간위치 삽입삭제가 $O(N)$이었는데 여기에서도 그 문제는 해결하지 못했다. 하지만 입력 개수를 안다면 chunk size를 잘 정하고 chunk를 리스트로 구현한다면 $O(\sqrt{N})$까지 최적화할 수 있을 것 같다.

찾아보니 이런 연산을 $O(\log N)$에 수행하는 로프 자료구조가 있다. 보통 상수시간은 통과하고 로그시간이 통과하지 않는 경우는 드물기 때문에 덱의 상위호환이다. 이는 BBST 기반으로 구현되어 효율적으로 연산이 가능하다.