Amortized Analysis를 통해 Unbounded Arrays를 알아보자

* 해당 글은 학과 수업으로 배운 내용과 코드가 포함되어 있으며 개인적 공부 목적으로 업로드하였습니다.

 

Text file에 있는 모든 단어들을 array와 유사한 데이터 구조에 넣는다고 가정했을때

우리는 몇개의 단어가 그 파일에 있는지 알 수 없다. 

 

이에 따라 우리가 생각할 수 있는 것은 unbounded array이다.

Array의 element를 access하는 것은 O(1)이며 우리는 적당한 size의 array를 가져야 한다. 

이러한 unbounded array를 어떻게 만들 수 있을까?

 

이전에 우리는 linked list 를 통해 SSA type struct를 구성할 수 있었다.

struct ssa_header{
    int length;
    string[] data;
}

element를 추가해가며 unbounded array에도 적용할 수 있는지 살펴보자

 

일반적인 array ["a","b"], length=2에서 "c"를 추가하려고 할때 

새로운 length=3의 array를 만들고, 기존 elements를 복사하고 "c"를 추가한다. => O(n)

 

다시 "c"를 제거하려고 할때 새로운 length=2의 array를 만들고, 기존 elements를 복사하고 "c"를 return => O(n)

 

만약 array를 바꾸지 않고 length attribute만 바꾼다면 elements를 복사하지 않아도 되므로 insert/delete 모두 O(1)이 된다. 

하지만 우리는 사전에 array의 실제 길이를 알수 없다.-> safe하지 않다.

 

기존 length attrbute를 두가지 field로 나누면 어떻게 될까?

-size: unbounded array의 size => element 개수

-limit: array의 실제 길이

struct header{
    int size;  //0<=size && size<limit
    int limit;
    string[] data;
};

 

다시 "c"를 추가해보자. 

(size=2, limit=4)

-> size를 올리고 새로운 element를 사용하지 않은 space에 채워넣는다. => O(1)

"c"를 다시 삭제하는 것도 같은 원리다. 

 

만약 여기에서 "e"를 또 추가한다면

-> size가 4가 되고 limit과 같아지면서 array를 resize해야한다. 

 

그렇다면 얼마나 길게 resize해야할까?

우선 size와 limit이 같아질때마다 하나씩 길게 만든다고 해보자.

 

이것 역시 기존의 element를 복사해야하므로 O(n)이 된다. 

계속해서 반복해서 element를 넣을때마다 O(n)이 될것이다. 

 

우리가 n operations를 한다고 했을 때 총 O(n^2)의 complexity를 가질 것이다.

(이에 따라 O(n)의 amortized cost를 가진다. )

 

만약 우리가 array resize를 2개씩 늘린다고 해도 여전히 같은 complexity를 가진다.

 

이를 통해 우리는 constant c만큼 array를 resize할때는 항상 같은 complexity를 가짐을 확인 할 수 있다. 

 

 

이번에는 array를 resize할 때마다 길이를 double시킨다 .

이것 역시 기존의 element를 복사해야하므로 O(n)이 된다. 

하지만 다음 operation이 매번 O(n)이 되지는 않는다. (여유 space가 있기 때문이다.)

바로 이어서 새로운 element를 넣는다면 O(1)의 complexity를 가진다. 

 

이에 따라 length를 2배로 늘려 resize를 할경우 worst-case complexity가 O(n),

그리고 amortized complexity가 O(1)이 됨을 알 수 있다. 

 

이에 따라 다른 operation또한 정리를 하자면

unbounded array 혹은 그의 length를 구하는 경우 => O(1)

element를 지우는 경우 => O(1)

특정 위치에 특정 element를 지정하는 경우 => O(1)

새로운 unbounded array를 만드는 경우 => O(size)

 

코드 구현

 

실제 unbounded arrays를 만들기 위해서 필요한 함수들을 실제로 구현해보자

 

우리는 이전에 struct를 이미 구현했고 이에 따른 type이름을 아래와 같이 정한다.

typedef struct header uba*

이제부터 unbounded array는 uba* type이 되기 때문에 (pointer) 우리는 이것이 NULL이 아니고 struct header안의

attributes에 필요한 조건들을 모두 만족하는지를 확인해야 한다. 

또한 나머지 operation도 비슷하게 구현할 수 있다.

 

bool is_array_expected_length(string[]A, int length){
  //@assert \length(A) == length;
  return true;
}

bool is_uba(uba* A){
    return A!=NULL
        && is_array_expected_length(A->data, A->limit)
        && 0<= A->size
        && A->size <A->limit;
}

int uba_len(uba* A)
//@requires is_uba(A);
//@ensures 0<= \result && \result < \length(A->data);
{
   return A->size;
}

string uba_set(uba* A, int i, string x)
//@requires is_uba(A);
//@requires 0<= i&& i<uba_len(A);
//@ensures is_uba(A);
{
	A->data[i] = x;
}

string uba_get(uba* A, int i)
//@requires is_uba(A);
//@requires 0<= i && i< uba_len(A);
{
 	return A->data[i];
}

uba* uba_new(int size)
//@requires 0<=size;
//@ensures is_uba(\result);
//@ensures uba_len(\result)==size;
{
    uba* A = alloc(uba);
    int limit = size == 0?1 : size*2;
    A->data = alloc_array(string, limit);
    A->size = size;
    A->limit = limit;
    return A;
}

Element를 추가하는 함수 역시 아래와 같은 논리로 구현할 수 있다.

-새로운 element를 쓰고 

-size를 증가시키고

-만약 array가 다 찼다면 resize한다.

 

void uba_add(uba* A, string x)
//@requires is_uba(A);
//@ensures is_uba(A);
{
   A->data[A->size] = x;
   (A->size)++;
   
   if (A->size < A->limit) return;
   assert(A->limit <= int_max()/2); //fail if new limit would overflow
   uba_resize(A, A->limit*2);
}

그렇다면 array를 어떻게 resize할 수 있을까?

-새로운 limit의 array를 구현한다.

-기존 element를 복사한다

-바뀐 limit으로 header의 field를 바꾼다.

void uba_resize(uba* A, int new_limit)
//@requires A!=NULL;
//@requires 0<= A->size && A->size <new_limit;
//@requires \lengthh(A->data)==A->limit;
//@ensures is_uba(A);
{
   string[] B = alloc_array(string, new_limit);
   
   for (int i=0; i<A->size; i++)
   //@loop_invariant 0<= i && i<=A->size;
   {
      B[i] = A->size[i];
   }
   A->limit = new_limit;
   A->data = B;
}

Summary

- Amortized Complexity: Operation에 따라 평균 cost

- Amortized Analysis를 통해 unbounded arrays에 대한 cost를 얻을 수 있다.

Operation	Worst-case Complexity	Amortized Complexity
uba_len	O(1)	O(1)
uba_new	O(n)	O(n)
uba_get	O(1)	O(1)
uba_set	O(1)	O(1)
uba_add	O(n)	O(1)
uba_rem	O(n)	O(1)