Samoorganizující se seznam - Self-organizing list

A samoorganizující se seznam je seznam který na základě některých mění pořadí jeho prvků samoorganizující se heuristika zlepšit průměrný přístupová doba. Cílem samoorganizujícího se seznamu je zlepšit efektivitu lineárního vyhledávání přesunutím častěji přístupných položek k hlavě seznamu. Samoorganizující se seznam dosahuje v nejlepším případě téměř konstantní doby pro přístup k prvku. Samoorganizující se seznam používá reorganizační algoritmus k přizpůsobení různým distribucím dotazů za běhu.

Dějiny

Koncept samoorganizujících se seznamů má své kořeny v myšlence organizace činnosti^[1] záznamů v souborech uložených na discích nebo páskách. Jednou z často citovaných diskusí o samoorganizujících se souborech a seznamech je Knuth.^[2] John McCabe poskytl první analýzu algoritmické složitosti strategie Move-to-Front (MTF), kdy je položka po přístupu přesunuta do přední části seznamu.^[3] Analyzoval průměrnou dobu potřebnou k tomu, aby se náhodně seřazený seznam dostal do optimálního pořadí. Optimální řazení seznamu je takové, ve kterém jsou položky seřazeny v seznamu podle pravděpodobnosti, s jakou budou potřebné, přičemž nejdříve je k dispozici nejvíce přístupná položka. Optimální řazení nemusí být předem známé a může se také časem měnit.

McCabe představil transpoziční strategii, ve které je přístupná položka vyměněna s položkou před ní v seznamu. Udělal domněnku, že v průměrném případě transpozice fungovala přinejmenším stejně dobře jako MTF při přibližování optimálního uspořádání záznamů v limitu. Tato domněnka byla později prokázána Rivestem.^[4] McCabe také poznamenal, že buď s transpozicí, nebo s MTF heuristikou, by se optimální pořadí záznamů přiblížilo, i kdyby byla heuristika použita pouze při každém N-tom přístupu, a že by mohla být zvolena hodnota N, která by odrážela relativní náklady na přemístění záznamů hodnota rychlejšího přiblížení k optimálnímu objednání. Byly provedeny další vylepšení a algoritmy navržené výzkumníky, včetně: Rivest, Tenenbaum a Nemes, Knuth a Bentley a McGeoch (např. Analýzy nejhorších případů pro samoorganizující se heuristiku sekvenčního vyhledávání).

Úvod

Nejjednodušší implementace samoorganizujícího se seznamu je jako spojový seznam a proto, že je efektivní při vkládání náhodných uzlů a přidělování paměti, trpí neefektivním přístupem k náhodným uzlům. Samoorganizující se seznam snižuje neefektivitu dynamickým přeskupováním uzlů v seznamu na základě frekvence přístupu.

Neúčinnost procházení propojeného seznamu

Pokud má být v seznamu vyhledán konkrétní uzel, musí být každý uzel v seznamu postupně porovnáván, dokud není dosaženo požadovaného uzlu. V propojeném seznamu je načítání n-tého prvku operací O (n). To je vysoce neefektivní ve srovnání například s polem, kde přístup k n^th element je operace O (1).

Efektivnost samoorganizujících se seznamů

Samoorganizující se seznam přeuspořádává uzly a udržuje ty nejčastěji přístupné v čele seznamu. Obecně platí, že v konkrétním dotazu jsou šance na přístup k uzlu, který byl mnohokrát zpřístupněn, vyšší než šance na přístup k uzlu, který historicky nebyl tak často přístupný. Výsledkem je, že udržování běžně přístupných uzlů v čele seznamu vede ke snížení počtu srovnání požadovaných v průměrném případě k dosažení požadovaného uzlu. To vede k lepší efektivitě a obecně zkrácení doby dotazování.

Implementace samoorganizujícího se seznamu

Implementace a metody samoorganizujícího se seznamu jsou stejné jako u standardu spojový seznam. Propojený seznam a samoorganizující se seznam se liší pouze z hlediska organizace uzlů; rozhraní zůstává stejné.

Analýza doby běhu pro přístup / vyhledávání v seznamu

Průměrný případ

Je možné ukázat, že v průměrném případě je čas potřebný k vyhledávání na samoorganizujícím se seznamu velikosti n

${displaystyle Tavg = 1 * p (1) + 2 * p (2) + 3 * p (3) + ... + n * p (n).}$

kde p (i) je pravděpodobnost přístupu k i-tému prvku v seznamu, který se také nazývá pravděpodobnost přístupu. Pokud je pravděpodobnost přístupu každého prvku stejná (tj. p (1) = p (2) = p (3) = ... = p (n) = 1 / n) pak je řazení prvků irelevantní a průměrná časová složitost je dána vztahem

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

a T (n) v tomto případě nezávisí na individuálních pravděpodobnostech přístupu prvků v seznamu. V případě vyhledávání v seznamech s nejednotnými pravděpodobnostmi přístupu k záznamu (tj. seznamech, ve kterých je pravděpodobnost přístupu k jednomu prvku se liší od jiného), průměrná časová složitost může být drasticky snížena správným umístěním prvků obsažených v seznamu.

To se provádí párováním menších i s většími pravděpodobnostmi přístupu, aby se snížila celková průměrná časová složitost. To lze prokázat následujícím způsobem:

Uvedený seznam: A (0,1), B (0,1), C (0,3), D (0,1), E (0,4)
Bez přeskupení je průměrná doba hledání nutná:

${displaystyle T (n) = 1 * 0,1 + 2 * 0,1 + 3 * 0,3 + 4 * 0,1 + 5 * 0,4 = 3,6}$

Nyní předpokládejme, že uzly jsou přeskupeny tak, aby ty uzly s nejvyšší pravděpodobností přístupu byly umístěny nejblíže vpředu, takže přeskupený seznam je nyní:
E (0,4), C (0,3), D (0,1), A (0,1), B (0,1)
Zde je průměrná doba hledání:

${displaystyle T (n) = 1 * 0,4 + 2 * 0,3 + 3 * 0,1 + 4 * 0,1 + 5 * 0,1 = 2,2}$

Průměrná doba potřebná k vyhledání v organizovaném seznamu je tedy (v tomto případě) přibližně o 40% kratší než čas potřebný k vyhledání náhodně uspořádaného seznamu. Jedná se o koncept samoorganizovaného seznamu v tom, že průměrná rychlost načítání dat se zvyšuje přeskupením uzlů podle přístupové frekvence.

Nejhorší případ

V nejhorším případě je prvek, který má být umístěn, na samém konci seznamu, ať už je to normální seznam, nebo samoorganizovaný, a proto k jeho dosažení je třeba provést n srovnání. Nejhorší doba běhu lineárního vyhledávání v seznamu je tedy O (n) nezávislá na typu použitého seznamu. Upozorňujeme, že výraz pro průměrnou dobu vyhledávání v předchozí části je pravděpodobnostní. Udržování běžně používaných prvků v čele seznamu jednoduše snižuje pravděpodobnost výskytu nejhoršího případu, ale ne zcela jej eliminuje. I v samoorganizujícím se seznamu, pokud má být zpřístupněn prvek s nejnižší pravděpodobností přístupu (zjevně umístěný na konci seznamu), musí být celý seznam kompletně projet, aby jej bylo možné načíst. Toto je hledání v nejhorším případě.

Nejlepší případ

V nejlepším případě je uzlem, který má být prohledán, ten, ke kterému se běžně přistupuje, a byl tedy identifikován seznamem a udržován v čele. To bude mít za následek téměř stálý provoz. Ve značce big-oh je v nejlepším případě přístup k prvku operací O (1).

Techniky pro přeskupení uzlů

Při objednávání prvků v seznamu nejsou pravděpodobnosti přístupu prvků obecně známy předem. To vedlo k vývoji různých heuristik pro přiblížení optimálního chování. Základní heuristika použitá k přeskupení prvků v seznamu je:

Metoda Move to front (MTF)

Tato technika přesouvá prvek, který je přístupný do záhlaví seznamu. To má tu výhodu, že je snadno implementováno a nevyžaduje žádnou další paměť. Tato heuristika se také rychle přizpůsobuje rychlým změnám v distribuci dotazů. Na druhou stranu může tato metoda upřednostňovat zřídka přístupné uzly - například pokud se k neobvyklému uzlu přistupuje i jednou, je přesunut do záhlaví seznamu a je mu dána maximální priorita, i když k němu nebude často přistupováno budoucnost. Tyto uzly s „nadhodnocením“ ničí optimální uspořádání seznamu a vedou ke zpomalení doby přístupu pro běžně dostupné prvky. Další nevýhodou je, že se tato metoda může stát příliš flexibilní, což vede k příliš rychlým změnám přístupových vzorů. To znamená, že díky velmi krátkým vzpomínkám na přístupové vzory lze i optimální uspořádání seznamu okamžitě narušit přístupem k řídkému uzlu v seznamu.

Pokud je vybrán 5. uzel, přesune se dopředu

Při výběru t-té položky: -li je vybrána položka i: ​​přesune položku i do záhlaví seznamu

Metoda počítání

V této technice se počítá, kolikrát byl každý uzel vyhledáván, tj. Každý uzel uchovává samostatnou proměnnou čítače, která se zvyšuje pokaždé, když je volána. Uzly jsou poté přeskupeny podle klesajícího počtu. V čele seznamu jsou tedy uzly s nejvyšším počtem, tj. Nejčastěji přístupné. Primární výhodou této techniky je, že je obecně realističtější při představování skutečného vzoru přístupu. Existuje však požadavek na přidanou paměť, zachování proměnné čítače pro každý uzel v seznamu. Tato technika se také rychle nepřizpůsobuje rychlým změnám v přístupových vzorcích. Například: pokud počet hlavových prvků říká A je 100 a pro jakýkoli uzel po něm B je 40, pak i když se B stane novým nejčastěji používaným prvkem, musí být stále přístupný alespoň (100 - 40 = 60 ) krát, než se může stát hlavním prvkem, a tím optimalizovat pořadí seznamu.

Pokud je pátý uzel v seznamu vyhledán dvakrát, bude zaměněn za čtvrtý

init: count (i) = 0 pro každou položku iAt t-th výběr položky: -li prohledává se položka i: ​​count (i) = count (i) + 1 přeskupit položky podle počtu

Metoda transpozice

Tato technika zahrnuje výměnu přístupového uzlu za jeho předchůdce. Proto pokud je přístupný jakýkoli uzel, je zaměněn s uzlem vpředu, pokud nejde o hlavní uzel, čímž se zvyšuje jeho priorita. Tento algoritmus je opět snadno implementovatelný a prostorově efektivní a je pravděpodobnější, že udrží často přístupné uzly v přední části seznamu. Metoda transpozice je však opatrnější. tj. bude trvat mnoho přístupů, aby se prvek přesunul do čela seznamu. Tato metoda také neumožňuje rychlou reakci na změny v distribucích dotazů na uzlech v seznamu.

Pokud je vybrán 5. uzel v seznamu, bude zaměněn za 4. uzel

Při výběru t-té položky: -li je vybrána položka i: -li i není vedoucí seznamu: vyměnit položku i s položkou (i - 1)

Jiné metody

Výzkum byl zaměřen na fúzi výše uvedených algoritmů pro dosažení lepší účinnosti.^[5] Bitnerův algoritmus zpočátku používá MTF a poté používá metodu transpozice pro jemnější přeskupení. Některé algoritmy jsou randomizovány a snaží se zabránit nadměrnému odměňování zřídka přístupných uzlů, které se mohou v algoritmu MTF vyskytnout. Jiné techniky zahrnují reorganizaci uzlů na základě výše uvedených algoritmů po každém n přístupech v seznamu jako celku nebo po n přístupech v řadě na konkrétním uzlu atd. Některé algoritmy mění uspořádání uzlů, ke kterým se přistupuje na základě jejich blízkosti k hlavnímu uzlu, například: Swap-With-Parent nebo Move-To-Parent algorithms. Jiná třída algoritmů se používá, když vyhledávací vzor vykazuje vlastnost nazvanou referenční lokalita, přičemž v daném časovém intervalu je pravděpodobnější, že bude přístupná pouze menší podmnožina seznamu. Toto se také označuje jako závislý přístup, kde pravděpodobnost přístupu konkrétního prvku závisí na pravděpodobnosti přístupu jeho sousedních prvků. Takové modely jsou běžné v reálných aplikacích, jako jsou databázové nebo souborové systémy a správa paměti a ukládání do mezipaměti. Běžným rámcem pro algoritmy zabývající se takovými závislými prostředími je změnit uspořádání seznamu nejen na základě přístupu k záznamu, ale také na záznamech v jeho blízkosti. To efektivně zahrnuje reorganizaci podlistu seznamu, ke kterému záznam patří.

Aplikace samoorganizujících se seznamů

Překladatelé jazyků, jako jsou překladatelé a tlumočníci, používají ke správě samoorganizující se seznamy tabulky symbolů během kompilace nebo interpretace zdrojového kódu programu. V současné době probíhá výzkum začlenění datové struktury samoorganizujícího se seznamu do vestavěné systémy ke snížení aktivity přechodu sběrnice, která vede k ztrátě energie v těchto obvodech. Tyto seznamy se také používají v umělá inteligence a neuronové sítě stejně jako samonastavovací programy. Algoritmy použité v samoorganizujících se seznamech se také používají jako algoritmy ukládání do mezipaměti jako v případě algoritmu LFU.

Jednoduché metody Move to Front a transpose jsou použitelné také ve sbírkách v reálném světě: například organizování zásuvky na koření nahrazením použitých položek do přední části zásuvky nebo transpozice čisticího předmětu s jeho nejbližším sousedem, pokud je používán.

Poznámky

Reference

• Vlastní organizace (PDF), 2004
• NIST DADS vstup
• A Drozdek, Data Structures and Algorithms in Java Third edition
• Amer, Abdelrehman; B. John Oommen (2006), Seznamy na seznamech: Rámec pro samoorganizující se seznamy v prostředích s referenční lokalitou, Přednášky v informatice, 4007, doi:10.1007/11764298, ISBN  978-3-540-34597-8