랜덤 접근이 가능한 deque 자료구조를 chunk로 구현하면 어떤 이점이 있을까요?

 deque를 공식 레퍼런스 사이트에서 보면, Chunk로도 구현이 된다고 되어 있습니다. 그러면, Chunk로 구현했을 때, 장점이 무엇일까요? 일단, deque가 Random 접근이 되려면, 기본적으로 연속적이여야 합니다. List는 Random access를 지원하지 않습니다. 더 정확히 이야기 하면, base 주소가 있고, 그것을 통해서 i번째 index에 접근할 수 있어야 합니다.

 

 

---

 1차 구조의 덱을 생각해 보겠습니다. 원래 4개의 원소가 있었고, 5를 어딘가에 추가한다고 해 보겠습니다. 원래 capacity가 4였다면, 하나를 추가하려는 순간 추가하지 못하게 될 겁니다.

 

 그러므로 확장 연산이 수행이 될 겁니다. 그러면 확장된 후에 기존의 원소가 어떻게 들어가는 것이 좋을까요?

 

 

 이렇게 들어가는 것이 최선일까요? 우리는 최악의 경우를 생각해 보아야 합니다. 이 경우에는 앞에다 추가를 하는 연산이 2번만 호출되어도, 다시 expand가 일어나야 합니다.

 

 

 5를 앞에 추가 하고 6을 추가하려는 경우에, 더 이상 들어갈 공간이 없기 때문에, expand가 일어나야 합니다. 반대로, 이렇게 들어가면 어떨까요?

 

 

 뒤에다 원소를 추가하는 연산이 2번만 일어나도, expand가 일어나게 될 겁니다.

 

 

 5를 뒤에 추가하고, 6을 뒤에 추가하려 한다면? 6이 들어가지 못하니 확장 연산이 일어날 겁니다. 계속 앞에 부분에만 추가되거나, 계속 뒤에 부분에만 추가되는 극단적인 케이스에서도 효율적으로 동작이 되게 하기 위해서, 확장 연산이 일어난 경우에, 기존에 있는 원소들을 새로 할당된 배열의 중간에다가 채워버립니다.

 

 

 이렇게 옮겨버린 경우에는, 최소 2번의 push 연산이 확장 연산 없이 일어날 수 있어요. 확장 되었을 때, 중간 부분에 원래 원소들을 갔다 놓는 방식을 썼을 때, push_back이나 push_front 연산의 amortized 복잡도는 어떻게 될까요?

 

 

---

 먼저 연산들의 비용을 정의하겠습니다.

 

 그리고 충분히 많이 expand가 되었다고 해 봅시다.

 

 

 마지막으로 확장되었을 때, 중심점을 기준으로 왼쪽에 s개, 오른쪽에 s개가 있었다고 해 봅시다. 그 다음에 계속 push_back을 호출할 건데요. 확장 연산이 일어나기 직전에, push_front가 호출되지 않았습니다. 왼쪽에 있는 수의 갯수는 변함이 없습니다. 좌측에는 s개가, 우측에는 ks개의 원소가 있었다고 해 보겠습니다. 단, k는 1보다 큰 실수라고 해 보겠습니다.

 

 expand가 되었을 때, 중간에 가깝에 원소들을 복사한다고 했습니다. 이 때 우/좌의 값을 k라고 하겠습니다.

 

 

 그 다음에 확장이 일어나기 직전까지 계속 뒤에다 추가해 보겠습니다. 그러면 왼쪽에는 s(1+k)/2개가, 우측에는 2sk개가 있을 겁니다. 그러면, 이 때, 우/좌의 값은 4k/(1+k)가 됩니다. 그러면 다음이 성립합니다. k번째 우/좌값을 a(k), k+1번째 확장이 일어났을 때 우/좌 값을 a(k+1)이라 하면 아래가 성립합니다.

 

 

 어디서 많이 본 관계식이 나왔는데요. a(n+1) = pa(n) + q꼴입니다. 그러면 이 꼴은 a(n+1) + Q = p(a(n) + Q)꼴로 바꿀 수 있어요.

 

 

 그러면, a(n)은 n이 무한히 커지면 3으로 수렴합니다. 즉, 확장이 무한번 되었다고 가정했을 때 다음이 성립합니다.

 

 

 확장이 일어난 직후에, 1T, 1T는 왼쪽, 오른쪽에 있는 수의 갯수입니다. 그리고 2T만큼의 수를 뒤에다가 넣을 수 있다는 의미입니다. 그러면, 총 원소의 갯수는 6T일 겁니다. 만약에 이 상태에서 2T만큼 넣었다고 해 봅시다.

 

 

 그 다음에 원소를 뒤에다 넣으려고 하는 경우에는, 넣을 수 없습니다. 그렇기 때문에, 12T의 크기를 가지는 배열을 새로 만들어야 합니다. 그리고 4T만큼을 복사해야 합니다.

 

 

 이것이 끝이 아닙니다. 기존 배열은 delete 해야 합니다. 이 비용은 6T입니다.

 

 

 6T에다가 12T에 4T에 대입 비용인 2T를 더하면, 24T입니다. 여기에 2T를 나누면 12가 나옵니다. 물론, 대입 연산을 빼고 생각했을 때에는 평균 11입니다. 상수 복잡도이긴 하지만, 좋지는 않습니다. 공간은 많아봤자 O(4n)이고, default 크기는 작을 수 있지만, 시간이 생각보다 많이 들 수 있다는 게 문제입니다.

 

 

---

 이렇게 expand가 많이 일어난다면, 이것을 적게 일어나게끔 해야 할 겁니다. 그 방법 중 하나는 CHUNK별로 묶어서 관리를 하는 것입니다.

 

 

  CHUNK들의 포인터들은 동적 배열로 관리합니다. 그리고 각 CHUNK는 정적 배열을 두는 것입니다. 예를 들어, 256개의 int 자료형을 넣는다던지, 128개의 long long을 넣는 식입니다. 각 CHUNK에 들어가는 원소의 갯수를 b개라고 하겠습니다.

 

 

 그러면, b개가 들어갔을 때, 실제 동적 배열로 관리되는 자료 구조에서, 1개의 slot이 채워집니다. 동적 배열에 채워지는 비용이 1/b로 줄기 때문에, 동적 배열의 확장에 의한 amortized 되는 것은 대충 11/b라고 할 수 있습니다. 1개를 할당하면 동적 배열에 1개가 들어갈 것을, b개를 넣으면 1개가 들어가는 것으로 바뀌었으니 그럴 만도 합니다. 즉, dynamic array가 확장되고, 삭제되고, 새로운 동적 배열에 copy되는 비용은 무시해도 되는 수준으로 내려갑니다.

 

 CHUNK를 할당하는 평균 비용이 1이고, 대입하는 비용이 1입니다. 단지, expand가 일어나는 횟수가 줄었을 뿐인데, 앞이나 뒤에 추가하는 연산의 amortized 상수가 생각보다 많이 줄었다는 것을 알 수 있어요. default 공간이 크다는 것과, 1차 구조에 비해서 로컬리티가 떨어지는 단점은 있습니다. 하지만, 그 단점은, 확장 연산이 적게 일어난다는 장점이 커버합니다.