[ Open Data Structures ] - Dual Array Deque - 1

Dual Array Deque : Building a Deque From Two Stacks

/*

    수정 : Balance() 함수의 back stack을 확장하는데 있어서 For-Loop에 Get(nb + j )를 Get(nf + j)로 수정

*/

 

Dual Array Deque를 만들어 본다. Array Stack을 두 개 사용해서 전에 만들었던 Array Deque와 비슷한 성능을 낼 수 있다. 사실, Asymptotic performance자체는 Array deque와 크게 차이가 나지 않지만, 두 개의 간단한 자료구조를 조합하여 정교한 자료구조를 만드는 좋은 예제가 될 수 있다.

Dual Array Deque는  두 개의 Array Stack을 사용하는 List를 나타낸다. Array Stack이 배열의 양 끝에서 작업을 진행할 때, 빠른 속도를 보여주었던 것을 상기한다. Dual Array Deque는 front와 back이라는 두 개의 Array stack을 등을 맞댄 형태로 두어서 어느 끝에서 접근하여도 빠른 성능을 낼 수 있도록 한다.

Dual Array Deque는 저장된 원소의 개수를 추적하는 n을 명시적으로 갖지 않는다. n = front.size() + back.size()개의 원소를 갖고 있기 때문이다. 그럼에도 불구하고 Dual Array Deque를 분석함에 있어서 n이라는 키워드를 자주 사용할 것이다. 또한, front나 back없이 단독으로 GetSize()라고 쓴 것은 front와 back의 크기를 합한 n을 호출한 것과 완전히 같다.

Get(_i) / Set(_i, _x) Operation

Front Array Stack은 index가 0, 1, ... , front.size() - 1인 원소들을 역순으로 저장한다. Back Array Stack은 index가 front.size(), front.size() + 1, ... , GetSize() - 1인 원소들을 평범하게 저장한다. 이런 식으로 Get(_i)과 Set(_i, _x)는 적절하게 변형이 되어야 하고 O(1)의 시간복잡도를 갖는다.

만약, index를 나타내는 _i가 front.GetSize()보다 작다면 front가 index를 역순으로 저장하고 있기 때문에 실질적으로 front에 index _i에 접근하려면 front.GetSize() - _i - 1로 접근해야 한다.

Adding and Removing operation

아래의 그림에 Adding과 Removing의 Operation의 과정이 나타나 있다. Add(_i, _x) 작업은 front든 back이든 필요에 따라 적절히 조작한다. 가운데 수직으로 그은 선으로부터 0-index이며 back은 우측으로 갈수록 커지고 front는 좌측으로 갈 수록 index가 증가한다.

Add(_i, _x)는 Balance()함수를 호출하는 것으로 front와 back의 Rebalancing을 도모한다. Balancing의 Implementaion을 곧장 보여주겠지만 현재로서는 이 Balance()가 front와 back의 크기의 합(GetSize())이 2이상이라면 front와 back의 크기는 3배 이상 차이가 나지 않는다는 것을 보장한다. 식으로 표현하면 다음과 같다는 것을 보장한다.

따라서, Add(_i, _x)의 Running time 은 Balance()를 무시한다면 O( 1 + min{_i , n - _i{)다.Remove(_i)의 Operation과 분석은 Add와 유사하다.

Balancing

이제, Add와 Remove의 operation에 포함된 Balance()에 대한 논의를 할 차례다. 이 함수는 front든 back이든 그 크기가 너무 작거나 크게 변화하는 것을 방지한다. 위에서도 말했지만 각 Array Stack의 원소의 개수가 2미만이 아닌 경우에 각 Array Stack은 적어도 n/4개의 원소를 갖게 된다. 두 Array Stack이 이러한 조건을 만족하지 않는 경우엔 front와 back간의 원소의 이동을 촉발하여 각각 floor(n/2)와 ceil(n/2)개의 원소를 갖도록 조정한다.

 만약 Balance()가 Rebalancing을 수행하면 총 n개의 원소의 이동이 촉발되고 O(n)의 시간이 걸린다. 그런데 Add와 Remove의 호출마다 Balance()를 수행하기 때문에 굉장히 비효율적이고 긴 시간이 요구될 것처럼 보이다. 하지만 다음 Lemma에서 평균적으로 O(1)의 시간만 요구한다는 것을 보일 것이다.

Summary

다음의 Theorem이 Dual Array Deque의 Properties를 요약한다.

Theorem. Dual Array Deque는 List interface를 implement한다. Resize()와 Balance()의 비용을 무시한다면 다음과 같은 결과를 얻는다.

• Get(_i) / Set(_i, _x) : O(1) time per operation
• Add(_i, _x) / Remove(_i) : O( 1 + min{_i, n - _i}) time per operation

추가적으로, 텅 빈 Dual Array Deque에서 m번의 Add나 Remove는 Resize()와 Balance()로 인해 총 O(m)의 time spent를 유발한다.

 

HiddenWriter/List at DualArrayDeque (github.com)