Napredna povezana lista

U računarstvu, napredna povezana lista je varijacija povezane liste, koja čuva više elemenata u svakom čvoru. Može dramatično da poveća performanse keša, dok smanjuje opterećenje memorije zato što čuva metapodatke, kao što su pokazivači.^[1]

Struktura

Čvor jedne napredne liste izgleda:

 record node {
     node next       // pokazivač na naredni čvor u listi
     int numElements // broj elemenata u čvoru, do na maxElements
     array elements  // poredak numElements elemenata,
                     // sa prostorom alociranim za maxElements elemenata
 }

Svaki čvor sadrži maksimalan broj elemenata, obično dovoljno velik da bi mogao da popuni keš ili male porcije keša. Pokazivač u listi je i na samu listu, a i na početak niza elemenata. Može da sadrži i pokazivač na predhodni element, kod naprednih dvostruko povezanih lista.

Prilikom učitavanja novog elementa, jednostavno pronađemo u čvoru slobodo mesto (u array elements) i uvećamo maksimalan broj elemenata (numElements). Ako je niz već popunjen, napravimo novi čvor, kao prethodni ili sledeći od postojećeg, i polovinu elemenata iz postojećeg prebacimo u njega.

Kada se element briše, pronađemo čvor u kojem je, pa ga izbrišemo iz niza, umanjujući istovremeno numElements. Ako ovo smanji čvor na ispod polovine popunjenosti, punimo ga elementima iz sledećeg čvora, dok ne bude manje od polovine, uradimo rekurzivno za celu listu i obrišemo višak.

Performanse

Jedna od osnovnih prednosti naprednih povezanih listi je što smanjuje potrebe skladištenja. Svi čvorovi (sa izuzetkom najviše jednog) su polu-puni. Ako je mnogo nasumičnih unosa i brisanja rađeno, prosečan čvor će biti napunjen oko tri četvrtine, a ako su svi unosi i brisanja rađeni samo na početku i na kraju liste, skoro svi čvorovi će biti popunjeni potpuno. Ako pretpostavimo:

m = maxElements, makssimalan broj elemenata u svakom čvoru;
v = cena po čvoru, za čvor i broj elemenata; kada se kaže cena, misli se na efikasnu potrošnju;
s = veličina jednog elementa.

Onda prostor iskorišćen za n elemenata varira između $({\frac {v}{m}}+s)n$ i $({\frac {2v}{m}}+s)n$ . Kao usporedba, klasičnoj povezanoj listi je potrebno $(v+s)n$ prostora, iako je v možda manje, i niz, jedan od najkompaktnijih struktura podataka, traži $sn$ prostora.^[2] Napredna povezana lista efikasno rasporedi cenu v na broj elemenata liste. Na taj način vidimo koliko prostora dobijamo kada je cena velika, maxElements je velik, ili su elementi mali.

Ako su elemeti baš mali, kao na primer bit, efikasna potrošnja može da bude i do 64 puta veća u odnosu na ostale podatke na mnogim mašinama. Takođe, mnogo popularnih alokatora memorije će čuvati male porcije metapodataka za svaki čvor koji je alociran, povećavajući efikasnost cene v. Obe ove stvari povećavaju efikasnost naprednih povezanih lista.

Zato što svaki čvor čuva pokazivač na sledećui niz, next, povratak k-tog elementa iz liste može biti urađeno sa ${\frac {n}{m}}+1$ promašaja keša, do faktora m bolje od običnih povezanih lista. Pored toga, ako je veličina svakog elementa manja u odnosu na veličinu keš linije, lista može da pređe u keš, tako da se dobije manje promašaja nego kod klasične povezane liste. U svakom slučaju, vreme rada se i dalje povećava linearno sa veličinom liste.

Vidi još

Povezana lista

Referencе

^ Shao, Z; Reppy, J. H.; Appel, A.W. (1994), „Unrolling lists”, Conference record of the 1994 ACM Conference on Lisp and Functional Programming, ISBN 978-0-89791-643-1, doi:10.1145/182409.182453
^ Janičić, Predrag; Marić, Filip (2014). Osnove programiranja kroz programski jezik C – Deo II (PDF). стр. 135—141. ^{[мртва веза]}

Литература

Spoljašnje veze

Implementacija napisana u C++ Архивирано на сајту Wayback Machine (9. октобар 2014)
Implementacija napisana u C
Implementacija napisana u Java

[1] Shao, Z; Reppy, J. H.; Appel, A.W. (1994), „Unrolling lists”, Conference record of the 1994 ACM Conference on Lisp and Functional Programming, ISBN 978-0-89791-643-1, doi:10.1145/182409.182453

[2] Janičić, Predrag; Marić, Filip (2014). Osnove programiranja kroz programski jezik C – Deo II (PDF). стр. 135—141. ^{[мртва веза]}

[1]

[2]