Skip List를 어디에 쓸 수 있을까

-

Skip List
일반 Linked List는 정렬이 되어있더라도 그 이점을 살리지 못하고, 원하는 노드를 찾기 위해 헤드부터 끝까지 쭉 돌아야 한다. == O(n).
Skip List는 일반 Linked List에 level의 개념을 추가해서 마치 binary search tree처럼 탐색 속도를 줄이는 자료구조라고 할 수 있다
우선 생긴 것은 아래와 같다.

출처: https://en.wikipedia.org/wiki/Skip_list#/media/File:Skip_list.svg 

각 노드마다 위쪽으로 길게 포인터가 붙어있는데, 이것을 레벨이라고 한다. (위에서부터 0이라 하는지, 밑에서부터 0이라 하는지 등의 구체적인 것은 구현에 따라 달라질 수 있음)


먼저 find를 생각해보자.
위의 Skip List에서 7를 찾고 싶다고 생각하면, 기존의 Linked List에선 7개의 노드를 봐야한다.
(1)  1 보고, 아니네? 다음
(2)  2 보고, 아니네? 다음
(3)  3 보고, 아니네? 다음
…
(7)  6 보고, 아니네? 다음
(8)  7 보고, 맞네? 찾았다!
물론 원하는 게 바로 안 나오면 n개까지 찾다가 없다고 알아낼 수 있다.
7을 7번만에 찾았다는 건 운이 좋은 경우이고,
정렬이 되어있더라도 이 사실은 크게 변하지 않는다(일반적인 Linked List라고 하면).

반면 Skip List에서 8를 찾고 싶다면 1 -> 4 -> 6 -> 7 을 거쳐 찾을 수 있다.
(1)  1 보고, 나보다 작네? 가장 높은 레벨(4)이 가리키는 애를 보자
(2)  Null을 가리키고 있네.. 그러면 다음 낮은 레벨(3)을 보자.
(3)  4를 기리키고 있네? 내가 찾고자하는 8보다 작으니 이동하자
(4)  4에서 같은 레벨의 다음 것을 보니 6을 가리키고 있네? 8보다 작으니 이동하자
(5)  6에서 같은 레벨의 다음 것을 보니 Null을 가리키고 있네? 레벨을 하나 낮추자(2).
(6)  7을 가리키고 있네? 찾았다!

위의 Skip List로 예를 들어서 단계의 수만 보면 별로 차이가 없다고 느낄 수 있다.
하지만 Skip List는 무려 정렬을 이용할 수 있다.
마치 Binary Search Tree 처럼 정렬을 이용해서 Linked List임에도 불구하고 빠르게 서치할 수 있는 것이다.

그러면 구현은 어떻게 하지?
각 노드마다의 레벨이 있는데, 이 레벨을 정하는 게 문제다.
이 레벨은 동전을 던져서 정하면 된다.
그냥 랜덤하게 정하는 것이다.
노드의 레벨을 정할 때마다 랜덤하게 만들면 전체적으로 보았을 때 레벨이 골고루 분포되고 우리가 원하는, 마치 Binary Search Tree를 쭉 늘어놓은 듯한, Skip List가 나온다고 한다.

이 Skip List의 내용은 수업 중에도 깊게 다루기 보단 개념을 소개하는 느낌으로 가서 보다 자세한 내용은 더 공부가 필요하다.

Skip List는 어디에 쓰지?
사실 수업 때 Skip List를 보면서 처음 든 생각은 ‘어디에 쓸까’였다.
레벨을 랜덤하게 설정했는데 아무튼 바이너리 서치 트리처럼 빠르게 찾을 수 있다는 것도 잘 이해가 안됐고
그럼 그냥 만들기도 쉬운 바이너리 서치 트리 만들면 되는 거 아닌가? 라는 생각도 들었다.
우매한 한명의 비전공생의 생각에 불과했다.
교수님은 Randomized된 자료구조의 장점을 이야기하며 Skip List의 사용처 느낌을 잡아주셨다(교수님도 사용처를 정확히 모르셔서 이후 보충자료를 보내주셨다).
Randomized된 자료구조는 공격에 강하다는 것이다.
예를 들어 어떤 서비스에서 바이너리 서치 트리를 사용한다고 생각해보자.
자료형에 따라 다르겠지만 극도로 단순하게 생각해서 정수형 자료구조라 했을 때,
우리는 비교적 쉽게 특정 값의 위치를 파악할 수 있다.
예를 들면, 가장 서치가 오래 걸리는 값의 위치.
그러면 그런 값을 반복해서 요청한다면 나름의 공격이 되는 것이다.
이게 개념적으로 맞는지는 모르겠는데 그나마 이해할 수 있는 설명이었다.
예시로만 받아들이자.
아무튼 이것과 다르게 Randomized된 자료구조는 특정 값의 위치를 파악하기 힘들어
공격에 내성이 있다는 것이다.

이 정도가 교수님의 설명이었고 추가적으로 주변 현업 개발자분들께 실제 사용을 물어보고 알려주신다 하셨다(^^b)

Skip List가 BST에 비해 좋은 점?
추가적으로 교수님이 읽을 거리를 주셨는데, 여기서 결정적인 Skip List의 사용을 알 수 있었다.
https://stackoverflow.com/questions/256511/skip-list-vs-binary-search-tree

Skil List와 BTS를 비교한 글인데, 요약하자면
Skip List는 concurrent access / modification 에 적합하다는 내용이다.
concurrent는 주로 병행으로 번역하는데, 우리가 알고 있는 parallel(병렬)과는 다른 뜻이다.
Throughput과 관련이 있다고 생각하면 된다.
같은 일을 나눠서 하면 parallel이고, 같은 일을 동시에 여러 개가 수행하도록 하면 concurrent이다.(더 자세한 건 여기서 다룰 수 없음)

아무튼 Skip List가 concurrent에 적합한 이유는, 일종의 lock-free 자료구조에 가깝기 때문이다.
BTS(red black tree 기준)은 수정되면 rebalance를 해주면서 트리의 모든 부분이 영향을 받을 수 있기 때문에 많은 트리 노드에 대한 mutex lock이 필요하다.
Skip List는 삽입시 훨씬 더 좁은 범위와 관련이 있다(far more localized),.
영향을 받는 노드에 직접적으로 연결되어 있는 노드들만 lock되면 되기 때문이다.
Linked List에 삽입 시 삽입할 위치와 한쪽 노드(더블 링크드면 양쪽)만 건드리면 된다는 걸 알 것이다.
Skip List도 비슷한 원리로 삽입할 곳의 주변 노드들에만 lock을 걸고 수정하면 된다.
(레벨별 포인터 값을 다 수정해주어야 해서 Linked List보단 신경쓸 게 많긴 함)

같은 일을 하는데 lock을 더 적게 걸 수 있다면 당연히 이득을 볼 수 있다.
데이터 삽입 할 때 다른 곳의 데이터를 접근하려면 기다리지 않아도 되고
lock으로 다뤄야할 정보 역시 적어지니 개발이 더 쉬워질 것이다.



댓글

댓글 쓰기

이 블로그의 인기 게시물

C++ int, long int, long long int 어떤 걸 써야할까

-
이미지
(출처:  https://ko.cppreference.com/w/cpp/language/types ) (LP32, ILP32, LLP64, LP64는 data model을 나타내며, 글 맨 아래 '참고'에 정리해둠) C++ 정수형 데이터 타 입들 C++ standard를 기준으로      short                     - 최소 16비트      int                         - 최소 16비트      long int                - 최소 32비트      long long int        - 최소 64비트 (C++ standard는 정수형 데이터 타입의 명확한 크기를 정해두지 않았다.  다만 최소한의 하한선만 정해놓았다) 일반적으로 short 는 16 비트 , int 는 32 비트로 알고 있다 . 그래서 int 는 -2^31 ~ 2^31 – 1 범위의 정수를 표현할 수 있고 , 이보다 크거나 작은 정수를 표현하기 위해서는 비트수가 더 필요하다 . 그러면 long 을 써야하나 long long 을 써야하나 ? 확실한 방법은 long long int 를 쓰는 것이다 . C++ 표준을 보면 long int 는 최소 32 비트를 보장한다고 한다 . -2^31 ~ 2^31 – 1 범위를 넘어서는 정수를 표현하기 위해서는 C++ 표준 기준으로 최소 64 비트를 보장하는 long long int 를 써야한다 . (long int를 쓸 경우, 윈도우 환경에서는 int와 똑같은 범위까지만 표현할 수 있다) // 나만의 생각 시작 그러면 long int 는 필요 없는 것 아닌가 ? ILP32, LLP64, LP64 data model만 고려한다면 그렇다고 볼 수 있지 않을까 싶다. 왜냐하면 위 세 개의 data model 에서는 int 와 long int 의 비트수가 같거나,  long int 와 long long int 의 비트수가 같기 때문이다 . long int가 int
자세한 내용 보기

C++ fstream 간단한 사용법(파일입출력)

-
이미지
인터넷을 돌아다니다 보니, 파일입출력은 기본 중에 기본이라고 한다. C++를 주로 사용하고 있지만 파일입출력을 할 줄 몰랐다. 그래서 정리한다. (내용출처 :  http://www.cplusplus.com/doc/tutorial/files/  ) <fstream>  C++는 <fstream> 이라는 Stream class를 지원한다. '파일에서 읽어오거나 파일에 쓰는 클래스' 라고 한다. istream과 ostream의 파생클래스이다(자식임).  <fstream>에서 주로 쓰는 두 가지는 ofstream 과 ifstream 이다. ofstream  ofstream은 'output file stream'이다. output이라길래 파일의 내용을 읽어오는 줄 알았는데 내 생각과 반대로 파일에 적는 친구다. ofstream에는 멤버함수 open이 있다. 사용법은 평소에 쓰던 cin, cout 과 비슷하다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 #include   < iostream > #include   < fstream > using   namespace   std ; int  main( void ) {      // 파일 열기     ofstream myfile;     myfile.open( "example.txt" );           // 파일에 쓰기     myfile  < <   "Wow.\n" ;     myfile  < <   "Writing this to a file.\n" ;           // 파일 닫기     myfile.close();    
자세한 내용 보기

x86 OS interrupts routine

-
x86 운영체제에서는 다음과 같은 과정을 거쳐 interrupt 를 호출한다 1.       interrupt n instruction 수행 . 2.       IDT 에 등록되어있는 ISR(interrupt Service Routine) 수행 . xv6 는 위의 두 과정을 아래와 같이 진행한다 . 1. interrupt n instruction - “int n” instruction workflow. 1)        IDT(interrupt descriptor table) 에서 n’th descriptor 를 읽어온다 . -  시스템 부팅시 tvinit() 함수로 vertors.S 의 번호 , DPL 을 다 초기화 해줌 . -  system call은 DPL이 유저 레벨로 세팅됨 2)        CPL 이 DPL 보다 작거나 같은지를 확인함 ( 커널 모드 : 0, 유저 모드 : 3, 부를 수 있는지 없는지를 확인하는 것 ) -   이 조건을 충족하지 못하면 부를 수 없는 interrupt 를 부른 것이라 exception 이 발생한다 . 3)        만약 target segment selector 의 PL 이 CPL 보다 작으면 PL 의 변환이 필요하다 (ex PL 이 커널모드인 경우 ). 다음 3 단계를 거쳐서 변환이 일어남 . (1)   현재 유저모드니깐 , 유저모드의 esp, ss register 를 임시로 저장함 ( 임시로 저장하는 이유는 커널 스택에다 푸시하기 위해서 ) (2)   task segment descriptor 에서 esp, ss 를 불러와서 CPU-internal registers 에 저장함 . (3)   이제 아까 임시로 저장한 esp, ss 를 푸시해줌 ( 유저 모드로 돌아가기 위한 esp, ss) 4)        eflags, cs, eip register 를 stack 에 푸시한다 . -   당연히 여기는 Kernal Stack 임 .
자세한 내용 보기