Напредна повезана листа

У рачунарству, напредна повезана листа је варијација повезане листе, која чува више елемената у сваком чвору. Може драматично да повећа перформансе кеша, док смањује оптерећење меморије зато што чува метаподатке, као што су показивачи.^[1]

Структура уреди

Чвор једне напредне листе изгледа:

 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
 }

Сваки чвор садржи максималан број елемената, обично довољно велик да би могао да попуни кеш или мале порције кеша. Показивач у листи је и на саму листу, а и на почетак низа елемената. Може да садржи и показивач на предходни елемент, код напредних двоструко повезаних листа.

Приликом учитавања новог елемента, једноставно пронађемо у чвору слободо место (у array elements) и увећамо максималан број елемената (numElements). Ако је низ већ попуњен, направимо нови чвор, као претходни или следећи од постојећег, и половину елемената из постојећег пребацимо у њега.

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

Перформансе уреди

Једна од основних предности напредних повезаних листи је што смањује потребе складиштења. Сви чворови (са изузетком највише једног) су полу-пуни. Ако је много насумичних уноса и брисања рађено, просечан чвор ће бити напуњен око три четвртине, а ако су сви уноси и брисања рађени само на почетку и на крају листе, скоро сви чворови ће бити попуњени потпуно. Ако претпоставимо:

м = maxElements, макссималан број елемената у сваком чвору;
в = цена по чвору, за чвор и број елемената; када се каже цена, мисли се на ефикасну потрошњу;
с = величина једног елемента.

Онда простор искоришћен за н елемената варира између $({\frac {v}{m}}+s)n$ и $({\frac {2v}{m}}+s)n$ . Као успоредба, класичној повезаној листи је потребно $(v+s)n$ простора, иако је в можда мање, и низ, један од најкомпактнијих структура података, тражи $sn$ простора.^[2] Напредна повезана листа ефикасно распореди цену в на број елемената листе. На тај начин видимо колико простора добијамо када је цена велика, maxElements је велик, или су елементи мали.

Ако су елемети баш мали, као на пример бит, ефикасна потрошња може да буде и до 64 пута већа у односу на остале податке на многим машинама. Такође, много популарних алокатора меморије ће чувати мале порције метаподатака за сваки чвор који је алоциран, повећавајући ефикасност цене в. Обе ове ствари повећавају ефикасност напредних повезаних листа.

Зато што сваки чвор чува показивач на следећуи низ, next, повратак к-тог елемента из листе може бити урађено са ${\frac {n}{m}}+1$ промашаја кеша, до фактора м боље од обичних повезаних листа. Поред тога, ако је величина сваког елемента мања у односу на величину кеш линије, листа може да пређе у кеш, тако да се добије мање промашаја него код класичне повезане листе. У сваком случају, време рада се и даље повећава линеарно са величином листе.

Види још уреди

Повезана листа

Референце уреди

^ Схао, З; Реппy, Ј. Х.; Аппел, А.W. (1994), „Унроллинг листс”, Цонференце рецорд оф тхе 1994 АЦМ Цонференце он Лисп анд Фунцтионал Программинг, ИСБН 978-0-89791-643-1, дои:10.1145/182409.182453
^ Јаничић, Предраг; Марић, Филип (2014). Основе програмирања кроз програмски језик C – Део II (ПДФ). стр. 135—141. ^{[мртва веза]}

Литература уреди

Спољашње везе уреди

Имплементација написана у C++ Архивирано на сајту Wayback Machine (9. октобар 2014)
Имплементација написана у C
Имплементација написана у Јава

[1] Схао, З; Реппy, Ј. Х.; Аппел, А.W. (1994), „Унроллинг листс”, Цонференце рецорд оф тхе 1994 АЦМ Цонференце он Лисп анд Фунцтионал Программинг, ИСБН 978-0-89791-643-1, дои:10.1145/182409.182453

[2] Јаничић, Предраг; Марић, Филип (2014). Основе програмирања кроз програмски језик C – Део II (ПДФ). стр. 135—141. ^{[мртва веза]}

[1]

[2]