9장 맵과 딕셔너리(2)

9.3 딕셔너리 추상 데이터 타입

맵와 마찬가지로, 딕셔너리(dictionary)는 키-값 쌍(k, v)을 저장하는데, 

우리는 이것을 항목(엔트리, entry)이라고 부르는데,

k는 키이고 v는 값이다. 

마찬가지로, 딕셔너리는 키와 값이 어떤 객체 타입이든 허용한다. 

그러나 맵은 항목이 고유한 키를 가지고 있다고 주장하는 반면, 

딕셔너리는 동일한 단어에 대한 

여러 정의를 허용하는 영어 사전과 마찬가지로 

여러 항목이 동일한 키를 가질 수 있도록 허용한다.

우리는 순서 없는 딕셔너리(unordered dictionary)와

순서 있는 딕셔너리(ordered dictionary)의 두 가지 타입을 구별한다. 

순서 있는 딕셔너리에서는 키에 대해 전체 순서 관계가 정의된다고 가정하고 

이 순서를 참조하는 추가 메소드를 제공한다(9.5.2절 참조). 

그러나 순서 없는 딕셔너리에서는 키에 순서 관계가 가정되지 않으므로 

키 간의 동등성 검정만 사용된다.

ADT로서 (순서 없는) 딕셔너리 D는 다음과 같은 메서드를 지원한다:

size(): D의 엔트리 수를 반환한다.

isEmpty(): D가 비어 있는지 여부를 테스트한다.

find(k): 

D에 k와 같은 키를 가진 엔트리가 포함되어 있으면, 그러한 엔트리를 반환하고, 

그렇지 않으면 null을 반환한다.

find All(k): 키가 k와 같은 모든 항목을 포함하는 반복 가능한 컬렉션을 반환한다.

insert(k,v): 키 k와 값 v를 가진 엔트리를 D에 삽입하여 생성된 엔트리를 반환한다.

remove(e): 엔트리 e를 D로부터 제거하고, 제거된 엔트리를 반환하거나 D에 없는 경우 null이다.

entries(): D의 키-값 항목의 반복 가능한 컬렉션을 반환한다.

 

우리의 딕셔너리 연산은 딕셔너리에 저장된 키-값 쌍인 엔트리를 사용한다는 것에 주목하라. 

우리는 각 엔트리가 키와 값 구성 요소에 각각 접근하기 위해 

getKey()와 getValue() 메서드를 갖추고 있다고 가정한다.

메소드 find(k)가 실패하면(즉, k와 같은 키를 가진 엔트리가 없음), 

센티넬 null을 반환하는 규칙을 사용한다.

물론, 다른 선택은 실패한 find(k)에 대한 예외를 던지는 것이지만,

우리의 딕셔너리에 없을 수도 있는 키를 요청하는 것은 일반적이기 때문에

그것은 아마도 예외를 적절하게 사용하지 않을 것이다.

게다가, 예외를 던지고 받는 것은 일반적으로 센티넬에 대한 테스트보다 느리기 때문에,

센티넬을 사용하는 것이 더 효율적이다.

정의했듯이, 딕셔너리 D는 키가 같은 다른 엔트리를 포함할 수 있다. 

이 경우, 연산 find(k)는 키가 k와 같은 임의의(arbitrary) 엔트리(k,v)를 반환한다.

여담으로 딕셔너리 ADT가 실제로 위에 주어진 맵 ADT에 대응하고

이제는 더 이상 쓸모없는 것으로 간주되는

추상적인 클래스 java.util. Dictionary와 혼동되어서는 안 된다고 언급한다.

예제 9.2: 다음은 정수 키와 문자 값을 가진 항목을 저장하는

초기 빈 딕셔너리에 대한 일련의 연산을 보여준다.

연산	출력	딕셔너리
insert(5,A)	(5,A)	{(5,A)}
insert(7,B)	(7,B)	{(5,A), (7,B)}
insert(2,C)	(2,C)	{(5,A), (7,B), (2,C)}
insert(8,D)	(8,D)	{(5,A), (7,B), (2,C),(8,D)}
insert(2,E)	(2,E)	{(5,A), (7,B), (2,C), (8,D), (2,E)}
find(7)	(7,B)	{(5,A), (7,B), (2,C), (8,D), (2,E)}
find(4)	null	{(5,A), (7,B), (2,C), (8,D), (2,E)}
find(2)	(2,C)	{(5,A), (7,B), (2,C), (8,D), (2,E)}
findAll(2)	{(2,C), (2,E)}	{(5,A), (7,B), (2,C), (8,D), (2,E)}
size()	5	{(5,A), (7,B), (2,C), (8,D), (2,E)}
remove(find(5))	(5,A)	{(7,B), (2,C), (8,D), (2,E)}
find(5)	null	{(7,B), (2,C), (8,D), (2,E)}

 

9.3.1 리스트 기반 딕셔너리와 감사 추적

딕셔너리를 구현하는 간단한 방법은 순서 없는 리스트를 사용하여 키-값 항목들을 저장한다. 

이러한 구현을 종종 로그 파일(log file) 또는 감사 추적(audit trail)이라고 부른다. 

감사 추적의 주요 응용 프로그램은 구조화된 데이터를 보관하고자 하는 상황이다. 

예를 들어, 많은 운영 체제들은 그들이 처리하는 로그인 요청의 로그 파일을 저장한다. 

전형적인 시나리오는 딕셔너리에 삽입되는 것은 많지만 검색되는 것은 거의 없다는 것이다. 

예를 들어, 이러한 운영 체제 로그 파일을 검색하는 것은 일반적으로 어떤 일이 잘못된 후에만 일어난다. 

따라서 리스트 기반 딕셔너리는 딕셔너리의 항목들을 임의의 순서로 저장함으로써, 

아마도 검색 시간을 희생하더라도 간단하고 빠른 삽입을 지원한다. 

(그림 9.6 참조)

그림 9.6: 로그 파일을 이용한 딕셔너리 D의 구현. 

우리는 이 딕셔너리의 순서 없는 리스트 구현을 강조하기 위해 키만 보여준다.

 

정렬되지 않은 리스트로 딕셔너리 구현

리스트 기반 딕셔너리에 사용된 리스트 S가 이중 연결 리스트로 구현되었다고 가정한다. 

코드 조각 9.7에서 리스트 기반 구현을 위한 주요 딕셔너리 메소드에 대해 설명한다. 

이 간단한 구현에서, 어떤 엔트리가 그것의 위치에 대한 참조를 S에 저장한다고 가정하지 않는다.

코드 조각 9.7: 

정렬되지 않은 리스트 SH로 구현된 딕셔너리 D의 주요 메소드 중 일부.

Algorithm findAll(k):

      Input: A key k

      Output: An iterable collection of entries with key equal to k

      Create an initially-empty list L

      for each entry e in D.entries() do

          if e.getKey() = k then

               L.addLast(e)

       return L                 {the elements in L are the selected entries}

Algorithm insert(k, v):

      Input: A key k and value v

      Output: The entry (k, v) added to D

      Create a new entry e = (k, v)

      Call S.addLast(e)              {S is unordered}

       return e      

Algorithm remove(e):

      Input: An entry e

      Output: The removed entry e or null if e was not in D

      {We don't assume here that e stores its location in S}

      for each position p in S.positions() do

          if p.element() = k then

               Call S.remove(p)

               return e

       return null                 {there is no entry e in D}

Algorithm entries():

      Input: None

      Output: An iterable collection of entries in the dictionary D

       return S                 {The elements in S are the entries in D}

 

리스트 기반 딕셔너리 분석

정렬되지 않은 리스트로 구현된 딕셔너리의 성능을 간단히 분석해 보겠다. 

먼저, 연결 리스트 자료 구조는 크기에 비례하는 메모리 사용량을 가지므로 

n개의 항목으로 구성된 리스트 기반 딕셔너리에 필요한 공간은 O(n)이다. 

또한, 이번 딕셔너리 ADT 구현을 통해

리스트 끝에 새 항목을 추가하는 S의 addLast 메소드에

한 번의 호출만으로 쉽고 효율적으로 insert(k, v) 연산을 구현할 수 있다.

따라서 딕셔너리 D에서 insert(k, v) 연산에 대한 O(1) 시간을 달성한다.

불행히도, 이 메소드를 구현하는 것은 

find 메소드를 효율적으로 수행하는 것을 허용하지 않는다. 

find(k) 연산은 최악의 경우 리스트 S 전체를 스캔하여

n개의 항목을 각각 검사해야 한다. 

예를 들어, S의 위치에 반복기를 사용하여 

k와 같은 키를 가진 항목을 발견하는 즉시 중지할 수 있다

(또는 리스트의 끝에 도달). 

이 메소드의 실행 시간에 대한 최악의 경우는 

검색에 실패했을 때 분명히 발생하며, 

n개의 항목을 모두 검사한 리스트의 끝에 도달한다. 

따라서 find 메소드는 O(n) 시간 내에 실행된다.

마찬가지로, 만약 엔트리들이 

S에서 자신의 위치를 추적하지 못한다고 가정한다면, 

D에 대해 remove(e) 연산을 수행하기 위해서는 n에 비례하는 시간이 필요하다. 

따라서 remove(e) 연산을 수행하기 위한 실행 시간은 O(n)이다. 

또는 S에 자신의 위치를 저장하는 위치 인식 엔트리들을 사용한다면, 

O(1) 시간에 remove(e) 연산을 수행할 수 있다(섹션 9.5.1 참조)

findAll 연산은 항상 전체 리스트 S를 스캔해야 하므로 

실행 시간은 O(n)이다. 

더 정확하게는 

big-Theta 표기법(4.2.3절)을 사용하여 findAll 연산은 

최상의 경우와 최악의 경우 모두 n에 비례하는 시간이 걸리기 때문에 

θ(n) 시간에 실행된다고 말한다.

결론적으로 정렬되지 않은 리스트로 딕셔너리를 구현하면 

삽입 속도는 빠르지만 

검색 및 제거 속도는 느리다. 

따라서 딕셔너리가 항상 작을 것으로 예상하거나 

검색 및 제거 횟수에 비해 

삽입 횟수가 많을 것으로 예상하는 경우에만 

이 구현을 사용해야 한다. 

물론 데이터베이스 보관 및 운영 체제 트랜잭션이 바로 이런 경우이다.

그럼에도 불구하고 

딕셔너리의 삽입 횟수는 검색 및 제거 횟수에 대략 비례할 것이며, 

이러한 경우 리스트 구현이 분명히 부적절한 경우가 많다. 

그러나 다음에 설명할 순서 없는 딕셔너리 구현은 

그러한 경우 빠른 삽입, 제거 및 검색을 달성하는 데 종종 사용될 수 있다.

9.3.2 해시 테이블 딕셔너리 구현

우리는 맵 ADT에서와 거의 같은 방식으로 

해시 테이블을 사용하여 ADT 딕셔너리를 구현할 수 있다. 

물론 주요 차이점은 딕셔너리에서 중복된 키를 가진 항목을 허용한다는 것이다. 

해시 테이블의 로드 팩터가 1 이하로 유지된다고 가정할 때, 

해시 함수는 항목을 상당히 균일하게 퍼뜨리고 충돌을 해결하기 위해 

별도의 체인을 사용한다고 가정하면 

find, remove 및 insert 메소드에 대한 O(1) 시간 성능과 

findAll 메소드에 대한 O(1 + m) 시간 성능을 달성할 수 있다. 

여기서 m은 반환된 항목의 수이다.

또한 버킷 배열 A의 각 셀에 있는 엔트리들을 저장하는 

리스트 기반 딕셔너리가 있다고 가정하면, 

이 딕셔너리를 구현하기 위한 알고리즘을 단순화할 수 있다. 

각 셀은 리스트가 될 것이기 때문에, 

그러한 가정은 우리가 사용하는 개별적인 체인 방식과 일치할 것이다. 

이 방법을 사용하면 코드 조각 9.8과 같은 주요 딕셔너리 메소드를 구현할 수 있다.

코드 조각 9.8: 

딕셔너리 D의 주요 메소드 중 일부는 

버킷 배열, A 및 A의 각 셀에 대한 

순서 없는 리스트로 사용하는 해시 테이블로 구현된다. 

우리는 D의 엔트리 수를 n으로 표시하고, 

A의 용량을 표시하며, 

해시 테이블의 최대 로드 팩터를 표시하기 위해 λ를 사용한다.

Algorithm insert(k, v):

      Input: A key k and value v

      Output: The entry (k, v) added to D

      if (n + 1) / N > λ then

          Double the size of A and rehash all the existing  entries

      e ← A[h(k)].insert(k,v)

      n ← n + 1

       return e      

Algorithm findAll(k):

      Input: A key k

      Output: An iterable collection of entries with key equal to k

       return A[h(k)].findAll(k)

Algorithm remove(e):

      Input: An entry e

      Output: The removed entry e or null if e was not in D

      t ← A[h(k)].remove(e)

      if t ≠ null then

          n ← n - 1

       return t

9.3.3 순서 탐색표 및 이진 탐색

만약 딕셔너리 D의 키가 전체 순서에서 나온다면, 

우리는 키의 순서가 감소하지 않음으로써 

배열 리스트 S에 D의 항목을 저장할 수 있다. 

(그림 9.7 참조) 

배열 리스트에 있는 키들의 순서를 결정하기 위해 

S를 노드 리스트가 아닌 배열 리스트라고 지정하면 

S가 연결 리스트로 구현되었더라면 가능했던 것보다 

더 빠른 검색을 가능하게 해준다. 

물론 해시 테이블은 검색을 위한 예상 실행 시간을 가지고 있다. 

하지만 검색을 위한 최악의 경우 

시간은 연결 리스트보다 나을 것이 없으며, 

실시간 처리와 같은 일부 응용 프로그램에서는 

최악의 경우 검색 경계를 보장해야 한다. 

이 절에서 다루는 정렬 리스트에서 검색하는 빠른 알고리즘은 

실행 시간에 대한 좋은 최악의 경우 보장을 가지고 있다. 

따라서 특정 응용 프로그램에서는 해시 테이블보다 더 선호될 수 있다. 

정렬된 탐색 테이블(ordered search table): 딕셔너리 D의 정렬된 배열 리스트 구현

그림 9.7: 정렬된 검색 테이블을 통해 딕셔너리 D를 구현한다. 

그들의 순서를 강조하기 위해 이 딕셔너리의 키만 보여준다.

 

정렬된 탐색 테이블의 공간 요구 사항은 O(n)이며, 

이는 리스트 기반 딕셔너리 구현(섹션 9.3.1)과 유사하다. 

그러나 정렬되지 않은 리스트와 달리 

탐색 테이블에서 업데이트를 수행하려면

상당한 시간이 소요된다. 

 

특히 k보다 큰 키로 배열 리스트의 모든 항목을 이동하여 

새 entry(k, v)을 위한 공간을 확보해야 하므로 

검색 테이블에서 insert(k, v) 연산을 수행하려면 

O(n) 시간이 필요하다.

 

K보다 큰 키로 배열 리스트의 모든 항목을 이동하여

제거된 항목(또는 항목)이 남긴 "구멍"을 닫는 데

O(n) 시간이 걸리기 때문에 

유사한 관찰이 연산 remove(k)에도 적용된다. 

 

따라서 탐색 테이블 구현은 

딕셔너리 업데이트 연산 중 최악의 경우 

실행 시간 측면에서 로그 파일보다 성능이 떨어진다. 

그럼에도 탐색 테이블에서 find 메소드를 훨씬 빠르게 수행할 수 있다.

이진 탐색

정렬된 배열 리스트 S를 사용하여 

n개의 원소를 갖는 딕셔너리 D를 구현할 때

얻을 수 있는 큰 이점은 

S의 원소를 인덱스(index)로 접근하는 데

O(1) 시간이 걸린다는 것이다. 

6.1절에서 배열 리스트에 있는 원소의 인덱스는 

앞에 있는 원소의 개수임을 기억한다. 

S의 첫 번째 원소의 인덱스: 0

S의 마지막 원소는 인덱스: n - 1

S에 저장된 요소는 딕셔너리 D의 항목이며, 

S의 순서가 매겨지므로 

인덱스 i의 항목은 인덱스 0,..., i - 1의 항목 키보다 작지 않고 

인덱스 i + 1,..., n - 1의 항목 키보다 작지 않은 키를 가진다. 

 

이러한 관찰을 통해 

어린이 게임 "high low"의 변형을 사용하여 

탐색 키 k에서 빠르게 "home in"할 수 있다. 

현재 검색 단계에서 

이 항목이 k와 동일한 키를 가지고 있다는 것을 배제할 수 없다면 

D의 항목을 후보라고 부른다. 

알고리즘은 low 및 high의 두 매개 변수를 유지하므로 

모든 후보 항목은 적어도 low = 0과 high = n - 1이다. 

그런 다음 k를 mid 후보 e의 키, 

즉 인덱스 e가 있는 항목 e와 비교한다
mid = (low + high)/2. 

우리는 세 가지 경우를 고려한다:
• k = e.getKey()인 경우 

찾고 있던 항목을 찾았고 탐색을 성공적으로 종료하면서 e를 반환한다.
• k < e.getKey()인 경우 

배열 리스트의 전반부, 

즉 low에서 mid - 1까지의 인덱스 범위에서 반복된다.
• k > e.getKey()인 경우 

mid+1에서 high까지의 인덱스 범위에서 반복된다.

이 검색 방법은 이진 탐색이라고 하며 

코드 조각 9.9에서 의사 코드로 제공된다. 

순서 배열 리스트 S로 구현된 n개의 엔트리 딕셔너리의 연산 find(k)는 

BinarySearch(S,k,0,n - 1)를 호출하는 것으로 구성된다.

코드 조각 9.9: 순서가 있는 배열 리스트에서 이진 검색.

Algorithm BinarySearch(S,k,low,high):

      Input: An ordered array list S storing n entries and integers low and high

      Output: An entry of S with key equal to k and index between low and high, if

          such an entry exists, and otherwise null

       if low > high then

           return null

       else

           mid ← ⌊(low + high)/2⌋

           e ← S.get(mid)

           if k = e.getKey() then

               return e

           else if k < e.getKey() then

               return BinarySearch(S,k,low,mid - 1)

           else

               return BinarySearch(S,k,mid + 1,high)

 

그림 9.8에서 이진 탐색 알고리즘을 설명한다.

 

그림 9.8: 

정수 키가 있는 딕셔너리에서 순서 배열 리스트로 구현된 

연산 find(22)를 수행하는 이진 탐색의 예. 

단순화를 위해 딕셔너리에 저장된 키를 보여주지만 

전체 항목은 보여주지 않는다.

 

이진 탐색의 실행 시간을 고려하면, 

BinarySearch 메소드의 재귀적 호출 시마다 

일정한 수의 원시 연산이 수행되는 것을 알 수 있다. 

따라서 실행 시간은 수행된 재귀적 호출의 수에 비례한다. 

결정적인 사실은 각 재귀적 호출 시 

배열 리스트 S에서 여전히 검색해야 할 후보 항목의 수는 값으로 주어진다는 것이다
high - low + 1.

또한 재귀적 호출을 할 때마다 

나머지 후보의 수는 적어도 절반으로 줄어든다. 

구체적으로, mid의 정의에서 볼 때, 

나머지 후보의 수는 다음 중 하나이다

아니면

처음에는 후보 엔트리의 수가 n이고, 

BinarySearch로 첫 번째 호출 후에는 최대 n/2, 

두 번째 호출 후에는 최대 n/4 등이다. 

일반적으로 BinarySearch로 i번째 호출 후에는 

남아 있는 후보 엔트리의 수가 최대 n/2^i이다. 

최악의 경우(검색에 실패함), 

후보 엔트리가 더 이상 없을 때 

재귀적 호출이 중지된다. 

따라서 재귀적 호출의 최대 수는 최소 정수 m이므로 다음과 같다
n/2m < 1.

즉, (로그의 밑이 2일 때 생략됨을 상기), 

m > logn 이므로
m= logn +1,
이는 이진 검색이 O(logn) 시간 내에 실행됨을 의미한다.

시간 O(logn + s)에서 

FindAll(k)를 수행하는 이진 탐색의 단순한 변형이 있다. 

(s: 반환된 반복자의 엔트리 수)

따라서 정렬된 탐색 테이블을 사용하여 

빠른 딕셔너리 탐색을 수행할 수 있지만, 

많은 딕셔너리 업데이트를 위해 이러한 테이블을 사용하는 것은 

상당한 시간이 소요된다. 

이러한 이유로 탐색 테이블의 주요 응용 프로그램은 

딕셔너리 업데이트가 거의 없을 것으로 예상되지만 탐색이 많은 상황이다.

예를 들어 백과사전이나 도움말 파일의 항목을 정렬할 때 

사용하는 정렬된 영어 단어 리스트에서 이러한 상황이 발생할 수 있다.

딕셔너리 구현 비교

표 9.3은 

정렬되지 않은 리스트, 해시 테이블 또는 정렬된 검색 테이블로 구현된 

딕셔너리의 메소드의 실행 시간을 비교한다. 

정렬되지 않은 리스트는 빠른 삽입은 가능하지만 

검색 및 제거는 느리다는 점에 주목하고, 

검색 테이블은 빠른 검색을 가능하게 하지만 

삽입 및 제거는 느리다는 점에 주목하자. 

덧붙여서, 명시적으로 논의하지는 않지만, 

이중 연결 리스트로 구현된 정렬된 리스트는 

거의 모든 딕셔너리 연산을 수행하는 데 

속도가 느리다는 점에 주목한다.

표 9.3: 정렬되지 않은 리스트, 해시 테이블 또는 

정렬된 검색 테이블을 통해 실현된 딕셔너리의 방식의 실행 시간 비교.

n은 딕셔너리의 엔트리 수, 

N은 해시 테이블 구현에서 버킷 배열의 용량, 

s는 findAll 연산에 의해 반환되는 컬렉션 크기를 나타낸다. 

해시 테이블과 검색 테이블 구현을 지원하는 배열이 

딕셔너리의 엔트리 수에 비례하도록 유지된다고 가정할 때 

모든 구현의 공간 요구 사항은 O(n)이다.

메소드	리스트	해시 테이블	탐색 테이블
size, isEmpty	O(1)	O(1)	O(1)
entries	O(n)	O(n)	O(n)
find	O(n)	O(1) exp., O(n) worst-case	O(logn)
findAll	O(n)	O(1 + s) exp., O(n) worst-case	O(logn + s)
insert	O(1)	O(1)	O(n)
remove	O(n)	O(1) exp., O(n) worst-case	O(n)

 

9.4 스킵 리스트

딕셔너리 ADT를 효율적으로 구현하기 위한 

흥미로운 자료 구조는 스킵 리스트(skip list)이다. 

탐색 및 업데이트 시간이 평균적으로 O(logn)이 되도록 

엔트리를 정렬하는 데 랜덤 선택을 수행한다.

여기서 n은 딕셔너리의 엔트리 수이다. 

흥미롭게도 여기서 사용된 평균 시간 복잡도의 개념은 

입력에 있는 키들의 확률 분포에 의존하지 않는다. 

대신 새로운 엔트리를 배치할 위치를 결정하는 데 도움이 되는 삽입 구현에서

난수 생성기의 사용에 의존한다. 

실행 시간은 엔트리를 삽입할 때

사용된 난수의 모든 가능한 결과에 대해 평균화된다.

컴퓨터 게임, 암호학, 컴퓨터 시뮬레이션 등에서 광범위하게 사용되기 때문에 

난수로 볼 수 있는 숫자를 생성하는 방법은 

대부분의 현대 컴퓨터에 내장되어 있다. 

의사난수 생성기(pseudorandom number)라고 불리는 어떤 방법들은 

시드라고 불리는 초기 숫자부터 결정론적으로 난수와 같은 숫자를 생성한다. 

다른 방법들은 하드웨어 장치를 사용하여 

자연으로부터 "진정한" 난수를 추출한다. 

어떤 경우든 우리는 컴퓨터가 분석을 위해 

충분히 난수인 숫자에 접근할 수 있다고 가정할 것이다.

자료 구조와 알고리즘 설계에서 무작위화(randomization)를 사용할 때의 가장 큰 이점은 

구조와 방법이 일반적으로 간단하고 효율적이라는 것이다. 

우리는 이진 탐색 알고리즘에 의해 달성되는 것과 동일한 로그 시간 한계를 갖는

스킵 리스트라고 불리는 간단한 무작위화된 자료 구조를 고안할 수 있다. 

그럼에도 불구하고, 

룩업 테이블에서 이진 탐색의 경우에는 최악의 경우 경계인 반면, 

스킵 리스트의 경우에는 경계가 예상된다. 

반면에, 스킵 리스트는 딕셔너리 업데이트를 위한 룩업 테이블보다 훨씬 빠르다.

딕셔너리 D에 대한 스킵 리스트 S: {S0, S1, ..., Sh}의 일련의 리스트로 구성된다. 

각 리스트 Si는 -∞ 및 +∞로 표시된 두 개의 특수 키와 함께 

감소하지 않는 키로 정렬된 D의 항목의 부분 집합을 저장한다.

 ( -∞는 D에 삽입될 수 있는 모든 키보다 작다. 

+∞는 D에 삽입될 수 있는 모든 키보다 크다.)

또한 S의 리스트는 다음을 만족한다:

• 리스트 S0에는 딕셔너리 D의 모든 항목

(그리고 키가 있는 특수 항목 - ∞ 및 + ∞)이 포함된다.

• i = 1, ..., h - 1의 경우,

list Si에는 ( - ∞ 및 + ∞ 외에도) 

list Si-1의 항목 중 임의로 생성된 부분 집합이 포함된다.
• 리스트 Sh에는 - ∞ 및 + ∞만 포함된다.

스킵 리스트의 예는 그림 9.9와 같다. 

스킵 리스트 S를 하단에 리스트 S0으로 시각화하고 

그 위에 S1,...,Sh를 나열하는 것이 일반적이다. 

또한, 우리는 스킵 리스트 S의 높이 h를 언급한다.

그림 9.9: 10개의 항목을 저장하는 스킵 리스트의 예이다. 

단순화를 위해 항목의 키만 보여준다.

직관적으로 리스트는

Si+1이 Si의 다른 모든 원소들을 어느 정도 포함하도록 설정된다. 

삽입 방법의 세부 사항에서 살펴보겠지만, 

Si+1의 원소들은 Si에서 각 원소들을 선택하여 

Si+1 안에 있는 원소들로부터 확률 1/2로 임의로 선택된다. 

즉, 본질적으로, 

Si의 각 원소에 대해 "동전을 뒤집고" 동전이 "머리"로 나온다면 

Si+1 안에 그 원소를 배치한다. 

따라서,

S1은 약 n/2개의 원소들을, 

S2는 약 n/4개의 원소들을, 

그리고 일반적으로

Si는 약 n/2i개의 원소들을 가질 것으로 예상한다. 

즉, S의 높이 h를 약 logn이라고 예상한다. 

그러나 한 리스트에서 다음 리스트로 원소들의 수를 절반으로 줄이는 것은 

스킵 리스트의 명시적인 속성으로 적용되지 않다. 

대신에, 임의화가 사용된다.

리스트와 트리에 사용된 위치 추상화를 사용하여, 

우리는 스킵 리스트를 수평으로 레벨(level) 안으로 

그리고 수직으로 탑(tower) 안으로 배열된 위치들의 2차원 집합으로 본다. 

각 수준은 리스트 Si이고 

각 탑은 연속된 리스트에서 동일한 항목을 저장하는 위치들을 포함한다. 

스킵 리스트의 위치들은 다음 연산을 통해 탐색될 수 있다:

next(p): 같은 레벨에 있는 p의 위치를 반환한다.
prev(p): p 앞에 있는 위치를 같은 레벨로 되돌린다. 
below(p): 같은 탑의 p 아래 위치를 반환한다. 
above(p): p위의 위치를 같은 타워로 되돌린다.

저희는 일반적으로 위의 연산은 요청한 위치가 존재하지 않는 경우 Null 위치를 반환한다고 가정한다. 

자세한 내용을 설명하지 않고 

위의 순회 방법은 스킵 리스트 위치 p가 주어졌을 때 

각각 O(1) 시간이 걸리도록 연결된 구조를 통해 쉽게 스킵 리스트를 구현할 수 있다. 

이러한 연결된 구조는 기본적으로 타워에 정렬된 h개의 이중 연결 리스트의 컬렉션이며, 

이 또한 이중 연결 리스트이다.

9.4.1 스킵 리스트에서 검색 및 업데이트 연산

스킵 리스트 구조는 간단한 딕셔너리 탐색 및 업데이트 알고리즘을 가능하게 하다. 

사실, 모든 스킵 리스트 탐색 및 업데이트 알고리즘은 k 키를 가지고 

리스트 S0에서 가장 큰 키(아마도 - ∞)를 가질 수 있도록 

엔트리 e의 위치 p를 찾는 우아한 SkipSearch 메소드를 기반으로 한다.

스킵 리스트에서 탐색

우리에게 탐색 키 k가 주어졌다고 가정하자.

우리는 S의 시작 위치라고 불리는 스킵 리스트 S에서 

위치 변수 p를 맨 위 왼쪽 위치로 설정함으로써 

SkipSearch 메소드를 시작한다. 

시작 위치(start position): key - ∞로 특별한 엔트리를 저장하는 Sh의 위치

그런 다음 다음 다음 단계를 수행한다(그림 9.10 참조). 

여기서 key(p)는 p 위치에 있는 엔트리의 키를 나타낸다:

1. S. below(p)이 null이면 탐색이 종료된다. 

탐색 키 k보다 작거나 같은 키로 

S에서 가장 큰 엔트리를 찾았고 맨 아래에 있다. 

그렇지 않으면 p ← s. below(p)를 설정하여 

현재 타워에서 다음 하위 레벨로 떨어진다(drop down).

2. 스캔 전진(scan forward) 단계:

위치 p에서 시작해서 키(p) ≤ k가 되도록 

현재 레벨의 가장 오른쪽에 있을 때까지 앞으로 나아간다. 

각 레벨에는 + ∞와 - ∞ 키가 포함되어 있기 때문에 

이러한 위치는 항상 존재한다는 것을 주목하자. 

사실 이 레벨에 대해 스캔 전진을 수행한 후에 

p는 시작된 곳에 남아 있을 수 있다. 

어떤 경우든 우리는 이전 단계를 반복한다.

그림 9.10: 스킵 리스트에서 탐색 예시. 

키 50을 검색할 때 방문한 위치는 파란색으로 강조 표시된다.

코드 조각 9.10의 스킵 리스트 검색 

알고리즘 SkipSearch에 대한 의사 코드 설명을 제공한다. 

이 메소드를 사용하면 

간단히 p ← SkipSearch(k)를 수행하고 

key(p) = k 여부를 테스트하는 find(k) 연산을 쉽게 구현할 수 있다. 

이 두 키가 동일하면 p를 반환하고,

그렇지 않으면 null을 반환한다.

코드 조각 9.10: 

S의 시작 위치를 S 변수가 유지한다.

Algorithm SkipSearch(k):

      Input: A search key k

      Output: Position p in the bottom list S0 such that the entry at p has the largest

         key less than or equal to k

       p ← s

       while below(p) ≠ null do

           p ← below(p)                {drop down}

           while k ≥ key(next(p)) do

                p ←next(p)                {scan forward}

       return p

알고 보니 n개의 항목이 있는 스킵 리스트에서

알고리즘 SkipSearch의 예상 실행 시간은 O(logn)이다. 

하지만 이 사실의 정당성에 대해서는 

스킵 리스트의 업데이트 메소드의 구현에 대해 논의한 후로 미루겠다.

 

스킵 리스트에 삽입

스킵 리스트의 삽입 알고리즘은 랜덤화를 사용하여 새 엔트리의 탑 높이를 결정한다. 

SkipSearch(k) 연산을 수행하여 새로운 엔트리 (k,v)의 삽입을 시작한다. 

이것은 가장 큰 키가 k보다 작거나 같은 하위 엔트리의 위치 p를 우리에게 준다

(p는 키 - ∞로 특별한 엔트리를 보유할 수 있음을 유의하자). 

그리고 나서 p 위치 바로 뒤에 (k,v)를 삽입한다. 

하단에 새로운 엔트리를 삽입한 후에, 동전을 "플립"한다. 

만약 플립이 꼬리로 올라오면, 여기서 멈춘다. 

그렇지 않으면(플립이 머리로 올라와), 

이전 레벨(다음 높은 레벨)로 돌아가서 적절한 위치에 (k,v)를 삽입한다. 

동전을 다시 뒤집는다; 만약 머리로 올라오면, 다음 높은 레벨로 가서 반복한다. 

따라서, 마침내 꼬리로 올라오는 플립을 얻을 때까지 

리스트에 새로운 엔트리 (k,v)를 계속 삽입한다. 

이 과정에서 생성된 새로운 엔트리 (k,v)에 대한 모든 참조를 함께 연결하여 

새로운 엔트리의 탑을 만든다. 

코인 플립은 자바의 내장된 의사 난수 생성기 java.util.Random을 사용하여 시뮬레이션할 수 있으며, 

nextInt(2)를 호출하여 각각 1/2의 확률로 0을 반환한다.

코드 조각 9.11에 스킵 리스트 S에 대한 삽입 알고리즘을 제시하고 그림 9.11에 이를 설명한다.

알고리즘은 위치 p(p와 동일한 레벨)와 위치 q 위에 

엔트리(k, v)를 저장하는 위치를 삽입하고 

새 엔트리의 위치 r을 반환하며

(그리고 p, q, r에 대해 prev, 위, 아래 메소드가 올바르게 작동하도록 내부 참조를 설정),

 

알고리즘은 메소드 insertAfterAbove(p, q, (k, v))를 사용하여

위치 p(p와 동일한 레벨)와 위치 q 위에 엔트리(k, v)를 저장하는 위치를 삽입하고,

새로운 엔트리의 위치 r을 반환한다

(그리고 next, prev, above, below 메소드가

p, q, r에 대해 올바르게 작동하도록 내부 참조를 설정한다).

 n개의 엔트리가 포함된 스킵 리스트에서 삽입 알고리즘의 예상 실행 시간은 O(logn)이며, 

이는 9.4.2절에서 보여준다.

코드 조각 9.11: 스킵 리스트에 삽입. 

메소드 coinFlip()은 각각 1/2 확률로 "헤드" 또는 "테일"을 반환한다. 

변수 n, h 및 s는 스킵 리스트의 엔트리 수, 높이 및 시작 노드를 보유한다.

Algorithm SkipInsert(k,v):

      Input: Key k and value v

      Output: Entry inserted in the skip list

       p ← SkipSearch(k)

       q ← insertAfterAbove(p,null,(k,v))                {we are at the bottom level}

       e ← q.element()

       i ← 0

       while coinFlip() = heads do

           i ← i + 1 

           if i ≥ h then

                h ← h + 1                {add a new level to the skip list}

                t ← next(s)

                s ← insertAfterAbove(null,s,(-∞,null)) 

                insertAfterAbove(s,t(+∞,null)) 

           while above(p) = null do

                p ← prev(p)              {scan backward}

           p ← above(p)              {jump up to higher level}

           q ← insertAfterAbove(p,q,e)   {add a position to the tower of the new entry}

       n ← n + 1 

       return e

그림 9.11: 키가 42인 항목을 그림 9.9의 스킵 리스트에 삽입한다. 

우리는 새로운 항목에 대한 임의의 "동전 뒤집기"가 

세 번 연속으로 머리 위로 올라왔고, 

꼬리가 그 뒤를 따랐다고 가정한다. 

방문한 위치는 파란색으로 강조 표시된다. 

새로운 항목을 유지하기 위해 

삽입된 위치는 굵은 선으로 그려지고, 

그 앞에 있는 위치는 플래그로 표시된다.

 

스킵 리스트에서 제거

탐색 및 삽입 알고리즘과 마찬가지로 

스킵 리스트에 대한 제거 알고리즘은 매우 간단하다. 

사실 삽입 알고리즘보다 훨씬 쉽다. 

즉, remove(k) 작업을 수행하기 위해 

메소드 SkipSearch(k)를 실행하는 것으로 시작한다. 

만약 위치 p가 k와 다른 키를 가진 엔트리를 저장하고 있다면 null을 반환한다. 

그렇지 않으면 above 연산을 통해 

쉽게 접근할 수 있는 p 및 p 위의 모든 위치를 제거하고 

위치 p에서 시작하는 S의 엔트리의 탑을 올라간다. 

제거 알고리즘은 그림 9.12에 나와 있다.

다음 하위 섹션에서 보여주는 것처럼, 

n개의 엔트리를 가진 스킵 리스트의 remove 연산은 O(logn) 예상 실행 시간을 갖는다.

그러나 이 분석을 하기 전에 먼저 논의하고자 하는 

스킵 리스트 자료 구조에 약간의 개선 사항이 있다. 

1. 항목에 대한 참조는 bottom 레벨 이상의 스킵 리스트 수준에 저장할 필요가 없다. 

2. above 메소드가 실제로 필요하지 않는다. 

사실, 딕셔너리 메소드도 필요하지 않는다. 

항목 삽입 및 제거를 top-down, scan-forward 방식으로 수행할 수 있으므로 

"up" 및 "prev" 참조를 위한 공간을 절약할 수 있다. 

이러한 최적화는 모두 스킵 리스트의 점근적 성능을 상수 이상으로 향상시키지는 않지만 

실제로는 이러한 개선 사항이 의미가 있다. 

실제로 실험적 증거에 따르면 

최적화된 스킵 리스트는 

10장에서 설명한 AVL 트리 및 기타 균형 검색 트리보다 실제로 더 빠르다.

제거 알고리즘의 예상 실행 시간은 O(logn)이며, 이는 섹션 9.4.2에 나와 있다.

그림 9.12: 그림 9.11의 스킵 리스트에서 키 25가 있는 항목을 제거한다.

S0의 위치를 검색한 후에 방문한 위치는 파란색으로 강조 표시된다. 

제거된 위치는 점선으로 그린다.

최상위 레벨 유지

스킵 리스트 S는 시작 위치(S에서 최상위, 왼쪽 위치)에 대한 참조를 인스턴스 변수로 유지해야 하며, 

S의 최상위 레벨을 지나 새 항목을 계속 삽입하려는 삽입에 대한 정책이 있어야 한다. 

우리가 취할 수 있는 조치는 두 가지 가능한 과정이며, 두 가지 모두 장점이 있다.

1. 한 가지 가능성은 최상위 레벨인 h를 n의 함수인 고정된 값, 

현재 딕셔너리에 있는 항목 수로 유지하는 것이다

(분석을 통해 h = max{ 10,2 log n}가 합리적인 선택이며 

h = 3 logn을 선택하는 것이 훨씬 더 안전하다는 것을 알 수 있다). 

이 선택을 구현하면 최상위 레벨에 도달하면 

삽입 알고리즘을 수정하여 새 위치 삽입을 중지해야 한다

(logn < log(n + 1)가 아닌 경우 높이의 경계가 증가하므로 

이 경우 이제 적어도 한 단계 더 올라갈 수 있다).

2. 다른 가능성은 난수 생성기에서 헤드들이 계속 돌아오는 한

삽입이 새로운 위치를 계속 삽입하도록 하는 것이다. 

이것은 코드 조각 9.11의 알고리즘 SkipInsert에서 취한 접근법이다. 

우리가 스킵 리스트 분석에서 보여주듯이,

삽입이 O(logn)보다 높은 수준으로 갈 확률은 매우 낮으므로, 

이 설계 선택도 역시 효과가 있을 것이다.

두 가지 중 하나를 선택해도 

검색, 삽입 및 제거를 수행하는 데

예상되는 O(logn) 시간이 발생하지만 

다음 섹션에서 이를 보여준다.

9.4.2 스킵 리스트의 확률적 분석

위에서 보여준 것처럼 스킵 리스트는 정렬된 딕셔너리의 간단한 구현을 제공한다. 

그러나 최악의 경우 성능 면에서 스킵 리스트는 우수한 자료 구조가 아니다. 

사실, 공식적으로 현재 최고 레벨을 훨씬 넘어

삽입이 계속되는 것을 막지 않으면 

삽입 알고리즘은 거의 무한 루프에 들어갈 수 있다. 

하지만 공정한 동전이 영원히 반복적으로 떠오를 확률은 0이기 때문에

실제로는 무한 루프가 아니다. 

게다가, 우리는 결국 메모리가 부족하지 않고는 

무한히 위치를 리스트에 추가할 수 없다. 

어쨌든, 가장 높은 레벨 h에서 위치 삽입을 종료하면 

n개의 항목과 높이 h를 가진 스킵 리스트 S에서

find, insert, remove 연산을 수행하는 최악의 경우 실행 시간은 O(n + h)이다. 

이 최악의 경우의 성능은 모든 항목의 탑이 S의 높이인 레벨 h-1에 도달할 때 발생한다. 

그러나 이 이벤트는 매우 낮은 확률을 가지고 있다. 

이 최악의 경우로 미루어 볼 때, 

스킵 리스트 구조가 이 장에서 앞서 설명한 다른 딕셔너리 구현보다

엄격하게 열등하다고 결론지을 수 있다. 

그러나 이 최악의 경우의 행동은 엄청난 과대평가이기 때문에 이것은 공정한 분석이 될 수 없다.

 

스킵 리스트 높이 제한

삽입 단계는 무작위화를 포함하기 때문에

스킵 리스트를 보다 정확하게 분석하려면 약간의 확률이 필요하다. 

처음에는 완전하고 철저한 확률론적 분석을 위해서는

깊은 수학이 필요하기 때문에

이것은 주요 연산처럼 보일 수 있다. 

다행히도 이러한 분석은 스킵 리스트의 예상되는 점근적 행동을 이해하는 데 필요하지 않다. 

아래에서 제공하는 비공식적이고 직관적인 확률론적 분석은 확률 이론의 기본 개념만을 사용한다.

n개의 원소를 가진 스킵 리스트 S의 높이 h의 기대값을 구하는 것으로 시작하겠다. 

(주어진 원소가 높이 i ≥ 1의 탑을 가질 확률)

= (동전을 뒤집을 때 연속적으로 i개의 개수를 가질 확률)

= 1/(2^i)

따라서 레벨 i가 적어도 하나의 위치를 가질 확률 PiP는 많아야 한다
Pi ≤ n/(2^i),
n개의 서로 다른 사건 중 하나가 발생할 확률은 각각 발생할 확률의 합이다.

S의 높이 h가 i보다 클 확률은 

레벨 i가 적어도 하나의 위치를 가질 확률, 

즉 Pi보다 크지 않을 확률과 같다. 

이것은 h가 많아야 확률이 3 logn보다 크다는 것을 의미한다
P(3logn) ≤ n/(2^(3 log n))= n/(n^3) = 1/(n^2).

예를 들어, n = 1000이면 이 확률은 백만 분의 일의 장타이다. 

더 일반적으로 상수 c > 1이 주어지면 h는 c log n보다 크며, 최대 1/(n^(c-1))의 확률이다. 

즉, h가 c log n보다 작을 확률은 적어도 1 - 1/(n^(c-1))이다. 

따라서, 높은 확률로 S의 높이 h는 O(logn)이다.

스킵 리스트에서 탐색 시간 분석

다음으로, 스킵 리스트 S에서 탐색의 실행 시간을 고려하고, 

그러한 검색은 두 개의 중첩된 while 루프를 포함한다는 것을 기억하자. 

내부 루프는 다음 키가 탐색 키 k보다 크지 않은 한 S 레벨에서 순방향으로 스캔을 수행하고,

외부 루프는 다음 레벨로 하강하여 순방향으로 스캔을 반복한다. 

S의 높이 h는 확률이 높은 O(logn)이므로 

드롭다운 단계의 수는 확률이 높은 O(logn)이다.

따라서 우리는 아직 스캔 포워드 단계의 수를 제한하지 않았다. 

ni를 레벨 i에서 스캔 포워드 되는 동안 검사되는 키의 수라 하자. 

시작 위치에 있는 키 다음에, 

레벨 i에서 스캔 포워드 되는 각각의 추가 키도 

레벨 i+1에 속할 수 없음을 관찰하자. 

만약 이 키들 중 하나가 이전 레벨에 있었다면, 

우리는 이전 스캔 포워드 단계에서 키들을 접했을 것이다. 

임의의 키가 ni로 계산될 확률 = 1/2 

ni의 기대값 = 공정한 동전이 떠오르기 전에 뒤집어야 하는 기대 횟수

이 기대값은 2이다. 

따라서, 임의의 레벨 i에서 스캔 포워드 되는 기대 시간은 O(1)이다.

 

S는 높은 확률로 O(logn) 수준을 가지므로, 

S에서의 탐색은 예상 시간 O(logn)이 소요된다. 

비슷한 분석을 통해 삽입 또는 제거의 예상 실행 시간이 O(logn)임을 보여줄 수 있다.

스킵 리스트의 공간 사용량

마지막으로 n개의 원소를 갖는 스킵 리스트 S의 공간 요구 사항을 살펴보자. 

위에서 관측한 바와 같이, 

레벨 i에서의 기대되는 위치의 수는 n/2i이며, 

이는 S에서의 기대되는 총 위치의 수는 다음과 같다

기하학적 총합에 대한 명제 4.5를 사용하여, 모든 h ≥ 0에 대하여

따라서 S의 예상 공간 요구량은 O(n)이다.

표 9.4는 스킵 리스트로 구현된 딕셔너리의 성능을 정리한 것이다. 

표 9.4: 스킵 리스트로 구현된 딕셔너리의 성능이다. 

n: 연산이 수행될 때 딕셔너리의 엔트리 수

s: 연산으로 반환된 컬렉션의 크기

예상 공간 요구 사항: O(n)

연산	시간
size, isEmpty	O(1)
entries	O(n)
find, insert, remove	O(log n) (expected)
findAll	O(log n + s) (expected)

 

9.5 딕셔너리의 확장 및 적용

이 섹션에서는 딕셔너리의 여러 확장 및 응용에 대해 알아본다.

9.5.1 위치 인식 딕셔너리 항목 지원

또한 우선 순위 큐(8.4.2절)에서와 같이 위치 인식 항목을 사용하여 

딕셔너리의 일부 연산에 대한 실행 시간을 단축할 수 있다. 

특히 위치 인식 항목을 사용하면 

딕셔너리에서 항목 제거 속도를 크게 높일 수 있다. 

위치 인식 항목 e를 제거하려면 

자료 구조에서 e를 저장하고 있는 위치로 직접 이동하여 제거할 수 있다. 

예를 들어 private location 변수와 protectec 메소드인 location() 및 setLocation(p)로 엔트리 클래스를 확장하면 

위치 인식 항목을 구현할 수 있으며, 이 변수를 반환하고 설정할 수 있다. 

그런 다음 항목 e의 location 변수는 항상 딕셔너리를 구현하는 자료 구조에서 e의 위치 또는 인덱스를 참조해야 한다. 

물론 항목을 이동할 때마다 이 변수를 업데이트해야 하므로 

이 엔트리 클래스가 딕셔너리를 구현하는 클래스와 밀접하게 관련되는 것이 가장 합리적일 것이다. 

아래에서는 이 장에서 설명하는 여러 자료 구조에 대한 위치 인식 항목을 설정하는 방법을 보여 준다.

• 정렬되지 않은 리스트: 

정렬되지 않은 리스트인 L에서 딕셔너리를 구현하면 

각 항목 e의 location 변수를 유지하여 L에 대한 기본 연결 리스트에서 e의 위치를 지정할 수 있다. 

이 선택을 통해 L.remove(e.location())로 remove(e.location())를 수행할 수 있으며, 

이는 O(1) 시간 내에 실행된다.

• 별도의 체이닝을 갖는 해시 테이블 : 

충돌을 처리하기 위해 별도의 체이닝을 사용하는 

버킷 배열 A와 해시 함수 h를 갖는 해시 테이블을 생각해 보자. 

미니맵 A[h(k)]를 구현하는 리스트 L에서 e의 위치를 가리키기 위해 

각 엔트리 e의 location 변수를 사용한다.

 

이 옵션을 사용하면 

L.remove(e.location())와 같이 일정한 예상 시간 내에 실행되는

remove(e)의 주요 작업을 수행할 수 있다.

• 정렬된 탐색 테이블: 

딕셔너리를 구현하는 순서표 T에서, 

각 엔트리 e의 location 변수를 T의 인덱스로 유지해야 한다. 

이 선택은 T.remove(e.location()로 remove(e.location))를 수행할 수 있게 해준다. 

(그 location()는 이제 정수를 반환한다.) 

만약 엔트리 e가 T의 끝 근처에 저장되어 있다면 이 접근법은 빠르게 실행될 것이다.

• 스킵 리스트: 

딕셔너리를 구현하는 스킵 리스트 S에서 

S의 하단 레벨에서 e의 위치를 가리키기 위해 

각 항목 e의 location 변수를 유지해야 한다. 

이 선택을 통해 스킵 리스트에서 remove(e)를 수행하는 알고리즘의 탐색 단계를 건너뛸 수 있다.

표 9.5에 위치 인식 항목이 있는 딕셔너리에서 항목 제거 성능을 요약한다.

표 9.5: 위치 인식 항목으로 구현된 딕셔너리에서 remove 메소드의 성능. 

n: 딕셔너리의 항목의 수

리스트	해시 테이블	탐색 테이블	스킵 리스트
O(1)	O(1) (예상)	O(n)	O(logn)(예상)

 

9.5.2 정렬된 딕셔너리 ADT

정렬된 딕셔너리에서 우리는 일반적인 딕셔너리 연산을 수행할 뿐만 아니라 

우리의 딕셔너리에 있는 키들에 대해서도 순서 관계를 유지하고자 한다. 

위에서 설명한 정렬된 탐색 테이블과 스킵 리스트 딕셔너리 구현에서 했던 것처럼 

우리는 comparator를 사용하여 키들 간의 순서 관계를 제공할 수 있다. 

실제로 10장에서 설명한 모든 딕셔너리 구현은 comparator를 사용하여 

키가 감소하지 않는 순서로 딕셔너리를 저장한다.
딕셔너리의 항목들이 순서대로 저장될 때, 

우리는 딕셔너리 ADT에서 추가적인 방법들에 대한 효율적인 구현을 제공할 수 있다. 

예를 들어, 우리는 정렬된 딕셔너리(ordered dictionary) ADT를 정의하기 위해

딕셔너리 ADT에 다음과 같은 방법들을 추가하는 것을 고려할 수 있다.

first( ): 가장 작은 키로 항목을 반환한다. 
last(): 키가 가장 큰 항목을 반환한다.
successors(k): 키가 k 이상인 항목의 반복자를 감소하지 않는 순서로 반환한다.
predecessors(k): 키가 k보다 작거나 같은 항목의 반복자를 증가하지 않는 순서로 반환한다.

정렬된 딕셔너리 구현

위의 연산들의 정렬된 특성 때문에 

정렬되지 않은 리스트나 해시 테이블을 사용하는 것은 딕셔너리 구현에 부적절하다. 

실제로 해시 테이블은 키가 거의 무작위로 분포될 때 최상의 검색 속도를 달성한다. 

따라서 정렬된 딕셔너리를 다룰 때 

정렬된 탐색 테이블이나 스킵 리스트(또는 10장의 자료 구조)을 고려해야 한다.

예를 들어, 스킵 리스트를 사용하여 정렬된 딕셔너리를 구현하면 

맨 아래 리스트의 두 번째 위치와 두 번째 위치에서 마지막 위치에 액세스하여 

O(1) 시간에 first()와 last() 메소드를 구현할 수 있다. 

또한 메소드 successors(k)와 메소드 predecessors(k)를

O(logn) 예상 시간에 실행하도록 구현할 수 있다.

 

또한 successors(k) 메소드와 메소드 predecessors(k)에서 반환되는 반복자는 

스킵 리스트의 맨 아래 수준에서 현재 위치에 대한 참조를 사용하여 구현할 수 있다. 

따라서 이러한 반복자의 hasNext 메소드와 next 메소드는 

각각 이 접근 방식을 사용하여 일정한 시간에 실행된다.

java.util.Sorted 맵 인터페이스

Java는 java.util.SortedMap이라는 인터페이스에서 

java.util.Map 인터페이스의 정렬된 버전을 제공한다. 

이 인터페이스는 순서를 고려한 메소드로 java.util.Map 인터페이스를 확장한다. 

SortedMap은 상위 인터페이스와 마찬가지로 중복 키를 허용하지 않다.

딕셔너리가 동일한 키로 여러 항목을 허용한다는 사실을 무시하고, 

정렬된 딕셔너리 ADT의 메소드와

인터페이스 java.util.SortedMap의 메소드 간의 가능한 대응은 표 9.6에 나와 있다.

표 9.6: 정렬된 딕셔너리 ADT의 메소드와 

다른 메소드도 지원하는 java.util.SortedMap 인터페이스의 메소드 간에 느슨한 대응 관계가 있다. 

그러나 메소드 predecessors(k)에 대한 java.util.SortedMap 표현은 정확한 대응 관계가 아니다. 

그러나 반환되는 반복자는 키를 증가시켜 

k와 같은 키를 가진 항목을 포함하지 않기 때문에 

메소드 predecessors(k)에 대한 진정한 대응 관계를 얻는 효율적인 방법은 없는 것으로 보인다.

 

정렬된 딕셔너리 메소드	java.util.SortedMap 메소드
first().getKey()	firstKey()
first().getValue()	get(firstKey())
last().getKey()	lastKey()
last().getValue()	get(lastKey())
successors(k)	tailMap(k).entrySet().iterator()
predecessors(k)	headMap(k).entrySet().iterator()

 

9.5.3 비행 데이터베이스 및 Maxima 세트

앞 절에서 언급했듯이 정렬되지 않은 딕셔너리와 정렬된 딕셔너리에는 많은 응용이 있다.
이 섹션에서는 정렬된 딕셔너리의 몇 가지 특정 응용 분야를 살펴본다.

 

비행 데이터베이스

인터넷상에는 항공권을 구매할 목적으로 

다양한 도시 간의 항공편을 찾기 위해 

항공편 데이터베이스에서 쿼리를 수행할 수 있는 여러 웹 사이트가 있다. 

사용자는 쿼리를 수행하기 위해

출발지와 도착지 도시, 출발 날짜, 출발 시간을 지정한다. 

이러한 쿼리를 지원하기 위해 

항공편 데이터베이스를 딕셔너리로 모델링할 수 있으며, 

여기서 키는 이 네 가지 매개 변수에 해당하는 필드를 포함하는 Flight 객체이다. 

즉, 키는 튜플(tuple)이다
k = (origin, destination, date, time).

항공편 번호, 퍼스트(F) 및 코치(Y) 클래스에 남아 있는 좌석 수, 

운항 기간 및 요금 등 항공편에 대한 추가 정보를 값 객체에 저장할 수 있다.

하지만 단순히 딕셔너리에서 요청된 질문에 맞는 키를 찾는 것이 아니라, 

요청된 항공편을 찾는 것이 가장 큰 문제이다. 

가장 큰 어려움은 사용자가 보통 출발지와 도착지 도시, 출발일을 정확히 맞추기를 원하지만, 

요청된 출발 시간에 가까운 출발 시간이면 만족할 수 있다는 것이다.

 

물론 키를 사전적으로 정렬하여 이러한 쿼리를 처리할 수 있다. 

따라서 사용자 쿼리 키 k가 주어지면 

원하는 날짜에 원하는 도시 간의 모든 항공편을 요청한 출발 시간보다

엄격하게 증가하는 순서로 반복하여 반환하기 위해

successor(k)를 호출할 수 있다. 

predecessors(k)를 유사하게 사용하면 

요청한 시간 이전에 시간이 있는 항공편을 제공할 수 있다. 

따라서 정렬된 딕셔너리를 효율적으로 구현하는 것, 

예를 들어 스킵 리스트를 사용하는 것이

이러한 쿼리를 충족하는 좋은 방법이 될 것이다. 

 

예를 들어 쿼리 키 k = (ORD, PVD, 05 May, 09:30)에서 successor(k)를 호출하면 

다음과 같은 항목이 반복될 수 있다:
((ORD, PVD, 05May, 09:53), (AA 1840, F5, Y15, 02:05, $251))
((ORD, PVD, 05May, 13:29), (AA 600, F2, Y0, 02:16, $713))
((ORD, PVD, 05May, 17:39), (AA 416, F3, Y9, 02:09, $365))
((ORD, PVD, 05May, 19:50), (AA 1828, F9, Y25, 02:13, $186))

최대  집합

인생은 상충 관계로 가득 차 있다. 

우리는 종종 원하는 성능 척도를 그에 상응하는 비용과 교환해야 한다. 

 

예를 들어, 자동차의 최고 속도와 비용으로 평가하는

데이터베이스를 유지하는 데 관심이 있다고 가정해보자. 

일정 금액을 가진 사람이 데이터베이스를 조회하여

그들이 살 수 있는 가장 빠른 차를 찾을 수 있도록 하고 싶다.

키-값 쌍을 사용하여 서로 교환하는 두 모수를 모형화함으로써 

이러한 상충 문제를 모형화할 수 있는데, 이 경우 각 차의 쌍(cost, speed)이 된다. 

이 척도를 사용하는 다른 차들보다 어떤 차들은 엄밀하게 더 낫다. 

예를 들어, 비용-속도 쌍(20,000, 100)을 가진 차가 비용-속도 쌍(30,000, 90)을 가진 차보다 엄밀하게 낫다. 

동시에, 엄밀하게 다른 차에 의해 지배되지 않는 차들도 있다. 

예를 들어, 비용-속도 쌍(20,000, 100)을 가진 차가 비용-속도 쌍(300,000,120)을 가진 차보다 

얼마나 많은 돈을 써야 하는지에 따라 더 나을 수도 있고 더 나쁠 수도 있다. (그림 9.13 참조)

그림 9.13: 평면에 점으로 표시된 키-값 쌍을 사용한 비용-성능 절충을 보여준다. 

점 p는 c, d, e보다 엄밀하게 낫지만, 

지불하고자 하는 가격에 따라 점 a, b, f, g, h보다 낫거나 나쁠 수 있다. 

따라서 집합에 p를 더한다면 c, d, e는 제거할 수 있지만 다른 점들은 제거할 수 없다.

형식적으로, a < c 와 b > d 일 때,

가격 대비 성능 쌍 (a, b) 가 쌍 (c, d) 를 지배한다(dominate)고 한다. 

쌍 (a, b) 가 다른 쌍에 의해 지배되지 않으면 최대(maximum) 쌍이라고 한다. 

가격 대비 성능 쌍의 집합 C 의 최대(maxima) 집합을 유지하는 데 관심이 있다. 

즉, 이 집합에 새로운 쌍을 추가하고

(예를 들어, 새 차가 출시될 때), 

d 달러 이하의 가장 빠른 차를 찾기 위해 

주어진 달러 금액 d 에 대해 이 집합을 조회하고자 한다.

 

최대 쌍의 집합을 비용별로 정렬된 딕셔너리 D에 저장하여 

비용이 핵심 필드이고 성능(속도)이 값 필드가 되도록 할 수 있다. 

그런 다음 코드 조각 9.12와 같이 

새로운 비용-성능 쌍(c,p)을 추가하는 add(c,p)와 

비용이 많이 드는 최상의 쌍을 반환하는 best(c)를 구현할 수 있다.

코드 조각 9.12: 정렬된 딕셔너리 D로 구현된 최대 집합을 유지하는 메소드.

Algorithm best(c):

      Input: A cost c

      Output: The cost-performance pair in D with largest cost less than or equal to

          c or null if there is no such pair

       B ← D.predecessors(c)

       if B.hasNext() then

            return B.next()         {the first entry in the predecessors iterator}

       else

            return null

Algorithm add(c,p):

      Input: A cost-performance pair (c,p)

      Output: None

       B ← D.predecessors(c)              {iterator of pairs with cost at most c}

       if B.hasNext() then

           e ← B.next()                {predecessor of c}

           if e.getValue() > p then

                return                { (c, p) is dominated, so don't insert it in D}

           C ← D.successors(c)             {iterator of pairs with cost at least c}

           while C.hasNext() do

                e ← C.next()              {successor of c}

                if e.getValue() > p then

                   D.remove(e)             {this pair is dominated by (c, p)}

                else      

                  break from this while loop   {no more pair is dominated by (c, p)}

       D.insert(c,p)            {Add the pair (c, p), which is not dominated}

스킵 리스트를 사용하여 D를 구현하면 

O(logn) 예상 시간에 best(c) 쿼리를 수행하고 

O((1 + r)logn) 예상 시간에 add(c,p) 업데이트를 수행한다.
(r: 제거된 점의 수)

따라서 최대 집합을 유지하는 메소드에 대해 좋은 실행 시간을 얻을 수 있다.