Amortized Analysis (Dynamic Table)

우리는 하나의 테이블에 얼마나 많은 객체가 저장될지 미리 알 수 없다.

 

예를들어 < Insert, delete, insert, insert, delete,..> 같이 일련의 작업이 수행될 때,

insert 작업으로 인해 테이블이 가득 찰 수 있다.

 

이 경우, 추가로 작업을 할당하기 위해서는 테이블을 비우거나 (Contraction) 확장시켜야 (Expansion) 한다.

 

 

우리가 배울 Dynamic Tables의 목적은

삽입 및 삭제에 따른 amortized cost가 O(1)라는 것을 나타내는 것이다.

 

공간을 최대한 효율적으로 활용하면서, 사용되지 않는 공간은 항상 할당된 공간의 상수 부분보다 작은 상태를 유지하도록 한다.

위의 테이블은 insert와 delete 연산으로 확장될수도, 축소될수도 있다.

각각의 연산은 상수 시간에 실행된다.

 

이런 목표를 달성하기 위해, 우리는 어떻게 테이블의 크기를 동적으로 제어할 수 있을까?

 

 

 

Table Expansion

만약 가득 찬 테이블에 item을 삽입한다면, 우리는 더 많은 슬릇이 있는 새로운 테이블을 할당해서 확장시켜야 한다.

하지만 얼마나 많은 슬릇을 추가로 할당해야 하는지 정해진 것은 없다.

 

 

 

Aggregate Analysis

처음에 비어있던 테이블에서 n개의 TABLE‑INSERT 작업 시퀀스를 분석해보자.

 

 

현재 테이블에 새 항목을 위한 슬릇이 있는 경우, 비용 c = 1 // insertion

현재 테이블이 가득 차있으면 비용 c = (i - 1) + 1 = i   // expansion and insertion

 

그렇다면 현재 테이블에는 새 테이블에 복사해야 할 항목이 i-1 개 있고, 새 테이블에 i번째 항목을 삽입한다.

 

 

 

예를 들어 이와 같은 문제가 제시되어 i-1이 2의 정확한 거듭제곱일 때 i, 아니면 1의 비용을 갖는다고 설정하자.

 

이 때, 각 연산 당 amortized cost는 O(n)/n = O(1)이 된다.

 

 

 

 

Accounting Method

 

accounting 방법으로 table-insert 작업의 amortized cost를 계산했을 때, 비용이 3이되는 과정을 알아보자.

 

우선, 새로운 항목을 삽입할 때 비용 1이 지불된다.

향수 복사할 새 항목에 대해 (확장 발생 시) 비용 1을 지불한다.

확장 시, 향후에 복사할 다른 기존 항목에 대해 비용 1을 지불하므로, 

각 작업 당 amortized cost는 O(1)이다.

 

 

 

 

Potential Method

확장 직후 테이블의 포텐셜은 0이다.

이후, 다음 확장까지 포텐셜을 저장하여 모든 항목을 복사하는 데 필요한 잠재력을 모은다.

확장 직후, 모든 항목을 복사하는데에 모든 포텐셜을 사용한 모습과

확장 전, 모든 항목을 복사할 포텐셜 T.num의 모습이다.

 

 

 

포텐셜에서 i번째 Table-insert 연산의 amortized cost를 구하는 경우를 2 가지로 나눌 수 있다.

 

하나는 operation이 확장하지 않는 경우

i번째 size와 i-1번째 size는 서로 같고, i번째 실제 비용은 1이다.

 

다른 하나는 operation으로 확장을 한 경우

i번째 size는 i-1 번째 size의 2배이고,

i-1번째 size는 i-1번째 num과 같다. (i번째 num -1)

i번째 실제 비용은 i번째 num과 같다.

 

여기에서 각 연산 당 amortized cost는 O(1)이다.

 

 

 

 

 

Table Contraction

사용하지 않는 슬릇이 많은 경우, 절반 크기의 새 테이블을 재할당하고

나머지 항목을 새 테이블에 복사한다.

 

Load factor 𝛼 = T.num/T.size

 𝛼 = 1이면 테이블이 모두 차있는 상태이고

 𝛼 = 1/2 이면 테이블이 반만 차 있는 상태이다.

 

우리는  𝛼 를 통해 테이블을 축소할지 말지를 결정하는 기준으로 사용할 수 있다.

(만약  𝛼 가 너무 낮으면, 테이블을 축소한다.)

 

어떻게 구현할 것인지에 앞서 분명한 것 먼저 정리하자면

 𝛼 가 1보다 크거나 같으면 테이블이 모두 차있는 것으로, 테이블을 두 배로 확장할 것이고

 𝛼 가 1/2 보다 작다면 테이블이 1/2보다 덜 차있다는 것으로, 테이블을 반으로 축소할 것이다.

그러므로, 우리는 항상 1/2 ≤ 𝛼 ≤ 1를 만족한다.

 

 

여기에서 좀 더 개선을 해보자

 

예를 들어 위 상황에서 테이블이 확장된 후 곧바로 많은 요소가 제거되어 다시 축소되는 상황이 발생할 수 있다.

이 경우 확장과 축소가 반복되면서 비효율적인 연산이 빈번하게 발생하게 된다.

 

 

이런 상황을 방지하기 위해 아까 설정했던 contraction 조건을 1/4 로 완화하자.

이렇게 크기 조정의 빈도를 줄여서 전체 연산의 평균 비용을 줄일 수 있다.

 

 

 

 

Potential Method

 

테이블의 확장 직후 포텐셜이 0이었듯이, 수축 직후 테이블의 포텐셜 또한 0이다.

 

확장하는 경우는 다음 확장까지 다시 모든 항목을 복사하는 데 필요한 포텐셜을 구축하는 것이고,

수축의 경우는 모든 항목을 복사하는 데 필요한 포텐셜을 구축하는 것이다.

 

 

TABLE-INSERT operation

i-1번째 𝛼 가 1/2 보다 작은 경우 (확장하지 않음)

여기에서 i번째와 i-1 번째 size는 같고, i-1번째 num은 i번째 num - 1이다.

 

i번째 𝛼 가 1/2 보다 작거나 1/2 보다 크거나 같은 경우

 

이렇게 insert의 상각 비용은 O(1)이다.

 

 

 

TABLE-DELETE operation

 

i-1번째 𝛼가 1/2 보다 작고 contraction하지 않는 경우

여기에서 i번째와 i-1번째 size는 서로 같다.

 

 

 

i-1번째 𝛼가 1/2보다 작고 contraction을 유발하는 경우

 

이렇게 delete의 상각 비용은 상수로 제한되어 O(1)이다.