Самоорганизована листа

Самоорганизована листа је листа код које се елементи распоређују на основу самоорганизованог хеуристичног алгоритма који побољшава просечно време приступа. Циљ овакве листе је да се побољша ефикасност линеарне претраге померањем чешће приступаним елементима ка предњем крају листе. Листа само-организовања остварује готово константно време за приступ елементима у најбољем случају. Користи се алгоритам за препознавање како би се прилагодила различитим врстама захтева у току рада.

Историја

Концепт самоорганизованих листи увео је МцЦабе 1965. године. У раном периоду он је представио две хеуристике - Померање ка предњем крају (енг. Мове то Фронт Метход (МТФ)) и Правило замене (енг. Транспосе Метход). Временом, прављена су различита побољшања, а алгортиме су проналазили Роналд Ривест, Тененбаум и Немес, D. Кнутх и други.

Увод

Најједноставнија имплементација самоорганизоване листе је у облику повезане листе. Овај начин је ефикасан у случајном уметању чвора и алокацији меморије, али трпи због неефикасног приступа тим случајним чворовима.

Нефикасност самоорганизованих листи

Ако посебан чвор треба да се пронађе у листи, сваком чвору у листи мора секвенцијално да се приступи док се не достигне жељени чвор. У повезаној листи, за проналажење н-тог елемента потребно је О(н) операција. Ово је веома неефикасно у поређењу са низовима где је, на пример, приступ н-том елементу О(1) операција.

Ефикасност самоорганизованих листи

Самоорганизована листа чува чворове којима се најчешће приступа на врху листе. Генерално , у одређеном упиту , шансе за приступање чвору којем је раније приступљено много пута веће су него шансе за приступ неком чвору којем раније није тако често приступано. Као резултат тога, држећи најчешће приступане чворове на предњем крају листе резултује смањеном броју поређења потребних, у просечном случају, да се достигне жељени чвор. То доводи до боље ефикасности и генерално смањеном броју упита.

Имплементација самоорганизованих листи

Имплементација и методе самоорганизованих листи су идентични са онима за стандардну повезану листу. Повезана листа и самоорганизована листа се разликују само у погледу организовања чворова, интерфејс остаје исти.

Анализа времена потребног за приступ/претрагу у листи

Просечан случај

Може се показати да у просечном случају, време потребно за претрагу у самоорганизованој листи величине н је:

$Tprosek=1*p(1)+2*p(2)+3*p(3)+...+n*p(n).$

где је п(и) вероватноћа приступа и-том елементу у листи; Ако је вероватноћа приступа сваког елемента иста ( тј. п(1) = п(2) = п(3) = ... = п(н) = 1/н ), онда је редослед елемената ирелевантан и просечна временска сложеност износи:

$T(n)=1/n+2/n+3/n+...+n/n=(1+2+3+...+n)/n=(n+1)/2$

и Т(н) не зависи од вероватноће појединачних приступа елеменатима у листи у овом случају. Међутим, у случају претраге на листи са нејединственим записом вероватноће приступа елементима (тј. оне листе код којих се вероватноћа приступа једног елемента разликује од другог), просечна сложеност може бити драстично смањена правилним постављањем елемената садржаних у листи. То се ради упаривањем мањег $i$ са већим вероватноћама приступа како би да смањило укупну просечно време сложености. Ово може да се покаже на следећи начин: Дата је листа: А(0.1), Б (0.1), C (0.3), D (0.1), Е (0.4). Без прераспоређивања, просечно време потребно је претраживање:

$T(n)=1*0.1+2*0.1+3*0.3+4*0.1+5*0.4=3.6$

Сада претпоставимо да су чворови преуређене тако да су они са највећом вероватноћом приступа постављени на предњем крају, тако да је сада преуређена листа: Е(0.4), C(0.3), D(0.1), А(0.1), Б(0.1) Овде, сложеност износи:

$T(n)=1*0.4+2*0.3+3*0.1+4*0.1+5*0.1=2.2$

Тако је просечно време потребно за тражење у организованој листи је ( у овом случају ) око 40% мање у односу на време које је потребно за тражење у насумично уређеној листи. Ово је концепт самоорганизованих листи код којих се просечна брзина преузимања података повећава са прераспоређивањем чворова према њиховој фреквенцији приступа.

Најгори случај

У најгорем случају, елемент који треба пронаћи налази се на самом крају листе; било то обична или самоорганизована листа, мора бити направљено н поређења како би се се стигло до тог елемента. Стога, у најгорем случају време извршавања линеарне претраге на листи је О(н) независно од типа листе који се користи. Имајте на уму да израз просечне сложености времена за претрагу у претходном одељку је само једна вероватноћа. Задржавање елемената којима се најчешће приступа на челу листе једноставно смањује вероватноћу јављања најгорег случаја, али га не елиминише у потпуности! Чак и у самоорганизованој листи, ако треба да се приступи елементу са најмањом вероватноћом приступа (очигледно сместеном на крај листе), цела листа мора да се предје. То је најгори слуцај.

Најбољи случај

У најбољем случају, чвор који тражимо је бас онај чвор којем се најчешће приступа и он представља главу листе. Ово ће резултовати готово констатан број операција, па је у $O$ - нотацији, у најбољем случају, сложеност приступа том елементу О(1).

Технике прераспоређивања чворова

Током постављања елемената у листу, вероватноће приступа елементима нису опште познате унапред. Ово је довело до развоја различитих хеуристика да приближе оптимално понашање. Основне хеуристике које се користе да бисте променили редослед елемената у листи су:

Померање ка предњем крају(МТФ метод)

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

Ако се приступи 5. чвору у листи, он се помера на чело листе

    Za i-ti čvor važi:
         if čvor i je pristupljen:
                 premesti i-ti čvor na čelo liste

Метод бројања

У овој техници, броји се колико пута је сваки чвор тражен, односно сваки чвор води посебну бројачку променљиву која се повећава сваки пут када се чвору приступи. Чворови су затим распоређени у опадајућем редоследу. Дакле, чворови са највећим бројем, односно најчешће приступани, чувају се на челу листе. Основна предност ове технике је да генерално реалније приказује стварни образац приступа. Међутим, постоји додатни меморијски захтев, тј простор за бројачку променљиву за сваки чвор у листи. Такође, ова техника се не прилагођава брзом наглим променама у обрасцима приступа. На пример: ако бројач за елемент главе (А) износи 100, а за неки други чвор након њега (Б) је 40, онда чак и ако Б постане нови најчешће приступани елеменат, њему се мора приступити најмање (100 - 40 = 60 ) пута пре него што он сам може постати глава листе, како би редослед листе постао оптималан.

Ако се 5. чвору у листи приступи 3 пута, изамениће се ца 4.

    init: count(i) = 0 za svaki čvor i
    Za i-ti čvor važi:
       if čvor i je pristupljen:
           count(i) = count(i) + 1
           sortiraj listu prema promenjivoj count(i)

Метод замене

Ова техника подразумева замену чвора којем се приступа са својим претходником. Према томе, ако је приступљено чвору, он се мења са чвором иза, осим ако је чвор глава; тада само повећава свој приоритет. Овај алгоритам се лако имплементира и просторно је ефикасан (не захтева додатан меморијски простор) и лакше је чувати чешће приступане чворове на предњем делу листе. Међутим, овај метод је знатно опрезнији, односно потребан је велики број приступа да би елемент дошао на врх листе. Овај метод такође не дозвољава брзе одговоре на нагле промене у расподели захтева за чворове у листи.

Ако се приступи 5. чвору у листи, он ће бити замењен са 4.

    Za i-ti čvor važi:
         if čvor i je pristupljen:
             if čvor i nije glava liste:
                     zameni čvor i sa čvorom i-1

Друге методе

Истраживање су се фокусирала на спајање горе наведених алгоритама за постизање боље ефикасности. Битнеров алгоритам користи МТФ метод у почетку, а затим, за финије прерасподеле, користи метод замене. Неки алгоритми су насумични и покушавају да спрече "претерано награђивање" чворова којима се ретко приступа, које може настати у МТФ алгоритму. Остале технике укључују реорганизацији чворове на основу наведених алгоритама после сваких н приступа листи у целини или после н приступа у низу на одређеном чвору и тако даље. Неки алгоритми преуређују чворове којима је приступљено на основу њихове близине глави листе, на пример: Замени са родитељем (енг. Сwап-Wитх-Парент) или Додај до родитеља (енг. Мове-То-Парент) алгоритами. Друга класа алгоритама се користе када образац за претраживање показује својство које се зове локалност веза, где у датом временском интервалу, само за мањи подскуп листе је највише вероватно да ће се приступити. Ово се такође назива и зависним приступом јер вероватноћа приступа одређеном елементу зависи од вероватноће приступа његовим суседним елеменатима. Такви модели су уобичајени у реалним апликацијама као што су базе података или фајл системи и управљање меморијом и кеширање. Заједнички оквир за алгоритаме који се баве таквим зависним окружењима је да реорганизује листу не само на основу евиденције приступа за сам чвор, већ и на евиденцији за чворове близу њега. То практично подразумева реорганизацију подлисте листе на коју се евиденција односи.

Апликације које користе самоорганизоване листе

Језички преводиоци попут компајлера и интерпретатора користе самоорганизоване листе за одржавање симбол-табеле током компилације или интерпретације изворног кода програма. Тренутно је у току пројекат који би требао да укључи структуру података самоорганизоване листе у системе да би смањиле активности магистрала које доводе до расипања снаге у тим круговима. Ове листе се такође примењују у вештачкој интелигенцији и неуронским мрежама, као и у само-подешавајућим програмаима. Алгоритми који се користе у самоорганизованим листама се такође користе као алгоритми за кеширање, као на пример ЛФУ алгоритам.

Референце

• Vlajic, N (2003), Self-Organizing Lists (PDF), Архивирано из оригинала (pdf) 06. 05. 2012. г., Приступљено 22. 03. 2014 
• Self Organization (PDF), 2004, Архивирано из оригинала (pdf) 14. 04. 2012. г., Приступљено 22. 03. 2014 
• NIST DADS entry
• A Drozdek, Data Structures and Algorithms in Java Third edition
• Amer, Abdelrehman; B. John Oommen (2006), Lists on Lists: A Framework for Self Organizing-Lists in Environments with Locality of Reference Lists on Lists: A Framework for Self-organizing Lists in Environments with Locality of Reference (pdf)