Problem z aktualizacją listy

Aktualizacja listy lub problem dostępu do listy to prosty model używany w badaniu konkurencyjnej analizy algorytmów online . Mając zestaw elementów na liście, gdzie koszt dostępu do elementu jest proporcjonalny do jego odległości od początku listy, np. Linked List i sekwencję żądań dostępu, problemem jest wymyślenie strategii zmiany kolejności listę tak, aby zminimalizować całkowity koszt dostępów. Ponowne zamówienie można wykonać w dowolnym momencie, ale wiąże się to z kosztami. Model standardowy obejmuje dwie akcje zmiany kolejności:

Swobodna transpozycja elementu, do którego uzyskuje się dostęp, w dowolnym miejscu przed jego aktualną pozycją;
Płatna transpozycja kosztu jednostkowego za wymianę dowolnych dwóch sąsiednich pozycji na liście. Wydajność algorytmów zależy od konstruowania sekwencji żądań przez adwersarzy w ramach różnych modeli adwersarzy

Algorytm online dla tego problemu musi zmienić kolejność elementów i obsługiwać żądania tylko na podstawie wiedzy o wcześniej żądanych elementach, a zatem jego strategia może nie mieć optymalnego kosztu w porównaniu z algorytmem offline, który widzi całą sekwencję żądań i opracowuje kompletna strategia przed obsłużeniem pierwszego żądania.

Sugerowano, że wraz z jego pierwotnymi zastosowaniami problem ten jest bardzo podobny do problemów związanych z poprawą globalnego kontekstu i ściśliwości po transformacji Burrowsa-Wheelera . Po tej transformacji pliki mają zwykle duże obszary z lokalnie wysokimi częstotliwościami, a wydajność kompresji jest znacznie poprawiona dzięki technikom, które mają tendencję do przesuwania często występujących znaków w kierunku zera lub początku „listy”. Z tego powodu metody i warianty funkcji Move-to-Front i liczenia częstotliwości często są zgodne z algorytmem BWT w celu poprawy ściśliwości.

Modele przeciwników

Przeciwnik to jednostka, która może wybrać sekwencję $dla$ algorytmu ALG . W zależności od tego, czy $ALG$ zmienić w oparciu o strategię , przeciwnicy otrzymują różne uprawnienia, a wydajność ALG jest mierzona w stosunku do tych przeciwników.

Nieświadomy przeciwnik musi $płaci$ całą sekwencję żądań uruchomieniem $która$ cenę w trybie offline , z ${\ Displaystyle ALG (\ sigma)}$

Adaptacyjny przeciwnik online może wykonać następne żądanie w oparciu o poprzednie wyniki algorytmu online, ale płaci za żądanie optymalnie i online.

Adaptacyjny przeciwnik offline może wykonać następne żądanie w oparciu o poprzednie wyniki algorytmu online, ale płaci optymalny koszt offline.

Algorytmy offline

Analiza konkurencji dla wielu problemów z aktualizacją list została przeprowadzona bez konkretnej wiedzy na temat dokładnej natury optymalnego algorytmu offline (OPT). Istnieje algorytm działający w czasie O( n 2 ^l ( l -1)!) i przestrzeni O ( l !), gdzie n to długość sekwencji żądań, a l to długość listy. Najbardziej znany optymalny algorytm offline zależny od długości sekwencji żądań działa w czasie O(l^2(l−1)!n) opublikowany przez dr Srikrishnana Divakarana w 2014 roku.

Płatne transpozycje są na ogół niezbędne dla optymalnych algorytmów. Rozważmy listę ( a , b , c ), gdzie a znajduje się na początku listy, oraz sekwencję żądań c , b , c , b . Optymalny algorytm offline korzystający tylko z bezpłatnych wymian kosztowałby 9 (3+3+2+1), podczas gdy optymalny algorytm offline wykorzystujący tylko płatne wymiany kosztowałby 8. Nie możemy więc uciec od korzystania tylko z bezpłatnych transpozycji dla optymalnego algorytmu offline .

Problem aktualizacji optymalnej listy okazał się NP-trudny przez ( Ambühl 2000 ) .

Algorytm online

Algorytm online ALG ma współczynnik konkurencyjności c , jeśli dla dowolnego wejścia działa co najmniej tak dobrze, jak c razy gorzej niż OPT. tj $długości$ jeśli istnieje taki $,$ że dla wszystkich sekwencji żądań skończonej ${\ Displaystyle ALG (\ sigma) -c.OPT (\ sigma) \ równoważnik \ alfa}$ . Algorytmy online mogą być deterministyczne lub losowe i okazuje się, że w tym przypadku randomizacja może naprawdę pomóc w walce z nieświadomymi przeciwnikami.

deterministyczny

Większość algorytmów deterministycznych to warianty tych trzech algorytmów:

MTF (Przenieś na początek): Po uzyskaniu dostępu do elementu przenieś go na początek listy bez zmiany kolejności innych elementów
TRANS (Transponuj): Po uzyskaniu dostępu do elementu transponuj go z elementem bezpośrednio poprzedzającym.
FC (Frequency Count): Dla każdego elementu utrzymuj częstotliwość dostępu do niego - gdy element jest uzyskiwany, zwiększ jego liczbę częstotliwości i zmień kolejność listy w malejącej kolejności częstotliwości.

Zauważ, że wszystkie one używają tylko wolnych transpozycji. Okazuje się, że zarówno TRANS, jak i FC nie są konkurencyjne. W klasycznym wyniku przy użyciu metody analizy potencjału ( Sleator & Tarjan 1985 ) udowodniono, że MTF jest 2-konkurencyjna. Dowód nie wymaga jawnej znajomości OPT, lecz zlicza liczbę inwersji, czyli elementów występujących w przeciwnej kolejności na listach MTF i OPT.

algorytm deterministyczny ma dolną granicę dla listy o długości $l ,$ rzeczywistości optymalnym deterministycznym algorytmem aktualizacji Typ przeciwnika nie ma znaczenia w przypadku algorytmów deterministycznych, ponieważ przeciwnik może samodzielnie uruchomić kopię algorytmu deterministycznego, aby wstępnie obliczyć najbardziej katastrofalny ciąg.

Randomizowane

Rozważ następujący prosty losowy algorytm:

BIT: Dla każdego elementu na liście zachowaj bit. Zainicjuj wszystkie bity równomiernie i losowo na 0 lub 1. Gdy element jest dostępny, odwróć bit, a jeśli jest to 1, przesuń go na przód, w przeciwnym razie nie.

Ten algorytm jest prawie losowy - wszystkie losowe wybory dokonuje na początku, a nie w trakcie biegu. Okazuje się, że BIT przełamuje deterministyczną granicę - jest lepszy niż MTF przeciwko nieświadomym adwersarzom. Jest konkurencyjny 7/4. Istnieją inne losowe algorytmy, takie jak COMB, które działają lepiej niż BIT. Boris Teia wykazał dolną granicę 1,5 dla dowolnego algorytmu aktualizacji losowej listy.

Powiązane problemy

Problem z aktualizacją listy, w którym elementy mogą być wstawiane i usuwane, nazywany jest problemem z aktualizacją listy dynamicznej, w przeciwieństwie do problemu z aktualizacją listy statycznej, w którym dozwolony jest dostęp tylko do elementów listy. Górna $_$ modelu

Istnieją również różne modele kosztów. W zwykłym modelu kosztów pełnych dostęp do elementu znajdującego się na pozycji i kosztuje i , ale ostatnie porównanie jest nieuniknione dla każdego algorytmu, tzn. na drodze do i stoi i-1 elementów . W modelu kosztów częściowych te końcowe koszty porównania, sumujące się do liczby elementów w sekwencji żądań, są ignorowane. Dla kosztów płatnych transpozycji innych niż jedność stosuje się modele P ^{d .}

Zobacz też

Notatki

Sleator, D .; Tarjan, R. (1985), „Zamortyzowana efektywność aktualizacji list i reguł stronicowania”, Communications of the ACM , 28 (2): 202–208, CiteSeerX 10.1.1.367.6317 , doi : 10.1145/2786.2793 , S2CID 2494305 .
Borodin, A .; El-Janiw, R. (1998). Obliczenia online i analiza konkurencji . Wydawnictwo Uniwersytetu Cambridge. ISBN 978-0-521-56392-5 .

Ambühl, C. (2000), Aktualizacja listy offline jest np-trudna , Springer, s. 42–51