Скип листа

скип листа
тип	листа
Година настанка	1989
Изумео	Вилијам Паг
Временска сложеност; у нотацији велико О

У рачунарству, скип листа је структура података која омогућава брзу претрагу кроз уређени низ елемената. Изнад низа елемената се формира више слојева повезаних листи. Прва, најнижа листа садржи све елементе низа, а свака следећа је све ређа (прескаче неке елементе из претходне листе). Чворови свих листи као вредност садрже одговарајући елемент основног низа, и приликом проласка кроз неки чвор једне листе, могуће је прећи (вертикално се померити) у било коју другу листу која садржи исти елемент.

Претрага почиње од највише (најређе) подлисте, кроз коју се пролази док се не нађу два узастопна елемента таква да је један мањи а други већи или једнак траженом елементу. Уколико је нађен елемент једнак траженом, претрага је готова. У супротном се преко највећег елемента мањег од траженог елемента се спушта у следећу подлисту у хијерархији, и од тог елемента се наставља претрага као и у претходном нивоу. Претрага се завршава када је тражени елемент нађен, или када се утврди да елемент не постоји у најнижој (комплетној) листи. Елементи који су прескочени у вишим подлистама могу да буду изабрани пробабилистички ^[2] или детерминистички^[3], али се чешће користи пробабилистички приступ.

Опис

Скип листа је сачињена од слојева. Најнижи слој је обична уређена повезана листа. Сваки виши слој служи као „пречица“ кроз листе испод себе. Елемент из слоја i се појављује у слоју i+1 са неком фиксном вероватноћом p (две често коришћене вредности за p су 1/2 и 1/4). У просеку, сваки елемент се појављује у 1/(1-p) листи, а највиши елемент (обично специјални почетни елемент испред листе) се појављује у свим листама. Скип листа садржи $\log _{1/p}n\,$ листи.

Претрага за одређеним елементом почиње од првог елемента у највишој листи. Претрага се врши хоризонтално кроз највишу листу док се не дође до елемента који је већи од или једнак траженом елементу. Уколико је текући елемент једнак траженом елементу, тражени елемент је нађен. Ако је тренутни елемент већи од траженог елемента, или ако је претрага довела до краја тренутне листе, потребно је вратити се до претходног елемента, и спустити се једну листу ниже. Затим се понавља хоризонтална претрага из те следеће ниже листе почев од истог елемента (највећег елемента из претходне листе који је мањи од траженог). Очекивани број корака у свакој од листи је највише 1/p, што се може видети праћењем тока претраге уназад од траженог елемента све до елемента који се појављује у следећој вишој листи, или до почетка текуће листе. Стога, укупан број очекиваних корака је $(\log _{1/p}n)/p,\,$ што је ${\mathcal {O}}(\log n)\,$ када је p константно. Одабирањем различитих вредности за p, могуће је утицати на брзину претраге на уштрб меморијских захтева.

Имплементациони детаљи

Елементи унутар скип листе могу да садрже више од једног показивача јер могу да се налазе у више листи.

Уметање и брисање елемената је имплементирано на исти начин као и одговарајуће операције у повезаним листама, изузев што „високи“ елементи морају да буду уметнути или обрисани из више од једне повезане листе.

${\mathcal {O}}(n)$ операција, то јест пролазак кроз све чворове у листи у растућем поретку (као приликом штампања целе листе), пружа могућност да се успут изврши дерандомизација структуре скип листе, тако да се време претраге сведе на ${\mathcal {O}}(\log n)$ . Висина i-тог члана скип листе може да се израчуна као 1 плус број пута којим i може да се подели са 2 пре него што се добије непаран број. У специфичним случајевима када злонамерни корисник може да утиче на елементе који се додају или бришу из скип листе, уколико корисник може да израчуна висину елемената, он има могућност да обрише све елементе са већом висином, и тако ефективно да деградира перформансе претраге кроз скип листу.

Алтернативно, структура нивоа скип листе би могла да буде квази-насумична ако би балансирање било имплементирано на следећи начин:

neka svi cvorovi budu nivoa 1
j ← 1
while broj cvorova na nivou j > 1 do
  for svaki i-ti cvor na nivou j do
    if i is odd 
      if i nije poslednji cvor na nivou j
        nasumicno odaberi da li da se cvor promovise u nivo j+1
      else
        cvor se ne promovise
      end if
    else if i je parno i i-1 nije promovisan
      promovisi cvor u nivo j+1
    end if
  repeat
  j ← j + 1
repeat

Као и код дерандомизоване верзије, квази-насумично балансирање се обично врши кад се из неког другог разлога већ пролази кроз сваки нод, што је операција дужине ${\mathcal {O}}(n)$ .

Скип листа не пружа исте гаранције перформанси у апсолутно најгорем случају као традиционално балансирано стабло, јер је увек могуће (мада врло мало вероватно) да се насумичним избором висине елемената произведе лоше балансирана структура. Међутим, скип листе добро функционишу у пракси, а рандомизована схема балансирања је потенцијално једноставнија за имплементацију од детерминистичке схеме балансирања која се користи у балансираним бинарним стаблима претраге. Скип листе могу такође да буду корисне у паралелном рачунарству, где уметање у различите делове скип листе може да се врши у паралели без било каквог глобалног ребалансирања структуре података. Такав паралелизам може бити посебно погодан за откривање ресурса у ад хок бежичној мрежи, јер рандомизована скип листа може да се начини да буде робусна у случају губитка једног од нодова.^[4]

Индексирана скип листа

Као што је већ наведено, скип листа омогућава брзо ${\mathcal {O}}(\log n)$ уметање и брисање вредности из сортираног низа елемената, али је проналажење елемента на одговарајућем месту (нпр. 500. елемент по реду) споро, ${\mathcal {O}}(n)$ . Међутим, уз малу измену, брзина приступа i-том елементу у листи може да се поправи у ${\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    најнижи ниво
                                         
старт 1.    2.    3.    4.    5.    6.    7.    8.    9.    10.   NIL
      чвор  чвор  чвор  чвор  чвор  чвор  чвор  чвор  чвор  чвор

Дужина показивача на вишем нивоу је једнака збиру дужина показивача из претходног нивоа који се налазе испод њега (на пример, показивач дужине 10 се налази изнад показивача дужина 3, 2 и 5 у нивоу испод). Стога, збир дужина свих показивача је исти за сваки ниво (10 + 1 = 1 + 3 + 2 + 5 = 1 + 2 + 1 + 2 + 5).

Како би се пронашао o-ти елемент у индексираној скип листи, потребно је да се пролази кроз листу сабирајући дужине показивача кроз које се ппролазе. Кад се наиђе на показивач чија дужина је превлика за тражени елемент, спушта се ниво ниже.

На пример, како би се пронашао пети елемент у листи наведеној изнад (5. чвор), прво се пролази показивач дужине 1 на највишем нивоу. Потребно је прећи још 4 корака, али је следећи показивач (дужине 10) превише дугачак, тако да је потребно спустити се један ниво ниже. Пролази се показивач дужине 3. Следећи показивач на овом нивоу је дужине 2, па је он предугачак, потребно је спустити се на следећи ниво. На том нивоу је следећи показивач поново дужине 2, тако да је потребно спустити се на следећи (најнижи) ниво. Следећи показивач је дужине 1, и након што се он прође, долази се до траженог елемента на позицији 5 (1+3+1).

 function pretraziPoPolozajuIndeksa(i)
     cvor ← start
     i ← i + 1                             # почетни елемент се не рачуна као корак
     for nivo from vrh to dno do
          while i ≥ cvor.cuzina[nivo] do   # ако следећи корак није превише далеко
              i ← i - cvor.duzina[nivo]    # одузми тренутну дужину
              cvor ← cvor.sledeci[nivo]    # крећи се напред на тренутном нивоу
          repeat
     repeat
     return cvor.vrednost
 end function

Овај метод имплементирања индексирања је детаљно описан у Одељку 3.4 Операције над линеарним листама, у „Кувару за скип листе“ Вилијама Пага Архивирано на сајту Wayback Machine (27. септембар 2011).

Историја

Скип листе је први описао Вилијам Паг 1989. године.^[5]

Цитат аутора:

Скип листе су пробабилистичка структура података која ће вероватно заменити балансирана стабла као уобичајени имплементациони метод у многим применама. Алгоритми над скип листама имају исте асимптотске границе очекиваних времена као балансирана стабла, а једноставнији су и користе мање простора.

Види још

Блумов филтар

Референце

^ ^а ^б 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). Communications of the ACM. 33 (6): 668—676. S2CID 35479922. doi:10.1145/78973.78977. Архивирано из оригинала (PDF) 20. 06. 2020. г. Приступљено 20. 01. 2018.
^ 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. doi:10.1145/139404.139478 (неактивно 2023-10-11).
^ Shah, Gauri (2003). Distributed Data Structures for Peer-to-Peer Systems (PDF) (Ph.D. thesis). Yale University.
^ Pugh, William (април 1989). Concurrent Maintenance of Skip Lists (PS, PDF) (Технички извештај). Dept. of Computer Science, U. Maryland. CS-TR-2222.

Додатна литература

„Скип стабла, алтернатива скип листама у конкурентном приступу”. CiteSeerX 10.1.1.47.514 .

Спољашње везе

Имплементације

[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). Communications of the ACM. 33 (6): 668—676. S2CID 35479922. doi:10.1145/78973.78977. Архивирано из оригинала (PDF) 20. 06. 2020. г. Приступљено 20. 01. 2018.

[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. doi:10.1145/139404.139478 (неактивно 2023-10-11).

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

[5] Pugh, William (април 1989). Concurrent Maintenance of Skip Lists (PS, PDF) (Технички извештај). Dept. of Computer Science, U. Maryland. CS-TR-2222.

[1]

[2]

[3]

[4]

[5]

скип листа
тип	листа
Година настанка	1989
Изумео	Вилијам Паг
Временска сложеност у нотацији велико О
	Просечна	Најгори случај
Простор	O(n)	O(n log n)^[1]
Претрага	O(log n)	O(n)^[1]
Уметање	O(log n)	O(n)
Брисање	O(log n)	O(n)