[ Open Data Structures ] - Rootish Array Stack - 1

 

Rootish Array Stack

 

blocks엔 자료의 포인터를 준다. 자료의 개수를 추적하는 mSize.

 

Get and Set

 

이러한 방법을 토대로 Get과 Set을 직관적으로 작성할 수 있다. 가장 먼저 적절한 block b를 찾아내고 해당 block 내의 index i가 위치할 index j를 계산하면 된다. 마지막으로 호출한 각 함수마다 적절한 조치를 취하면 끝이다. 일반적으로 이 작업들은 Constant time내에 완료된다.

 

Add and Remove

 

Grow()에서 소모하는 시간을 제외하면 Add의 Running time은 Array Stack처럼 원소들의 위치를 교환하는 작업에 압도적으로 의존하게 된다. 따라서 Array Stack과 같은 O(1 + n - i )의 Running time을 갖는다. 

Remove는 Add와 비슷하게 동작한다. i+1, i+2, ... n을 i+1보다 작은 방향으로 밀어내는 작업을 하고 텅 빈 (혹은 사용하지 않는 ) block이 존재한다면 해당 block을 제거하는 Shrink()를 호출한다.

Add와 마찬가지로 Shrink()의 호출을 무시한다면 Remove의 Running time은 자료나 원소의 교환에 절대적으로 영향을 받고 O(n - i)의 Running time을 갖는다. 

 

Analysis of Growing and Shrinking

 

위의 Add와 Remove의 분석에선 Grow()와 Shrink()의 시간을 무시했다. Array Stack의 Resize()와는 다르게 Grow()와 Shrink()는 사실 자료를 복사하지 않는다. ( 잘 생각해보면 자료의 복사는 Add나 Remove 자체가 수행하는 기능이지 Grow()와  Shrink()가 수행하는 바는 아니었다. ) 이 두 함수는 그저 메모리에 배열을 할당하거나 해제하는 역할을 수행할 뿐이었다. 어떤 환경에서는 배열의 크기 r에 비례하는 시간을 소모할 수 있으며 또 어떤 환경에서는 상수 시간만을 요구할 수도 있다.

Grow()와 Shrink()의 호출 직후의 상황은 정갈하다고 표현할 수 있다. 마지막 Block은 아무것도 저장하고 있지 않을 것이며 그 이전 Block은 모든 배열에 자료를 저장하고 있는 상태일 것이다. 이 상태에서 더 자료를 추가하거나 한 Block을 비우기 전까지 Grow()나 Shrink()가 호출되는 일은 없다. 따라서 설령 이 두 함수의 Running time이 O(r)이라고 하더라도 Amortised running time을 생각하면 Amortised running time으로서는 O(1)이라고 할 수 있다.

 

Space Usage

 

HiddenWriter/List at RootishArrayStack (github.com)