Teilbarer Stapel

Was ist über Datenstrukturen bekannt, die eine Abfolge von Elementen verwalten können, die den folgenden beiden Operationen unterliegen?

Drücken Sie (x): Fügen Sie x am Ende der Sequenz hinzu und geben Sie einen Bezeichner für die Position in der Sequenz zurück
Extrakt (S): Bei einem ungeordneten Satz von Bezeichnern entfernen Sie die Elemente an diesen Positionen aus der Sequenz und geben eine Liste der entfernten Elemente in der Sequenzreihenfolge zurück

Wenn Sie möchten, können Sie sich dies als einen Stapel oder eine Warteschlange mit einer Aufteilungsoperation vorstellen, die ihn in zwei Stapel aufteilt: Die Extraktionsoperation kann verwendet werden, um eine Pop- oder Dequeue-Operation zu implementieren, und die extrahierte Sequenz von Elementen könnte auch abgelegt werden zurück in einen anderen Stapel oder eine andere Warteschlange.

Was ich bereits weiß: Man kann die Sequenz als doppelt verknüpfte Liste verwalten, wobei jeder Bezeichner nur ein Zeiger auf einen Knoten mit verknüpfter Liste ist und jeder Knoten auch eine Positionsnummer speichert, die einen schnellen Vergleich zwischen den Positionen zweier nicht miteinander verbundener Elemente ermöglicht in der Reihenfolge. Es ist nicht schwierig, die Positionsnummern im Verlauf der Datenstruktur so zu aktualisieren, dass sie alle positive ganze Zahlen mit dem Maximalwert , wobei die aktuelle Anzahl der Elemente in der Liste ist. Bei dieser Datenstruktur besteht der einzige schwierige Teil einer Extraktionsoperation darin, die extrahierten Elemente nach ihren Positionsnummern zu sortieren. Eine Extraktion von Elementen dauert $O(n)$ $n$ $k$ $O(k\sqrt{\log\log k})$ erwartete zufällige Zeit unter Verwendung des Ganzzahl-Sortieralgorithmus von Han und Thorup von FOCS 2002, und eine Push-Operation benötigt konstante Zeit.

Was ich nicht weiß: Ist es möglich, Extrakt in -Zeit zu verarbeiten und konstante Zeit einzugeben? Gibt es Literatur zu diesem Problem? Ist es so schwer wie eine Ganzzahlensortierung? $O(k)$

Motivation: Dies ist der grundlegende Schritt, der erforderlich ist, um die Elemente im Coffman-Graham-Planungsalgorithmus zu ordnen, der auch Anwendungen für das Zeichnen von Diagrammen bietet. Der schwierige Teil von Coffman-Graham ist eine lexikografische topologische Anordnung. Dies kann durchgeführt werden, indem für jeden unterschiedlichen Grad eine Folge der Eckpunkte mit demjenigen Grad in dem Teilgraphen beibehalten wird, der durch die verbleibenden Eckpunkte induziert wird. Entfernen Sie dann wiederholt den ersten Scheitelpunkt aus der Folge der Scheitelpunkte mit dem Grad Null und fügen Sie ihn der topologischen Reihenfolge hinzu. extrahieren sie die nachbarn von aus den graden, zu denen sie vorher gehörten und schieben sie sie für den nächst kleineren grad auf die folge. Also ein $v$ $v$ $O(k)$ Die Zeit für die Extraktionsoperationen in dieser Datenstruktur würde zu einer linearen Zeitimplementierung des Coffman-Graham-Algorithmus führen.

Seitdem ich dies ursprünglich gefragt habe, habe ich einen Artikel von Sethi aus dem Jahr 1976 gefunden , der es ermöglicht, den Coffman-Graham-Algorithmus in linearer Zeit zu implementieren, und ihn in meinen Wikipedia-Artikel über den Coffman-Graham-Algorithmus aufgenommen , sodass die ursprüngliche Motivation weniger aussagekräftig ist. Ich bin immer noch gespannt, wie die Antwort lautet.

ds.data-structures David Eppstein
quelle

Wenn Einfügungen nur am Ende der Sequenz erfolgen, können Sie sowohl eine doppelt verknüpfte Liste als auch eine Hash-Tabelle der Elementpositionen verwalten. Einfügung: Amortisiertes O (1) (nur Zeiger auf den letzten Posten lassen). Extraktion von k Elementen: Amortisiertes O (k) (für jedes Element von S Zeiger abrufen und aus der Hash-Tabelle entfernen, Element aus der Liste abrufen und entfernen und zum Extraktionsergebnis hinzufügen).

Marzio De Biasi

Es ist nicht das Extrahieren der Elemente aus der Liste, das Zeit in Anspruch nimmt, sondern das Umordnen der Elemente aus der unsortierten Reihenfolge des Arguments, um sie in die richtige Reihenfolge zu extrahieren.

David Eppstein

Antworten:

Ich denke, dies ist mindestens so schwierig wie das Sortieren einer Menge von ganzen Zahlen mit "zufälligen Ratschlägen" des Größenpolynoms in . Durch zufällige Beratung meine ich , dass für jede gibt es eine feste Verteilung (je nur auf ) über Ketten von Größe Poly ( ) und der Algorithmus (durch eine RAM - Maschine modelliert) wird wahlfreier Zugriff auf eine bestimmte Einzelprobe von . ist die (randomisierte) Datenstruktur nach dem Drücken von in der angegebenen Reihenfolge, zusammen mit einer Hash-Tabelle, die Ganzzahlen zu Bezeichnern in der erwarteten -Zeit abbildet . $S \subseteq [n]$ $n$ $n$ ${\cal D}_n$ $n$ $n$ ${\cal D}_n$ ${\cal D}_n$ $[n]$ $O(1)$

Unter dieser Voraussetzung können wir für eine Instanz des Integer-Sortierproblems extract ( ) ausgeben (tatsächlich benötigen wir die Bezeichner von aber diese Zuordnung kann in -Zeit pro Element mithilfe von erfolgen Hash-Tabelle, die Teil des Hinweises ist) und die Eingabe werden in der Zeit sortiert, die für die Ausführung des Extrakts benötigt wird. $S \subseteq [n]$ $S$ $S$ $O(1)$

Die Botschaft lautet also, dass Extrahieren genauso schwierig ist wie Sortieren von Ganzzahlen , es sei denn, einige "freie" Nebeninformationen, die nur von der Obergrenze der Ganzzahlen abhängen, können das Sortieren von Ganzzahlen vereinfachen.

Bedeutet dies eine Beziehung zwischen den beiden Problemen ohne das seltsame Modell? Ist dieser Begriff des zufälligen Ratschlags bekannt? Dies ist wie ein MA-Protokoll, aber Merlins Nachricht darf nicht von der Eingabe abhängen und wir kümmern uns um Arthurs Laufzeit.

Sasho Nikolov
quelle

Das Pushen von auf erfordert -Zeit. Der freie Zugriff auf also der Berechnung von bereits zu Beginn des Algorithmus. Da Sie Ganzzahlen, die aus in -Zeit gezogen wurden, sortieren können, besteht kein Grund zu der Annahme, dass das Sortieren mit freiem Zugriff auf diese Datenstruktur mehr als -Zeit dauern würde .

[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

Sie haben die Berechnung von kostenlos, der Zugriff ist jedoch nicht kostenlos: Jede Abfrage wird als Zeitschritt berechnet. Können Sie so gestalten, dass Sie Ganzzahlen mit -Abfragen nach einer Zeichenfolge aus sortieren können ?

Ω (n)

$\Omega(n)$

D_{n}

${\cal D}_n$

k

$k$

O (k)

$O(k)$

D_{n}

${\cal D}_n$

Sasho Nikolov

Hier ist der Grund, warum ich diese Antwort nicht ganz überzeugend finde. Wenn Sie nur einen Satz S von Ganzzahlen haben, die Sie sortieren möchten, ist alles lineare Zeit (zählen Sie einfach die Sortierung in O (n + k)). Wenn Sie jedoch versuchen, diese Datenstruktur zu verwenden, um eine Folge vieler kleiner Sortierungen zu simulieren (sodass das Zählen der Sortierungen nicht ausreicht), ist nur die erste dieser kleinen Sortierungen völlig uneingeschränkt: Danach haben Sie einige entfernt von den Elementen von [n], so dass jede Sequenz, die Sie sortieren, von den vorherigen getrennt werden muss. Eine Reduzierung der Sortierarbeit erscheint daher schwierig.

David Eppstein

@ David Eppstein: Für können Sie Kopien der ursprünglichen Datenstruktur erstellen. Natürlich ist das seltsame "Random Advice" -Modell nicht ganz überzeugend, wir möchten eine Reduzierung im üblichen Sinne. Aber die Botschaft, die ich übermittelte, ist, dass eine -Abfragezeit impliziert, dass ein Ganzzahl-Sortieralgorithmus auf speicherzugriffseffiziente Weise von Ratschlägen unabhängig von seiner Eingabe profitieren kann. Das ist für mich nicht intuitiv, aber meine Intuition ist hier schwach. Übrigens, ich dachte, ist nicht die Art von linearer Zeit, mit der Sie zufrieden sind?

ℓ

$\ell$

ℓ

$\ell$

O (k)

$O(k)$

O (n + k)

$O(n+k)$

Sasho Nikolov

Wenn Sie die Datenstruktur einmal für jede Verwendung kopieren, verwenden Sie die -Zeit, um für jede Sortierung eine Kopie zu erstellen. Dies führt also nicht zu einer schnelleren Sortierung. Wenn Sie nur Positionen in einer Zeichenfolge abfragen, die wie Sie vermuten, ist es unklar, dass dies ausreicht, um in -Zeit zu sortieren . Die Datenstruktur kann sich während eines Extraktionsvorgangs ändern, und das Ausführen einer statischen Version kann die Laufzeit verlängern.

Ω (n)

$\Omega(n)$

D_{n}

$\mathcal{D}_n$

O (k)

$O(k)$

Dave