스킵 리스트

스킵 리스트
스킵 리스트
종류	리스트
발명일	1989
발명자	W. 푸
점근표기법으로 된 시간복잡도
알고리즘
알고리즘
공간
탐색
삽입
삭제

컴퓨터 과학에서 스킵 리스트(skip list) 또는 스킵리스트(skiplist)는 $n$ 개의 요소로 구성된 정렬된 시퀀스 내에서 탐색에 대해 ${\mathcal {O}}(\log n)$ 평균 복잡도를, 삽입에 대해 ${\mathcal {O}}(\log n)$ 평균 복잡도를 허용하는 확률적 자료 구조이다. 따라서 정렬된 배열의 가장 좋은 기능(탐색용)을 얻으면서, 정적 배열로는 불가능한 삽입을 허용하는 연결 리스트와 유사한 구조를 유지할 수 있다. 빠른 탐색은 하위 시퀀스의 연결된 계층 구조를 유지함으로써 가능하며, 각 연속적인 하위 시퀀스는 이전 시퀀스보다 더 적은 요소를 건너뛴다(아래 그림 참조). 탐색은 가장 희소한 하위 시퀀스에서 시작하여, 탐색 중인 요소보다 작거나 같거나 큰 두 개의 연속적인 요소를 찾을 때까지 계속된다. 연결된 계층 구조를 통해 이 두 요소는 다음으로 희소한 하위 시퀀스의 요소에 연결되며, 최종적으로 전체 시퀀스에서 탐색이 끝날 때까지 탐색이 계속된다. 건너뛰는 요소는 확률적으로 선택될 수도 있고^[2] 결정론적으로 선택될 수도 있지만,^[3] 전자가 더 일반적이다.

설명

스킵 리스트는 여러 계층으로 구성된다. 가장 아래 계층 $1$ 은 일반적인 정렬된 연결 리스트이다. 각 상위 계층은 아래 리스트에 대한 "고속 차선" 역할을 하며, 계층 $i$ 의 요소는 특정 고정 확률 $p$ (일반적으로 $1/2$ 또는 $1/4$ )로 계층 $i+1$ 에 나타난다. 평균적으로 각 요소는 $1/(1-p)$ 개의 리스트에 나타나며, 가장 높은 요소(일반적으로 스킵 리스트의 맨 앞에 있는 특수 헤드 요소)는 모든 리스트에 나타난다. 스킵 리스트는 $\log _{1/p}n\,$ (즉, $n$ 의 $1/p$ 를 밑으로 하는 로그)개의 리스트를 포함한다.

대상 요소를 탐색하는 것은 최상위 리스트의 헤드 요소에서 시작하여, 현재 요소가 대상보다 크거나 같을 때까지 수평으로 진행된다. 현재 요소가 대상과 같으면 발견된 것이다. 현재 요소가 대상보다 크거나, 탐색이 연결 리스트의 끝에 도달하면, 이전 요소로 돌아가서 다음 하위 리스트로 수직으로 내려간 후 절차가 반복된다. 각 연결 리스트에서 예상되는 단계 수는 최대 $1/p$ 이며, 이는 대상에서 다음 상위 리스트에 나타나는 요소에 도달하거나 현재 리스트의 시작에 도달할 때까지 탐색 경로를 역추적함으로써 알 수 있다. 따라서 $p$ 가 상수일 때 탐색의 총 예상 비용은 ${\tfrac {1}{p}}\log _{1/p}n$ 이며, 이는 ${\mathcal {O}}(\log n)\,$ 이다. $p$ 의 다른 값을 선택함으로써 탐색 비용과 저장 비용을 교환할 수 있다. 예를 들어, $p=1/e$ 값은 스킵 리스트의 평균 탐색 시간을 최소화하는 반면, $p=1/2$ 값은 구현을 단순화한다.

구현 세부 사항

스킵 리스트에 사용되는 요소는 여러 리스트에 참여할 수 있으므로 두 개 이상의 포인터를 포함할 수 있다.

삽입 및 삭제는 해당 연결 리스트 연산과 매우 유사하게 구현되지만, "높은" 요소는 하나 이상의 연결 리스트에 삽입되거나 삭제되어야 한다는 점이 다르다.

오름차순으로 모든 노드를 방문해야 하는 ${\mathcal {O}}(n)$ 연산(예: 전체 리스트 인쇄)은 스킵 리스트의 레벨 구조를 최적으로 비확률화하여 ${\mathcal {O}}(\log n)$ 탐색 시간을 가져올 기회를 제공한다. (i번째 유한 노드의 레벨은 i가 홀수가 되기 전에 2로 반복적으로 나눌 수 있는 횟수에 1을 더한 값으로 선택한다. 또한 음의 무한 헤더의 경우 i=0인데, 이는 음의 및 양의 무한 노드에 대해 가능한 가장 높은 레벨을 선택하는 일반적인 특수 사례가 있기 때문이다.) 그러나 이것은 또한 누군가가 레벨 1보다 높은 모든 노드가 어디에 있는지 알고 삭제할 수 있도록 허용한다.

대안적으로, 레벨 구조는 다음과 같이 준-무작위로 만들 수 있다.

모든 노드를 레벨 1로 설정한다.
j ← 1
while 레벨 j의 노드 수가 1보다 클 동안
    for 레벨 j의 각 i번째 노드 에 대해
        if i가 홀수 이고 i가 레벨 j의 마지막 노드가 아닌 경우
            레벨 j+1로 승격할지 무작위로 선택한다.
        else if i가 짝수 이고 노드 i-1이 승격되지 않은 경우
            레벨 j+1로 승격한다.
        end if
    반복
    j ← j + 1
반복

비확률화된 버전과 마찬가지로, 준-무작위화는 ${\mathcal {O}}(n)$ 연산(모든 노드를 방문하는)을 실행해야 하는 다른 이유가 있을 때만 수행된다.

이 준-무작위화의 장점은 비확률화된 버전만큼 적대적 사용자에게 레벨 구조 관련 정보를 많이 알려주지 않는다는 점이다. 이는 적대적 사용자가 최하위 레벨이 아닌 노드를 알 수 있다면 상위 레벨 노드를 단순히 삭제함으로써 성능을 악화시킬 수 있기 때문에 바람직하다. (그러나 베티아(Bethea)와 라이터(Reiter)는 그럼에도 불구하고 적대적 사용자가 확률적 및 타이밍 방법을 사용하여 성능 저하를 강요할 수 있다고 주장한다.^[4]) 탐색 성능은 여전히 로그 시간으로 보장된다.

"다음으로 각 i번째에 대해..."라는 부분에서 각 짝수-홀수 쌍에 대해 동전 던지기를 하는 것을 잊고, 짝수만 승격할지 홀수만 승격할지를 결정하기 위해 동전을 한 번만 던지는 "최적화"를 하고 싶은 유혹이 있을 수 있다. 이렇게 하면 ${\mathcal {O}}(n\log n)$ 번의 동전 던지기 대신 ${\mathcal {O}}(\log n)$ 번만 던지게 된다. 불행하게도 이것은 적대적 사용자에게 (레벨 1 이상에 있는) 짝수 번호 노드들이 모두 레벨 1보다 높다고 추측할 경우 50/50의 정확도를 제공한다. 이는 특정 노드가 정수 N인 레벨 N에 있다고 추측할 확률이 매우 낮다는 특성에도 불구하고 그렇다.

스킵 리스트는 더 전통적인 균형 트리 자료 구조와 같은 절대적인 최악의 경우 성능 보장을 제공하지 않는다. 스킵 리스트를 구축하는 데 사용되는 동전 던지기가 심하게 불균형한 구조를 생성할 가능성(매우 낮지만^[5])이 항상 있기 때문이다. 그러나 스킵 리스트는 실제로 잘 작동하며, 무작위 균형 조정 방식은 균형 이진 탐색 트리에서 사용되는 결정론적 균형 조정 방식보다 구현하기 쉽다고 주장되어 왔다. 스킵 리스트는 병렬 컴퓨팅에서도 유용하며, 자료 구조의 전역적인 재균형 조정 없이 스킵 리스트의 다른 부분에 삽입을 병렬로 수행할 수 있다. 이러한 병렬 처리는 애드혹 무선망에서 자원 발견에 특히 유리할 수 있는데, 무작위 스킵 리스트는 단일 노드의 손실에 대해 견고하게 만들 수 있기 때문이다.^[6]

인덱싱 가능한 스킵 리스트

위에서 설명한 바와 같이 스킵 리스트는 정렬된 시퀀스에서 값을 ${\mathcal {O}}(\log n)$ 시간으로 빠르게 삽입하고 제거할 수 있지만, 시퀀스의 주어진 위치에서 값을 찾는 데는 ${\mathcal {O}}(n)$ 시간이 걸린다(즉, 500번째 값 반환). 그러나 약간의 수정으로 임의 접근 인덱싱 조회 속도를 ${\mathcal {O}}(\log n)$ 으로 향상시킬 수 있다.

모든 링크에 대해 링크의 너비도 저장한다. 너비는 각 상위 계층 "고속 차선" 링크가 이동하는 최하위 계층 링크의 수로 정의된다.

예를 들어, 페이지 상단 예시에서 링크의 너비는 다음과 같다.

   1                               10
 o---> o---------------------------------------------------------> o    최상위 레벨
   1           3              2                    5
 o---> o---------------> o---------> o---------------------------> o    레벨 3
   1        2        1        2              3              2
 o---> o---------> o---> o---------> o---------------> o---------> o    레벨 2
   1     1     1     1     1     1     1     1     1     1     1
 o---> o---> o---> o---> o---> o---> o---> o---> o---> o---> o---> o    최하위 레벨
Head  1st   2nd   3rd   4th   5th   6th   7th   8th   9th   10th  NIL
      Node  Node  Node  Node  Node  Node  Node  Node  Node  Node

상위 레벨 링크의 너비는 그 아래에 있는 구성 링크의 합과 같다(예: 너비 10 링크는 바로 아래의 너비 3, 2, 5 링크를 포함한다). 결과적으로 모든 너비의 합은 모든 레벨에서 동일하다(10 + 1 = 1 + 3 + 2 + 5 = 1 + 2 + 1 + 2 + 3 + 2).

스킵 리스트를 인덱싱하고 i번째 값을 찾으려면, 스킵 리스트를 탐색하면서 각 이동된 링크의 너비를 세어 내려간다. 다가오는 너비가 너무 크면 한 레벨 아래로 내려간다.

예를 들어, 다섯 번째 위치(노드 5)의 노드를 찾으려면 최상위 레벨에서 너비 1의 링크를 이동한다. 이제 네 단계가 더 필요하지만 이 레벨의 다음 너비는 10으로 너무 크므로 한 레벨 아래로 내려간다. 너비 3의 링크 하나를 이동한다. 너비 2의 또 다른 단계는 너무 멀 것이므로 최하위 레벨로 내려간다. 이제 너비 1의 마지막 링크를 이동하여 목표 총합 5(1+3+1)에 도달한다.

function lookupByPositionIndex(i)
    node ← head
    i ← i + 1                           # 헤드를 단계로 세지 않는다.
    for level from top to bottom do
        while i ≥ node.width[level] do # 다음 단계가 너무 멀지 않으면
            i ← i - node.width[level]  # 현재 너비를 뺀다.
            node ← node.next[level]    # 현재 레벨에서 앞으로 이동한다.
        repeat
    repeat
    return node.value
end function

이 인덱싱 구현 방법은 윌리엄 푸(William Pugh)의 "A skip list cookbook"에 자세히 설명되어 있다.^[7]

역사

스킵 리스트는 1989년 윌리엄 푸에 의해 처음 기술되었다.^[8]

저자의 말을 인용하자면:

스킵 리스트는 많은 응용 프로그램에서 균형 트리 대신 선택되는 구현 방법이 될 가능성이 있는 확률적 자료 구조이다. 스킵 리스트 알고리즘은 균형 트리와 동일한 점근적 예상 시간 경계를 가지며, 더 간단하고 빠르며 공간을 덜 사용한다.
— 윌리엄 푸, Concurrent Maintenance of Skip Lists (1989)

활용

스킵 리스트를 사용하는 응용 프로그램 및 프레임워크 목록:

아파치 포터블 런타임은 스킵 리스트를 구현한다.^[9]
MemSQL은 잠금 없는 스킵 리스트를 데이터베이스 기술의 주요 인덱싱 구조로 사용한다.
리눅스 커널용 MuQSS는 스킵 리스트를 기반으로 구축된 CPU 스케줄러이다.^[10]^[11]
Cyrus IMAP 서버는 "스킵 리스트" 백엔드 DB 구현을 제공한다.^[12]
Lucene은 스킵 리스트를 사용하여 델타 인코딩된 포스팅 리스트를 로그 시간에 탐색한다.
Qt의 "QMap" 키/값 딕셔너리(Qt 4까지) 템플릿 클래스는 스킵 리스트로 구현된다.^[13]
레디스는 Posix 시스템용 ANSI-C 오픈 소스 영구 키/값 저장소로, 정렬된 집합 구현에 스킵 리스트를 사용한다.^[14]
디스코드는 스킵 리스트를 사용하여 서버의 멤버 목록을 저장하고 업데이트한다.^[15]
자바는 ConcurrentSkipListSet 및 ConcurrentSkipListMap에 스킵 리스트를 사용한다.
RocksDB는 기본 Memtable 구현에 스킵 리스트를 사용한다.^[16]

스킵 리스트는 분산 응용 프로그램(노드가 물리적 컴퓨터를 나타내고 포인터가 네트워크 연결을 나타내는)에서도 사용되며, 잠금 경합이 적은 고도로 확장 가능한 동시 우선순위 큐를 구현하는 데 사용된다.^[17] 또는 잠금 없이도,^[18]^[19]^[20] 잠금 없는 동시 딕셔너리 구현에도 사용된다.^[21] 스킵 리스트를 사용하여 (잠금 없는) 우선순위 큐 및 동시 딕셔너리를 구현하기 위한 여러 미국 특허도 있다.^[22]

같이 보기

각주

↑ ^가 ^나 Papadakis, Thomas (1993). 《Skip Lists and Probabilistic Analysis of Algorithms》 (PDF) (Ph.D.). University of Waterloo.
↑ Pugh, W. (1990). 《Skip lists: a probabilistic alternative to balanced trees》 (PDF). 《커뮤니케이션스 오브 더 ACM》 33. 668–676쪽. doi:10.1145/78973.78977. S2CID 207691558.
↑ Munro, J. Ian; Papadakis, Thomas; Sedgewick, Robert (1992). 〈Deterministic skip lists〉 (PDF). 《Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms (SODA '92)》. Orlando, Florida, USA: Society for Industrial and Applied Mathematics, Philadelphia, PA, USA. 367–375쪽. S2CID 7477119.
↑ Bethea, Darrell; Reiter, Michael K. (September 21–23, 2009). 《Data Structures with Unpredictable Timing》 (PDF). ESORICS 2009, 14th European Symposium on Research in Computer Security. Saint-Malo, France. pp. 456–471, §4 "Skip Lists". doi:10.1007/978-3-642-04444-1_28. ISBN 978-3-642-04443-4.
↑ Sen, Sandeep (1991). 《Some observations on skip lists》. 《Information Processing Letters》 39. 173–176쪽. doi:10.1016/0020-0190(91)90175-H.
↑ Shah, Gauri (2003). 《Distributed Data Structures for Peer-to-Peer Systems》 (PDF) (Ph.D. thesis). Yale University.
↑ William Pugh. "A skip list cookbook". 1990. Section 3.4 Linear List Operations .
↑ Pugh, William (April 1989). 《Concurrent Maintenance of Skip Lists》 (PS, PDF) (기술 보고서). Dept. of Computer Science, U. Maryland. CS-TR-2222.
↑ 아파치 포터블 런타임 APR 1.6 문서
↑ LWN의 기사
↑ “LKML: Con Kolivas: [ANNOUNCE] Multiple Queue Skiplist Scheduler version 0.120”. 《lkml.org》. 2017년 5월 11일에 확인함.
↑ Cyrus IMAP 서버. skiplist 소스 파일
↑ QMap
↑ “Redis ordered set implementation”. 《GitHub》.
↑ Nowack, Matt. “Using Rust to Scale Elixir for 11 Million Concurrent Users”. 《Discord Blog》. 2023년 7월 23일에 확인함.
↑ “MemTable” (영어). 《GitHub》. 2023년 12월 12일에 확인함.
↑ Shavit, N.; Lotan, I. (2000). 〈Skiplist-based concurrent priority queues〉 (PDF). 《Proceedings 14th International Parallel and Distributed Processing Symposium. IPDPS 2000》. 263쪽. CiteSeerX 10.1.1.116.3489. doi:10.1109/IPDPS.2000.845994. ISBN 978-0-7695-0574-9. S2CID 8664407.
↑ Sundell, H.; Tsigas, P. (2003). 〈Fast and lock-free concurrent priority queues for multi-thread systems〉. 《Proceedings International Parallel and Distributed Processing Symposium》. 11쪽. CiteSeerX 10.1.1.113.4552. doi:10.1109/IPDPS.2003.1213189. ISBN 978-0-7695-1926-5. S2CID 20995116.
↑ Fomitchev, Mikhail; Ruppert, Eric (2004). 《Lock-free linked lists and skip lists》 (PDF). Proc. Annual ACM Symp. on Principles of Distributed Computing (PODC). 50–59쪽. doi:10.1145/1011767.1011776. ISBN 1581138024.
↑ Bajpai, R.; Dhara, K. K.; Krishnaswamy, V. (2008). 〈QPID: A Distributed Priority Queue with Item Locality〉. 《2008 IEEE International Symposium on Parallel and Distributed Processing with Applications》. 215쪽. doi:10.1109/ISPA.2008.90. ISBN 978-0-7695-3471-8. S2CID 15677922.
↑ Sundell, H. K.; Tsigas, P. (2004). 〈Scalable and lock-free concurrent dictionaries〉 (PDF). 《Proceedings of the 2004 ACM symposium on Applied computing - SAC '04》. 1438쪽. doi:10.1145/967900.968188. ISBN 978-1581138122. S2CID 10393486.
↑ US patent 7937378

외부 링크

위키미디어 공용에 스킵 리스트 주제와 관련된 미디어 분류가 있습니다.

[cs.uwaterloo-1] 가 ^나 Papadakis, Thomas (1993). 《Skip Lists and Probabilistic Analysis of Algorithms》 (PDF) (Ph.D.). University of Waterloo.

[pugh-2] Pugh, W. (1990). 《Skip lists: a probabilistic alternative to balanced trees》 (PDF). 《커뮤니케이션스 오브 더 ACM》 33. 668–676쪽. doi:10.1145/78973.78977. S2CID 207691558.

[3] Munro, J. Ian; Papadakis, Thomas; Sedgewick, Robert (1992). 〈Deterministic skip lists〉 (PDF). 《Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms (SODA '92)》. Orlando, Florida, USA: Society for Industrial and Applied Mathematics, Philadelphia, PA, USA. 367–375쪽. S2CID 7477119.

[4] Bethea, Darrell; Reiter, Michael K. (September 21–23, 2009). 《Data Structures with Unpredictable Timing》 (PDF). ESORICS 2009, 14th European Symposium on Research in Computer Security. Saint-Malo, France. pp. 456–471, §4 "Skip Lists". doi:10.1007/978-3-642-04444-1_28. ISBN 978-3-642-04443-4.

[5] Sen, Sandeep (1991). 《Some observations on skip lists》. 《Information Processing Letters》 39. 173–176쪽. doi:10.1016/0020-0190(91)90175-H.

[6] Shah, Gauri (2003). 《Distributed Data Structures for Peer-to-Peer Systems》 (PDF) (Ph.D. thesis). Yale University.

[7] William Pugh. "A skip list cookbook". 1990. Section 3.4 Linear List Operations .

[8] Pugh, William (April 1989). 《Concurrent Maintenance of Skip Lists》 (PS, PDF) (기술 보고서). Dept. of Computer Science, U. Maryland. CS-TR-2222.

[9] 아파치 포터블 런타임 APR 1.6 문서

[10] LWN의 기사

[11] “LKML: Con Kolivas: [ANNOUNCE] Multiple Queue Skiplist Scheduler version 0.120”. 《lkml.org》. 2017년 5월 11일에 확인함.

[12] Cyrus IMAP 서버. skiplist 소스 파일

[13] QMap

[14] “Redis ordered set implementation”. 《GitHub》.

[15] Nowack, Matt. “Using Rust to Scale Elixir for 11 Million Concurrent Users”. 《Discord Blog》. 2023년 7월 23일에 확인함.

[16] “MemTable” (영어). 《GitHub》. 2023년 12월 12일에 확인함.

[17] Shavit, N.; Lotan, I. (2000). 〈Skiplist-based concurrent priority queues〉 (PDF). 《Proceedings 14th International Parallel and Distributed Processing Symposium. IPDPS 2000》. 263쪽. CiteSeerX 10.1.1.116.3489. doi:10.1109/IPDPS.2000.845994. ISBN 978-0-7695-0574-9. S2CID 8664407.

[18] Sundell, H.; Tsigas, P. (2003). 〈Fast and lock-free concurrent priority queues for multi-thread systems〉. 《Proceedings International Parallel and Distributed Processing Symposium》. 11쪽. CiteSeerX 10.1.1.113.4552. doi:10.1109/IPDPS.2003.1213189. ISBN 978-0-7695-1926-5. S2CID 20995116.

[19] Fomitchev, Mikhail; Ruppert, Eric (2004). 《Lock-free linked lists and skip lists》 (PDF). Proc. Annual ACM Symp. on Principles of Distributed Computing (PODC). 50–59쪽. doi:10.1145/1011767.1011776. ISBN 1581138024.

[20] Bajpai, R.; Dhara, K. K.; Krishnaswamy, V. (2008). 〈QPID: A Distributed Priority Queue with Item Locality〉. 《2008 IEEE International Symposium on Parallel and Distributed Processing with Applications》. 215쪽. doi:10.1109/ISPA.2008.90. ISBN 978-0-7695-3471-8. S2CID 15677922.

[21] Sundell, H. K.; Tsigas, P. (2004). 〈Scalable and lock-free concurrent dictionaries〉 (PDF). 《Proceedings of the 2004 ACM symposium on Applied computing - SAC '04》. 1438쪽. doi:10.1145/967900.968188. ISBN 978-1581138122. S2CID 10393486.

[22] US patent 7937378

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

v t e 자료 구조
유형	컬렉션 컨테이너
추상	연관 배열 우선순위 덱 덱 리스트 멀티맵 우선순위 큐 큐 집합 멀티셋 분리 집합 스택
배열	비트 배열 환형 배열 동적 배열 해시 테이블 해시드 어레이 트리 희소 배열(Sparse array)
연결형	연관 리스트 연결 리스트
트리	B 트리 이진 탐색 트리 AA AVL 레드-블랙 자가 균형 스플레이 힙 이진 힙 피보나치 R 트리 R* R+ 힐버트 트리 해시 트리
그래프	이진 결정 다이어그램
자료 구조의 목록