Problém s aktualizací seznamu - List update problem

The Aktualizace seznamu nebo Přístup do seznamu problém je jednoduchý model používaný při studiu konkurenční analýza z online algoritmy. Vzhledem k sadě položek v seznamu, kde náklady na přístup k položce jsou úměrné její vzdálenosti od hlavy seznamu, např. A Spojový seznam, a sekvence požadavků na přístupy, je problém přijít se strategií přeskupení seznamu tak, aby byly minimalizovány celkové náklady na přístupy. Změna pořadí může být provedena kdykoli, ale je zpoplatněna. Standardní model zahrnuje dvě akce změny pořadí:

• Bezplatná transpozice položky, ke které se přistupuje kdekoli před její aktuální pozicí;
• Placené provedení jednotkové ceny za výměnu jakýchkoli dvou sousedních položek v seznamu. Výkonnost algoritmů závisí na konstrukci sekvence požadavků protivníky pod různými Nepříznivé modely

Online algoritmus pro tento problém musí změnit pořadí prvků a obsloužit požadavky pouze na základě znalostí dříve požadovaných položek, a proto jeho strategie nemusí mít optimální cenu ve srovnání s offline algoritmem, který uvidí celou sekvenci požadavků a navrhne před podáním prvního požadavku dokončete strategii.

Spolu s původním použitím bylo navrženo, že tento problém má silnou podobnost s problémy zlepšování globálního kontextu a stlačitelnosti po Burrows-Wheelerova transformace. Po této transformaci mají soubory tendenci mít velké oblasti s místně vysokými frekvencemi a účinnost komprese je výrazně zlepšena technikami, které mají tendenci přesouvat často se vyskytující znaky směrem k nule nebo k přední části „seznamu“. Z tohoto důvodu metody a varianty Move-to-Front a počty frekvencí často sledují algoritmus BWT pro zlepšení stlačitelnosti.

Nepříznivé modely

Protivník je entita, která si vybere sekvenci požadavků ${ displaystyle sigma}$ pro algoritmus ALG. Podle toho, zda ${ displaystyle sigma}$ lze změnit na základě strategie ALG, protivníkům jsou dány různé pravomoci a výkon ALG se měří proti těmto protivníkům.

An zapomnětlivý protivník musí postavit celou sekvenci požadavků ${ displaystyle sigma}$ před spuštěním ALG, a platí optimální offline cenu, ${ displaystyle OPT ( sigma)}$ který je porovnáván s ${ displaystyle ALG ( sigma)}$

An adaptivní online protivník dostane další požadavek na základě předchozích výsledků online algoritmu, ale zaplatí za požadavek optimálně a online.

An adaptivní offline protivník dostane další požadavek na základě předchozích výsledků online algoritmu, ale zaplatí optimální offline náklady.

Offline algoritmy

Konkurenční analýza mnoha problémů s aktualizací seznamu byla provedena bez konkrétních znalostí přesné povahy optimálního offline algoritmu (OPT). V O existují algoritmické běhyn2^l(l-1)!) Čas a O (l!) prostor kde n je délka sekvence požadavku a l je délka seznamu.^[1] Nejznámější optimální offline algoritmus závislý na délce sekvence požadavku běží v čase O (l ^ 2 (l − 1)! N) publikovaném Dr. Srikrishnan Divakaran v roce 2014.^[2]

Placené transpozice jsou obecně nutné pro optimální algoritmy. Zvažte seznam (A,b,C) kde A je v čele seznamu a sekvence požadavků C,b,C,b. Optimální offline algoritmus využívající pouze bezplatné výměny by stál 9 (3 + 3 + 2 + 1), zatímco optimální offline algoritmus využívající pouze placené výměny by stál 8. Takže se nemůžeme dostat pryč s pouhým použitím bezplatných transpozic pro optimální offline algoritmus .

Ukázalo se, že je problém s optimální aktualizací seznamu NP-tvrdé od (Ambühl 2000 ) chyba harv: žádný cíl: CITEREFAmbühl2000 (Pomoc).

Online algoritmus

Online algoritmus ALG má konkurenční poměr C pokud pro jakýkoli vstup funguje minimálně stejně dobře jako C krát horší než OPT. tj. pokud existuje ${ displaystyle alpha geq 0}$ tak, že pro všechny sekvence požadavku na konečnou délku ${ displaystyle sigma}$, ${ displaystyle ALG ( sigma) -c.OPT ( sigma) leq alpha}$. Online algoritmy mohou být deterministické nebo randomizované a ukázalo se, že randomizace v tomto případě může skutečně pomoci proti zapomnětlivým protivníkům.

Deterministický

Většina deterministických algoritmů jsou varianty těchto tří algoritmů:

MTF (Přesunout dopředu)

Po přístupu k položce ji přesuňte do přední části seznamu, aniž byste změnili pořadí ostatních položek

TRANS (transpozice)

Po přístupu k položce ji transponujte s bezprostředně předcházející položkou.

FC (počet frekvencí)

U každé položky udržujte počet kmitočtů počtu přístupů k němu - při přístupu k prvku zvyšte počet kmitočtů a změňte pořadí seznamu v sestupném pořadí frekvencí.

Všimněte si, že všechny tyto možnosti používají pouze bezplatné provedení. Ukazuje se, že jak TRANS, tak FC nejsou konkurenceschopní. V klasickém použití výsledku Potenciální metoda analýza (Sleator & Tarjan 1985 ) prokázal, že MTF je 2-konkurenční. Důkaz nevyžaduje výslovnou znalost OPT, ale místo toho počítá počet inverzí, tj. Prvků vyskytujících se v opačném pořadí v seznamech MTF a OPT.

Jakýkoli deterministický algoritmus má spodní hranici ${ displaystyle 2 - { frac {2} {l + 1}}}$ pro seznam délky la MTF je ve skutečnosti optimální deterministický algoritmus aktualizace seznamu. Na typu protivníka nezáleží v případě deterministických algoritmů, protože protivník může spustit kopii deterministického algoritmu sám, aby předpočítal nejchudší sekvenci.

Náhodně

Zvažte následující jednoduchý randomizovaný algoritmus:

BIT

U každé položky v seznamu trochu udržujte. Inicializujte všechny bity rovnoměrně a náhodně na 0 nebo 1. Když je položka přístupná, otočte bit a pokud je 1, přesuňte ji dopředu, jinak ne.

Tento algoritmus je sotva náhodný - provádí všechny své náhodné volby na začátku a ne během běhu. Ukazuje se, že BIT prolomí deterministickou hranici - to je lepší než MTF proti lhostejným protivníkům. Je 7/4 konkurenceschopný. Existují i ​​jiné randomizované algoritmy, například COMB, které fungují lépe než BIT. Boris Teia prokázal dolní hranici 1,5 u libovolného algoritmu aktualizace randomizovaného seznamu.^[3]

Související problémy

Problém s aktualizací seznamu, kde lze prvky vkládat a mazat, se nazývá problém s aktualizací dynamického seznamu, na rozdíl od problému se statickou aktualizací seznamu, kde je povolen pouze přístup k prvkům seznamu. Horní hranice ${ displaystyle 2 - { frac {2} {l + 1}}}$ platí i pro dynamický model.

Existují také různé nákladové modely. V obvyklém modelu úplných nákladů je přístup k prvku umístěnému na určité pozici i náklady i, ale poslední srovnání je nevyhnutelné pro jakýkoli algoritmus, tj. existují i-1 prvky stojící v cestě i. V modelu částečných nákladů jsou tyto náklady na konečné porovnání v celkovém počtu prvků v sekvenci požadavků ignorovány. Pokud jde o náklady na placené transpozice jiné než jednota, P^d jsou použity modely.

Viz také

• Online algoritmus
• Konkurenční analýza
• Algoritmy mezipaměti

Poznámky

Reference

• Sleator, D.; Tarjan, R. (1985), "Amortizovaná účinnost pravidel aktualizace a stránkování seznamu", Komunikace ACM, 28 (2): 202–208, CiteSeerX  10.1.1.367.6317, doi:10.1145/2786.2793.
• Borodin, A.; El-Yaniv, R. (1998). Online výpočet a konkurenční analýza. Cambridge University Press. ISBN  978-0-521-56392-5.

• Ambühl, C. (2000), Offline aktualizace seznamu je těžká, Springer, str. 42–51