Problem z utrzymaniem porządku

W informatyce problem utrzymania porządku polega na utrzymaniu całkowicie uporządkowanego zestawu obsługującego następujące operacje:

insert(X, Y) , która wstawia X bezpośrednio po Y w całkowitej kolejności;
order(X, Y) , która określa, czy X poprzedza Y w całkowitym zamówieniu; I
delete(X) , który usuwa X ze zbioru.

Paul Dietz po raz pierwszy wprowadził strukturę danych, aby rozwiązać ten problem w 1982 roku. Ta struktura danych obsługuje wstawianie (X, Y) w zamortyzowanym czasie i $O (\ log n)}$ Displaystyle order(X, Y) w stałym czasie, ale nie obsługuje usuwania. Athanasios Tsakalidis użył drzew BB[α] z tymi samymi granicami wydajności, które obsługują usuwanie w ${\ Displaystyle O (\ log n)}$ i ulepszona wydajność wstawiania i usuwania do zamortyzowanego czasu z pośrednim ${\ Displaystyle O (1)}$ Dietz i Daniel Sleator opublikowali ulepszenie stałego czasu najgorszego przypadku w 1987 r. Michael Bender, Richard Cole i Jack Zito opublikowali znacznie uproszczone alternatywy w 2004 r. Bender, Fineman, Gilbert, Kopelowitz i Montes również opublikowali rozwiązanie bez amortyzacji w 2017 r.

Wydajne struktury danych do utrzymania porządku mają zastosowanie w wielu obszarach, w tym trwałości struktury danych , algorytmach grafowych i odpornych na uszkodzenia strukturach danych.

Etykietowanie listy

Problemem związanym z problemem utrzymania porządku jest problem etykietowania listy , w którym zamiast operacji order(X, Y) rozwiązanie musi zachować przypisanie etykiet z uniwersum liczb całkowitych $\{1,2,\ldots ,m\}$ do elementów zbioru takich, że X poprzedza Y w porządku całkowitym wtedy i tylko wtedy, gdy X ma przypisaną mniejszą etykietę niż Y. Musi również obsługiwać etykietę operacji (X) zwracając etykietę dowolnego węzła X. Zwróć uwagę, że kolejność (X, Y) można zaimplementować po prostu porównując label (X) i label (Y), tak że każde rozwiązanie problemu etykietowania list natychmiast daje jedno rozwiązanie problemu utrzymania porządku. W rzeczywistości większość rozwiązań problemu utrzymania porządku to rozwiązania problemu etykietowania list, rozszerzone o poziom pośredniej struktury danych w celu poprawy wydajności. Przykład tego zobaczymy poniżej.

W przypadku problemu z etykietowaniem list w zestawach o rozmiarze do $koszt$ etykietowania list zależy od tego, jak duża $\ displaystyle n}$ funkcją ${$ . Odpowiedni zakres parametrów dla utrzymania porządku jest dla ${\ Displaystyle m = n ^ {1 + \ Theta (1)}}$ , dla których ${\ Displaystyle O ( \log n)}$ znane jest rozwiązanie z zamortyzowanym kosztem i znane jest rozwiązanie z amortyzacją w stałym czasie ${\ Displaystyle 2 ^ {\ Omega (n)}}$

O(1) amortyzowane wstawienie pośrednie

Pośredniość to technika stosowana w strukturach danych, w której problem jest dzielony na wiele poziomów struktury danych w celu poprawy wydajności. Zazwyczaj problem rozmiaru $problemy$ podzielony na rozmiaru $displaystyle \ log n} n /$ $/\ log n}$ . Na przykład ta technika jest używana w szybkich próbach y . Ta strategia działa również w celu poprawy wydajności wstawiania i usuwania struktury danych opisanej powyżej do stałego czasu amortyzacji. $czasem$ każdego rozwiązania problemu z etykietowaniem list z wstawiania i usuwania

Struktura danych utrzymania porządku z pośredniością. Elementy całkowitego zamówienia są przechowywane w

N

)

\

każda która ma swojego przedstawiciela w drzewie kozłów ofiarnych .

Nowa struktura danych jest całkowicie przebudowywana, gdy staje się zbyt duża lub zbyt mała. Niech będzie liczbą elementów całkowitego porządku, kiedy był on ostatnio $przebudowywany$ Struktura danych jest odbudowywana za każdym razem, $usunięcie$ przez Ponieważ odbudowę można przeprowadzić w czasie liniowym, nie wpływa to na amortyzowaną wydajność wstawiania i usuwania.

$Ω$ operacji odbudowy $elementy$ ${\ Displaystyle \ Omega (\ log N)}$ zamówienia są dzielone na podrzędne, z . Problem etykietowania list jest rozwiązany na zbiorze węzłów reprezentujących każdą z list podrzędnych w ich oryginalnej kolejności. Etykiety dla tego podproblemu są traktowane jako wielomiany --- powiedzmy ${\ Displaystyle m = N ^ {2}}$ , aby można je było porównywać w stałym czasie i aktualizować w czasie zamortyzowanym ${\ Displaystyle O (\ log N)} .$

Dla każdej podlisty tworzona jest podwójnie połączona lista jej elementów, w której każdy element zawiera wskaźnik do jego przedstawiciela w drzewie oraz lokalną etykietę całkowitą. Lokalne etykiety $czemu$ również pobierane z zakresu , dzięki $można$ porównywać w stałym czasie, ale ponieważ każdy lokalny problem dotyczy tylko $\ displaystyle \ Theta (\ log N)}$ elementy, zakres etykiet ${\ displaystyle m}$ jest wykładniczy pod względem liczby etykietowanych elementów. $W ten$ można je aktualizować czasie

Zobacz problem z etykietowaniem list, aby uzyskać szczegółowe informacje na temat obu rozwiązań.

Zamówienie

Biorąc pod uwagę węzły podlisty X i Y, na order(X, Y) można odpowiedzieć, najpierw sprawdzając, czy dwa węzły znajdują się na tej samej podliście. Jeśli tak, ich kolejność można ustalić, porównując ich lokalne etykiety. W przeciwnym razie porównuje się etykiety ich przedstawicieli w pierwszym problemie z etykietowaniem list. Te porównania zajmują stały czas.

Wstawić

Biorąc pod uwagę nowy węzeł podlisty dla X i wskaźnik do węzła podlisty Y, insert(X, Y) wstawia X bezpośrednio po Y na liście podrzędnej Y, jeśli jest miejsce na X na liście, to znaczy jeśli długość lista nie jest większa niż ${\ displaystyle 2 \ log N}$ po wstawieniu. Jej etykieta lokalna jest nadawana przez algorytm etykietowania listy lokalnej dla etykiet wykładniczych. Ta $_$ .

Jeśli lista lokalna jest przepełniona, jest dzielona równo na dwie listy o rozmiarze ${\ displaystyle \ log N}$ , a elementy na każdej liście otrzymują nowe etykiety z ich (niezależnych) zakresów. Tworzy to nową podlistę, która jest wstawiana do listy podlist, a nowy węzeł podlisty otrzymuje etykietę na liście podlist przez algorytm etykietowania list. Na końcu X jest wstawiany do odpowiedniej listy.

Ta sekwencja operacji zajmuje czas ${\ Displaystyle O (\ log$ $N$ utworzenia listy były wstawiane lub ostatni podział. Zatem amortyzowany czas na włożenie wynosi ${\ Displaystyle O (1)}$ .

Usuwać

Biorąc pod uwagę węzeł podlisty X do usunięcia, delete(X) po prostu usuwa X ze swojej podlisty w stałym czasie. Jeśli to pozostawi podlistę pustą, musimy usunąć przedstawiciela listy podrzędnych. $(\ log N)}$ co najmniej elementy zostały usunięte z podlisty od ${$ możemy sobie pozwolić na wydanie czasu, zamortyzowany koszt usunięcia wynosi ${\ Displaystyle O (1)}$ .

Linki zewnętrzne

Dwa uproszczone algorytmy utrzymywania porządku na liście. - Ten artykuł ( Michael A. Bender , Richard Cole, Erik D. Demaine , Martin Farach-Colton i Jack Zito, 2002) przedstawia strukturę danych z etykietami list z zamortyzowaną wydajnością, która nie przechowuje jawnie drzewa. Podana analiza jest prostsza niż ta podana przez (Dietz i Sleator, 1987) dla podobnej struktury danych.