Skip lista
| skip lista | ||
|---|---|---|
| tip | lista | |
| Godina nastanka | 1989 | |
| Izumeo | Vilijam Pag | |
| Vremenska složenost u notaciji veliko O | ||
| Prosečna | Najgori slučaj | |
| Prostor | O(n) | O(n log n)[1] |
| Pretraga | O(log n) | O(n)[1] |
| Umetanje | O(log n) | O(n) |
| Brisanje | O(log n) | O(n) |
U računarstvu, skip lista je struktura podataka koja omogućava brzu pretragu kroz uređeni niz elemenata. Iznad niza elemenata se formira više slojeva povezanih listi. Prva, najniža lista sadrži sve elemente niza, a svaka sledeća je sve ređa (preskače neke elemente iz prethodne liste). Čvorovi svih listi kao vrednost sadrže odgovarajući element osnovnog niza, i prilikom prolaska kroz neki čvor jedne liste, moguće je preći (vertikalno se pomeriti) u bilo koju drugu listu koja sadrži isti element.
Pretraga počinje od najviše (najređe) podliste, kroz koju se prolazi dok se ne nađu dva uzastopna elementa takva da je jedan manji a drugi veći ili jednak traženom elementu. Ukoliko je nađen element jednak traženom, pretraga je gotova. U suprotnom se preko najvećeg elementa manjeg od traženog elementa se spušta u sledeću podlistu u hijerarhiji, i od tog elementa se nastavlja pretraga kao i u prethodnom nivou. Pretraga se završava kada je traženi element nađen, ili kada se utvrdi da element ne postoji u najnižoj (kompletnoj) listi. Elementi koji su preskočeni u višim podlistama mogu da budu izabrani probabilistički [2] ili deterministički[3], ali se češće koristi probabilistički pristup.
Opis[uredi | uredi izvor]
Skip lista je sačinjena od slojeva. Najniži sloj je obična uređena povezana lista. Svaki viši sloj služi kao „prečica“ kroz liste ispod sebe. Element iz sloja i se pojavljuje u sloju i+1 sa nekom fiksnom verovatnoćom p (dve često korišćene vrednosti za p su 1/2 i 1/4). U proseku, svaki element se pojavljuje u 1/(1-p) listi, a najviši element (obično specijalni početni element ispred liste) se pojavljuje u svim listama. Skip lista sadrži listi.
Pretraga za određenim elementom počinje od prvog elementa u najvišoj listi. Pretraga se vrši horizontalno kroz najvišu listu dok se ne dođe do elementa koji je veći od ili jednak traženom elementu. Ukoliko je tekući element jednak traženom elementu, traženi element je nađen. Ako je trenutni element veći od traženog elementa, ili ako je pretraga dovela do kraja trenutne liste, potrebno je vratiti se do prethodnog elementa, i spustiti se jednu listu niže. Zatim se ponavlja horizontalna pretraga iz te sledeće niže liste počev od istog elementa (najvećeg elementa iz prethodne liste koji je manji od traženog). Očekivani broj koraka u svakoj od listi je najviše 1/p, što se može videti praćenjem toka pretrage unazad od traženog elementa sve do elementa koji se pojavljuje u sledećoj višoj listi, ili do početka tekuće liste. Stoga, ukupan broj očekivanih koraka je što je kada je p konstantno. Odabiranjem različitih vrednosti za p, moguće je uticati na brzinu pretrage na uštrb memorijskih zahteva.
Implementacioni detalji[uredi | uredi izvor]
Elementi unutar skip liste mogu da sadrže više od jednog pokazivača jer mogu da se nalaze u više listi.
Umetanje i brisanje elemenata je implementirano na isti način kao i odgovarajuće operacije u povezanim listama, izuzev što „visoki“ elementi moraju da budu umetnuti ili obrisani iz više od jedne povezane liste.
operacija, to jest prolazak kroz sve čvorove u listi u rastućem poretku (kao prilikom štampanja cele liste), pruža mogućnost da se usput izvrši derandomizacija strukture skip liste, tako da se vreme pretrage svede na . Visina i-tog člana skip liste može da se izračuna kao 1 plus broj puta kojim i može da se podeli sa 2 pre nego što se dobije neparan broj. U specifičnim slučajevima kada zlonamerni korisnik može da utiče na elemente koji se dodaju ili brišu iz skip liste, ukoliko korisnik može da izračuna visinu elemenata, on ima mogućnost da obriše sve elemente sa većom visinom, i tako efektivno da degradira performanse pretrage kroz skip listu.
Alternativno, struktura nivoa skip liste bi mogla da bude kvazi-nasumična ako bi balansiranje bilo implementirano na sledeći način:
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
Kao i kod derandomizovane verzije, kvazi-nasumično balansiranje se obično vrši kad se iz nekog drugog razloga već prolazi kroz svaki nod, što je operacija dužine .
Skip lista ne pruža iste garancije performansi u apsolutno najgorem slučaju kao tradicionalno balansirano stablo, jer je uvek moguće (mada vrlo malo verovatno) da se nasumičnim izborom visine elemenata proizvede loše balansirana struktura. Međutim, skip liste dobro funkcionišu u praksi, a randomizovana shema balansiranja je potencijalno jednostavnija za implementaciju od determinističke sheme balansiranja koja se koristi u balansiranim binarnim stablima pretrage. Skip liste mogu takođe da budu korisne u paralelnom računarstvu, gde umetanje u različite delove skip liste može da se vrši u paraleli bez bilo kakvog globalnog rebalansiranja strukture podataka. Takav paralelizam može biti posebno pogodan za otkrivanje resursa u ad hok bežičnoj mreži, jer randomizovana skip lista može da se načini da bude robusna u slučaju gubitka jednog od nodova.[4]
Indeksirana skip lista[uredi | uredi izvor]
Kao što je već navedeno, skip lista omogućava brzo umetanje i brisanje vrednosti iz sortiranog niza elemenata, ali je pronalaženje elementa na odgovarajućem mestu (npr. 500. element po redu) sporo, . Međutim, uz malu izmenu, brzina pristupa i-tom elementu u listi može da se popravi u .
Uz svaki pokazivač, takođe se skladišti i „dužina“ pokazivača. Dužina je definisana kao broj elemenata iz najnižeg nivoa koje taj pokazivač/prečica preskače.
Ispod su date dužine pokazivača u primeru skip liste:
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
чвор чвор чвор чвор чвор чвор чвор чвор чвор чвор
Dužina pokazivača na višem nivou je jednaka zbiru dužina pokazivača iz prethodnog nivoa koji se nalaze ispod njega (na primer, pokazivač dužine 10 se nalazi iznad pokazivača dužina 3, 2 i 5 u nivou ispod). Stoga, zbir dužina svih pokazivača je isti za svaki nivo (10 + 1 = 1 + 3 + 2 + 5 = 1 + 2 + 1 + 2 + 5).
Kako bi se pronašao o-ti element u indeksiranoj skip listi, potrebno je da se prolazi kroz listu sabirajući dužine pokazivača kroz koje se pprolaze. Kad se naiđe na pokazivač čija dužina je prevlika za traženi element, spušta se nivo niže.
Na primer, kako bi se pronašao peti element u listi navedenoj iznad (5. čvor), prvo se prolazi pokazivač dužine 1 na najvišem nivou. Potrebno je preći još 4 koraka, ali je sledeći pokazivač (dužine 10) previše dugačak, tako da je potrebno spustiti se jedan nivo niže. Prolazi se pokazivač dužine 3. Sledeći pokazivač na ovom nivou je dužine 2, pa je on predugačak, potrebno je spustiti se na sledeći nivo. Na tom nivou je sledeći pokazivač ponovo dužine 2, tako da je potrebno spustiti se na sledeći (najniži) nivo. Sledeći pokazivač je dužine 1, i nakon što se on prođe, dolazi se do traženog elementa na poziciji 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
Ovaj metod implementiranja indeksiranja je detaljno opisan u Odeljku 3.4 Operacije nad linearnim listama, u „Kuvaru za skip liste“ Vilijama Paga Arhivirano na sajtu Wayback Machine (27. septembar 2011).
Istorija[uredi | uredi izvor]
Skip liste je prvi opisao Vilijam Pag 1989. godine.[5]
Citat autora:
- Skip liste su probabilistička struktura podataka koja će verovatno zameniti balansirana stabla kao uobičajeni implementacioni metod u mnogim primenama. Algoritmi nad skip listama imaju iste asimptotske granice očekivanih vremena kao balansirana stabla, a jednostavniji su i koriste manje prostora.
Vidi još[uredi | uredi izvor]
Reference[uredi | uredi izvor]
- ^ a b 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. Arhivirano iz originala (PDF) 20. 06. 2020. g. Pristupljeno 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. str. 367—375. doi:10.1145/139404.139478 (neaktivno 2023-10-11).
- ^ Shah, Gauri (2003). Distributed Data Structures for Peer-to-Peer Systems (PDF) (Ph.D. thesis). Yale University.
- ^ Pugh, William (april 1989). Concurrent Maintenance of Skip Lists (PS, PDF) (Tehnički izveštaj). Dept. of Computer Science, U. Maryland. CS-TR-2222.
Dodatna literatura[uredi | uredi izvor]
Spoljašnje veze[uredi | uredi izvor]
- „Skip lista“ u Rečniku algoritama i struktura podataka
- Skip liste: POvezane liste sa svojstvima nalik samobalansirajućim binarnim stablima pretrage na MSDN u C# 2.0
- Čemu skip liste?
- Predavanje o skip listama (MIT OpenCourseWare: Uvod u algoritme)
- Open Data Structures - Poglavlje 4 - skipliste
- Grafovi skip stabala, distribuirana verzija skip stabala
- Više o grafovima skip stabala, distribuiranoj verziji skip stabala