Dzielony stos

Co wiadomo na temat struktur danych, które mogą utrzymywać sekwencję elementów podlegających następującym dwóm operacjom?

Naciśnij (x): dodaj x na końcu sekwencji i zwróć identyfikator jej pozycji w sekwencji
Wyodrębnij (S): biorąc pod uwagę nieuporządkowany zestaw identyfikatorów, usuń elementy z tych pozycji z sekwencji i zwróć listę usuniętych elementów w kolejności sekwencji

Jeśli chcesz, możesz myśleć o tym jak o stosie lub kolejce z operacją podziału, która dzieli ją na dwa stosy: operacja wyodrębniania może być wykorzystana do wykonania operacji pop lub dequeue, a wyodrębniona sekwencja elementów może być również umieszczona z powrotem do innego stosu lub kolejki.

Co już wiem: można zachować sekwencję jako podwójnie połączoną listę, gdzie każdy identyfikator jest tylko wskaźnikiem do węzła listy połączonych, a każdy węzeł przechowuje również numer pozycji, który umożliwia szybkie porównanie między pozycjami dwóch niepowiązanych elementów w sekwencji. Aktualizacja numerów pozycji nie jest trudna w miarę postępu struktury danych, dzięki czemu wszystkie są dodatnimi liczbami całkowitymi o maksymalnej wartości , gdzie jest bieżącą liczbą pozycji na liście. Przy tej strukturze danych jedyną trudną częścią operacji wyodrębniania jest sortowanie wyodrębnionych elementów według ich numerów pozycji. Wyodrębnienie elementów zajmuje $O(n)$ $n$ $k$ oczekiwany losowy czas przy użyciu algorytmu sortowania liczb całkowitych Hana i Thorupa z FOCS 2002, na przykład, a operacja wypychania zajmuje stały czas. $O(k\sqrt{\log\log k})$

Czego nie wiem: czy można poradzić sobie z ekstraktem w czasie i wcisnąć w czasie stałym? Czy jest literatura na ten temat? Czy to jest tak trudne jak sortowanie liczb całkowitych? $O(k)$

Motywacja: jest to podstawowy krok potrzebny do zamówienia elementów w algorytmie szeregowania Coffmana-Grahama, który ma również zastosowania w rysowaniu wykresów. Trudną częścią Coffmana-Grahama jest uporządkowanie leksykograficzne topologiczne. Można tego dokonać utrzymując dla każdego innego stopnia sekwencję wierzchołków z tym stopniem w podgrodzie indukowanym przez pozostałe wierzchołki. Następnie kilkakrotnie usuń pierwszy wierzchołek z sekwencji wierzchołków zerowo niezależnych i dodaj go do porządku topologicznego; wyodrębnij sąsiadów ze stopni, do których wcześniej należeli, i wypchnij ich na sekwencję o kolejny mniejszy stopień. Więc $v$ $v$ $O(k)$ czas na operacje wyodrębniania w tej strukturze danych prowadziłby do liniowej implementacji algorytmu Coffmana-Grahama.

Ponieważ pierwotnie pytałem o to, znalazłem artykuł Sethiego z 1976 r. , Który pozwala na implementację algorytmu Coffmana-Grahama w czasie liniowym, i umieściłem go w moim artykule w Wikipedii na temat algorytmu Coffmana-Grahama , więc oryginalna motywacja jest mniej znacząca. Nadal jestem ciekawa, jaka jest odpowiedź.

ds.data-structures

— David Eppstein
źródło

Jeśli wstawianie nastąpi tylko na końcu sekwencji, możesz zarządzać zarówno podwójnie połączoną listą, jak i tabelą skrótów pozycji pozycji. Wstawienie: amortyzowane O (1) (po prostu trzymaj wskaźnik do ostatniego elementu). Wyodrębnianie k elementów: zamortyzowane O (k) (dla każdego elementu S, pobierz wskaźnik i usuń go z tabeli skrótów, pobierz i usuń element z listy i dodaj go do wyniku ekstrakcji).

— Marzio De Biasi,

To nie jest ekstrakcja elementów z listy, która zajmuje dużo czasu, to przestawianie ich z nieposortowanej kolejności argumentu w celu wyodrębnienia do właściwej kolejności sekwencji.

— David Eppstein,

Myślę, że jest to co najmniej tak trudne, jak sortowanie zbioru liczb całkowitych z „losową wskazówką” wielomianu wielkości w . Przez losową poradę rozumiem, że dla dowolnego istnieje stały rozkład (w zależności tylko od ) na ciągi wielkości poli ( ), a nasz algorytm (modelowany przez maszynę RAM) ma losowy dostęp do pojedynczej próbki z . to (losowa) struktura danych po wypchnięciu $S \subseteq [n]$ $n$ $n$ ${\cal D}_n$ $n$ $n$ ${\cal D}_n$ ${\cal D}_n$ $[n]$ w kolejności, wraz z tabelą skrótów, która odwzorowuje liczby całkowite na identyfikatory w oczekiwanym czasie . $O(1)$

Biorąc pod uwagę tę konfigurację, na przykład problemu z sortowaniem liczb całkowitych, możemy wydać ekstrakt ( ) (w rzeczywistości potrzebujemy identyfikatorów ale to mapowanie może być wykonane w czasie na element przy użyciu skrótu tabela, która jest częścią porady), a dane wejściowe zostaną posortowane według czasu potrzebnego do wykonania wypakowania. $S \subseteq [n]$ $S$ $S$ $O(1)$

Komunikat jest taki, że o ile niektóre „wolne” informacje dodatkowe, które zależą tylko od górnej granicy liczb całkowitych, mogą ułatwić sortowanie liczb całkowitych, wyodrębnienie jest tak trudne jak sortowanie liczb całkowitych.

Czy to sugeruje związek między dwoma problemami bez dziwnego modelu? Czy to pojęcie losowej porady jest czymś znanym? Jest to trochę jak protokół MA, ale wiadomość Merlina nie może zależeć od danych wejściowych i zależy nam na czasie działania Artura.

— Sasho Nikolov
źródło

[n]

$[n]$

D_{n}

$\mathcal{D}_n$

Ω (n)

$\Omega(n)$

D_{n}

$\mathcal{D}_n$

Ω (n)

$\Omega(n)$

k

$k$

[n]

$[n]$

O (n + k)

$O(n+k)$

O (k)

$O(k)$

— Dave

Ω (n)

$\Omega(n)$

D_{n}

${\cal D}_n$

k

$k$

O (k)

$O(k)$

D_{n}

${\cal D}_n$ ?

— Sasho Nikolov

Oto powód, dla którego nie uważam tej odpowiedzi za całkowicie przekonującą. Jeśli masz tylko jeden zestaw liczb całkowitych, które chcesz posortować, wszystko jest czasem liniowym (po prostu zliczaj sortowanie w O (n + k)). Ale jeśli próbujesz użyć tej struktury danych do symulacji sekwencji wielu małych rodzajów (tak, że zliczanie sortowania nie jest wystarczająco dobre), tylko pierwszy z tych małych rodzajów jest całkowicie nieograniczony: po tym usunąłeś niektóre elementów [n], więc każda sortowana sekwencja musi być rozłączna od poprzednich. Wydaje się więc, że trudno jest ograniczyć pracę związaną z sortowaniem.

— David Eppstein,

@David Eppstein: for

ℓ

$\ell$ rodzaje, które możesz wziąć

ℓ

$\ell$ kopie początkowej struktury danych. Oczywiście, dziwny model „losowych porad” nie jest całkowicie przekonujący, chcielibyśmy ograniczenia w zwykłym sensie. Ale przesłanie, które przekazałem, brzmi:

O (k)

$O(k)$ czas zapytania oznacza, że algorytm sortowania liczb całkowitych może korzystać z porad niezależnych od danych wejściowych w sposób zapewniający efektywny dostęp do pamięci. Jest to dla mnie sprzeczne z intuicją, ale moja intuicja jest tutaj słaba. BTW, pomyślałem

O (n + k)

$O(n+k)$ nie jest to rodzaj czasu liniowego, z którego jesteś zadowolony?

— Sasho Nikolov

Jeśli kopiujesz strukturę danych raz dla każdego użycia, używasz

Ω (n)

$\Omega(n)$ czas na wykonanie kopii dla każdego rodzaju, więc nie spowoduje to szybszego sortowania. Jeśli po prostu zapytasz o pozycje w ciągu reprezentującym

D_{n}

$\mathcal{D}_n$ jak sugerujesz, nie jest jasne, czy to wystarczy, aby się przydzielić

O (k)

$O(k)$ czas. Struktura danych może ulec zmianie podczas operacji wyodrębniania, a uruchomienie w wersji statycznej może zwiększyć czas działania.

— Dave