[ Open Data Structures ] - Array Deque - 1

Array Deque : Fast Deque Operation using an array

Array Queue는 배열의 한 지점에서 정보를 저장하고 반대편에서 삭제하는 자료구조였다. Array Deque는 양지점 어느 쪽에서든 자료의 저장/삭제를 효율적으로 할 수 있도록 해준다. 이 자료구조는 Array Queue에서 봤던 Circular array를 사용하여 List interface를 implement한다.

각 변수가 의미하는 바는 Array Queue와 크게 다르지 않다. 삭제할 index를 추적하는 mElem2Remove, 배열에 저장된 원소의 개수를 추적하는 mNumOfElem, 그리고 배열 mArr.

Get(_i) Set(_i, _x)

Get(_i)과 Set(_i, _x)의 operation은 직관적이다. 각 작업은 mArr[(mElem2Reove+mNumOfElem) mod mArr.mLength]의 정보를 얻거나 수정/설정한다. 

다음 그림은 Array Deque의 Add와 Remove의 과정을 그린 것이다. 배열 간 화살표는 각 자료가 복사/이동되는 것을 의미한다.

Adding and Removing

Add의 implementaion엔 흥미로운 점이 있다. 언제나 처럼 배열의 포화상태를 확인하고 필요하다면 Resize()를 호출한다. 여기서 우리는 _i가 0이나 mNumOfElem(즉, 배열의 크기)에 가까울 수록 빠르게 수행되도록 만들고 싶다는 점을 염두에 둔다. 따라서,  _i < mNumOfElem / 2를 확인한다. 참이라면 mArr[0], .. mArr[_i - 1]를 각각 좌측(음의 방향)으로 한 칸씩 밀어 넣는다. 거짓이라면(즉, _i >= mNumOfElem으로써 _i가 0보다는 mNumOfElem에 가깝다면) a[ _i ], ... , a[ n - 1 ]을 전부 우측으로 한 칸씩 밀어 넣는다. 이 과정은 상단의 그림에 잘 나타나있다.

Add를 할 때, _i를 검증하는 과정을 추가하는 것으로 Add(_i, _x)의 과정이 결코 min{_i, mNumOfElem - _i}을 초과하는 원소의 이동을 요구하지 않는다는 점이 두서에 말했던 흥미로운 점이다. 따라서, Add의 Running time은 Resize()를 무시한다면 O( 1 + min{ _i , mNumOfElem - _i })이다.

Remove(_i)의 Implementation도 Add(_i, _x)와 크기 다르지 않다. 삭제할 index _i를 검증하고 좌측으로 밀지 우측으로 밀지 결정한다. Add와 같은 논리로 Remove역시 O( 1 + min{ _i , mNumOfElem - _i })의 비용이 발생한다.

 Summary

다음과 같은 Theorem이 Array Deque의 Performance를 요약한다.

Theorem. Array Deque는 List Interface를 Implement한다. Resize()를 호출하는데 필요한 시간복잡도를 빼면 다음과 같은 Running time을 요구한다.

• Get(_i) / Set(_i, _x) : O(1)
• Add(_x) / Remove(_i) : O( 1 + min{ _i , mNumOfElem - _i })

더 나아가서, 텅 빈 Array Deque에서 m번의 Add(_x)와 Remove(_i)의 호출에서 발생한 Resize()의 Running time은 O(m)이다.

 

HiddenWriter/List at ArrayDeque (github.com)