Ich bin auf diese Frage in einem Algorithmusbuch gestoßen ( Algorithms, 4th Edition von Robert Sedgewick und Kevin Wayne).
Warteschlange mit drei Stapeln. Implementieren Sie eine Warteschlange mit drei Stapeln, sodass für jede Warteschlangenoperation eine konstante Anzahl von Stapeloperationen (im schlimmsten Fall) erforderlich ist. Warnung: hoher Schwierigkeitsgrad.
Ich weiß, wie man eine Warteschlange mit 2 Stapeln erstellt, aber ich kann die Lösung mit 3 Stapeln nicht finden. Irgendeine Idee ?
(oh und, das sind keine Hausaufgaben :))
algorithm
data-structures
DuoSRX
quelle
quelle
Antworten:
ZUSAMMENFASSUNG
EINZELHEITEN
Hinter diesem Link stehen zwei Implementierungen: http://www.eecs.usma.edu/webs/people/okasaki/jfp95/index.html
Eines davon ist O (1) mit drei Stapeln, ABER es verwendet eine verzögerte Ausführung, die in der Praxis zusätzliche Zwischendatenstrukturen (Verschlüsse) erzeugt.
Ein anderer von ihnen ist O (1), verwendet jedoch SIX-Stapel. Es funktioniert jedoch ohne verzögerte Ausführung.
UPDATE: Okasakis Artikel ist hier: http://www.eecs.usma.edu/webs/people/okasaki/jfp95.ps und es scheint, dass er tatsächlich nur 2 Stapel für die O (1) -Version verwendet, die eine verzögerte Bewertung hat. Das Problem ist, dass es wirklich auf einer faulen Bewertung basiert. Die Frage ist, ob es ohne verzögerte Auswertung in einen 3-Stapel-Algorithmus übersetzt werden kann.
UPDATE: Ein weiterer verwandter Algorithmus ist in dem Artikel "Stacks versus Deques" von Holger Petersen beschrieben, der auf der 7. Jahreskonferenz für Computer und Kombinatorik veröffentlicht wurde. Sie finden den Artikel in Google Books. Überprüfen Sie die Seiten 225-226. Der Algorithmus ist jedoch keine Echtzeitsimulation, sondern eine lineare Zeitsimulation einer doppelendigen Warteschlange auf drei Stapeln.
gusbro: "Wie @Leonel vor einigen Tagen sagte, dachte ich, es wäre fair, sich bei Prof. Sedgewick zu erkundigen, ob er eine Lösung kennt oder ob ein Fehler vorliegt. Also habe ich ihm geschrieben. Ich habe gerade eine Antwort erhalten (wenn auch nicht von selbst, aber von einem Kollegen in Princeton), also teile ich es gerne mit Ihnen allen. Er sagte im Grunde, dass er keine Algorithmen mit drei Stapeln UND die anderen auferlegten Einschränkungen (wie die Nichtverwendung einer faulen Auswertung) kenne. Er kannte einen Algorithmus mit 6 Stapel, wie wir bereits wissen, wenn wir uns die Antworten hier ansehen. Ich denke, die Frage ist noch offen, um einen Algorithmus zu finden (oder zu beweisen, dass einer nicht gefunden werden kann). "
quelle
rotate
sieht es so aus, als würde diefront
Liste beidenoldfront
und zugewiesenf
, und diese werden dann separat geändert.Ok, das ist wirklich schwer, und die einzige Lösung, die ich finden konnte, erinnert mich an Kirks Lösung für den Kobayashi Maru-Test (irgendwie betrogen): Die Idee ist, dass wir Stapel von Stapeln verwenden (und dies verwenden, um eine Liste zu modellieren ). Ich rufe die Operationen en / dequeue und push and pop auf, dann bekommen wir:
(StackX = StackY ist kein Kopieren des Inhalts, sondern nur eine Kopie der Referenz. Es dient nur zur einfachen Beschreibung. Sie können auch ein Array von 3 Stapeln verwenden und über den Index darauf zugreifen. Dort würden Sie nur den Wert der Indexvariablen ändern ). Alles ist in O (1) in Bezug auf die Stapeloperation.
Und ja, ich weiß, dass es fraglich ist, weil wir mehr als 3 Stapel impliziert haben, aber vielleicht gibt es anderen von Ihnen gute Ideen.
EDIT: Erklärungsbeispiel:
Ich habe hier mit ein wenig ASCII-Kunst versucht, Stack1 zu zeigen.
Jedes Element wird in einen einzelnen Elementstapel eingeschlossen (wir haben also nur einen typsicheren Stapelstapel).
Sie sehen, um zu entfernen, platzieren wir zuerst das erste Element (den Stapel, der hier Element 1 und 2 enthält). Dann Pop das nächste Element und dort die 1 auspacken. Danach sagen wir, dass der erste Poped Stack jetzt unser neuer Stack1 ist. Um es etwas funktionaler zu sagen: Dies sind Listen, die durch Stapel von 2 Elementen implementiert werden, wobei das oberste Element cdr und das erste / unterste obere Element car ist . Die anderen 2 helfen Stapeln.
Besonders schwierig ist das Einfügen, da Sie irgendwie tief in die verschachtelten Stapel eintauchen müssen, um ein weiteres Element hinzuzufügen. Deshalb ist Stack2 da. Stack2 ist immer der innerste Stack. Beim Hinzufügen wird dann nur ein Element hineingeschoben und dann auf einen neuen Stack2 geschoben (und deshalb dürfen wir Stack2 in unserer Warteschlangenoperation nicht berühren).
quelle
Ich werde einen Beweis versuchen, um zu zeigen, dass dies nicht möglich ist.
Angenommen, es gibt eine Warteschlange Q, die durch 3 Stapel A, B und C simuliert wird.
Behauptungen
ASRT0: = Nehmen wir außerdem an, dass Q Operationen {queue, dequeue} in O (1) simulieren kann. Dies bedeutet, dass für jede zu simulierende Warteschlangen- / Warteschlangenoperation eine bestimmte Folge von Stack-Push / Pops vorhanden ist.
Nehmen Sie ohne Verlust der Allgemeinheit an, dass die Warteschlangenoperationen deterministisch sind.
Lassen Sie die in Q in die Warteschlange gestellten Elemente basierend auf ihrer Reihenfolge der Warteschlangen mit 1, 2, ... nummerieren, wobei das erste in Q in die Warteschlange gestellte Element als 1, das zweite als 2 usw. definiert wird.
Definieren
Q(0) :=
Der Zustand von Q, wenn 0 Elemente in Q vorhanden sind (und somit 0 Elemente in A, B und C)Q(1) :=
Der Zustand von Q (und A, B und C) nach 1 Warteschlangenoperation einQ(0)
Q(n) :=
Der Zustand von Q (und A, B und C) nach n Warteschlangenoperationen anQ(0)
Definieren
|Q(n)| :=
die Anzahl der Elemente inQ(n)
(daher|Q(n)| = n
)A(n) :=
der Zustand des Stapels A, wenn der Zustand von Q istQ(n)
|A(n)| :=
die Anzahl der Elemente inA(n)
Und ähnliche Definitionen für die Stapel B und C.
Trivial,
|Q(n)|
ist offensichtlich unbegrenzt auf n.Daher mindestens eines von
|A(n)|
,|B(n)|
oder|C(n)|
unbeschränkt auf n.WLOG1
Angenommen, Stapel A ist unbegrenzt und Stapel B und C sind begrenzt.Definiere *
B_u :=
eine Obergrenze von B *C_u :=
eine Obergrenze von C *K := B_u + C_u + 1
WLOG2
Wählen Sie für ein n so aus, dass|A(n)| > K
Sie K Elemente aus auswählenQ(n)
. Angenommen, eines dieser Elemente befindet sichA(n + x)
für allex >= 0
, dh das Element befindet sich immer im Stapel A, unabhängig davon, wie viele Warteschlangenoperationen ausgeführt werden.X :=
dieses ElementDann können wir definieren
Abv(n) :=
Die Anzahl der Elemente im StapelA(n)
liegt über X.Blo(n) :=
Die Anzahl der Elemente im StapelA(n)
liegt unter X.| A (n) | = Abv (n) + Blo (n)
ASRT1 :=
Die Anzahl der Pops, die erforderlich sind, um X aus der Warteschlange zu entfernen,Q(n)
beträgt mindestensAbv(n)
Von (
ASRT0
) und (ASRT1
)ASRT2 := Abv(n)
muss begrenzt werden.Wenn
Abv(n)
es unbegrenzt ist, wenn mindestens 20 Warteschlangen erforderlich sind, um X aus der Warteschlange zu entfernenQ(n)
, sind mindestensAbv(n)/20
Pops erforderlich . Welches ist unbegrenzt. 20 kann eine beliebige Konstante sein.Deshalb,
muss unbegrenzt sein.
WLOG3
können wir die K-Elemente unten auswählenA(n)
, und eines davon istA(n + x)
für alle dax >= 0
X(n) :=
dieses Element für jedes gegebene nImmer wenn ein Element in die Warteschlange gestellt wird
Q(n)
...WLOG4
Angenommen, B und C sind bereits bis zu ihren oberen Grenzen gefüllt. Angenommen, die Obergrenze für die obigen ElementeX(n)
wurde erreicht. Dann tritt ein neues Element in A ein.WLOG5
Angenommen, das neue Element muss als Ergebnis unten eingegeben werdenX(n)
.ASRT5 :=
Die Anzahl der Pops, die erforderlich sind, um ein Element darunter zu platzierenX(n) >= Abv(X(n))
Von
(ASRT4)
,Abv(n)
ist unbegrenzt auf n.Daher ist die Anzahl der Pops, die erforderlich sind, um ein Element darunter zu platzieren,
X(n)
unbegrenzt.Dies widerspricht
ASRT1
daher, dass es nicht möglich ist, eineO(1)
Warteschlange mit 3 Stapeln zu simulieren .Dh
Mindestens 1 Stapel muss unbegrenzt sein.
Für ein Element, das in diesem Stapel verbleibt, muss die Anzahl der darüber liegenden Elemente begrenzt werden. Andernfalls ist die Dequeue-Operation zum Entfernen dieses Elements unbegrenzt.
Wenn jedoch die Anzahl der darüber liegenden Elemente begrenzt ist, erreicht sie eine Grenze. Irgendwann muss ein neues Element darunter eintreten.
Da wir das alte Element immer aus einem der niedrigsten Elemente dieses Stapels auswählen können, kann es eine unbegrenzte Anzahl von Elementen darüber geben (basierend auf der unbegrenzten Größe des unbegrenzten Stapels).
Um ein neues Element darunter einzugeben, ist eine unbegrenzte Anzahl von Elementen erforderlich, um das neue Element darunter zu platzieren, da sich eine unbegrenzte Anzahl von Elementen darüber befindet.
Und damit der Widerspruch.
Es gibt 5 WLOG-Anweisungen (ohne Verlust der Allgemeinheit). In gewissem Sinne können sie intuitiv als wahr verstanden werden (aber wenn sie 5 sind, kann es einige Zeit dauern). Der formale Beweis, dass keine Allgemeinheit verloren geht, kann abgeleitet werden, ist aber äußerst langwierig. Sie werden weggelassen.
Ich gebe zu, dass eine solche Auslassung die fraglichen WLOG-Aussagen belassen könnte. Bei der Paranoia eines Programmierers für Fehler überprüfen Sie bitte die WLOG-Anweisungen, wenn Sie möchten.
Der dritte Stapel ist ebenfalls irrelevant. Was zählt, ist, dass es eine Reihe von begrenzten Stapeln und eine Reihe von unbegrenzten Stapeln gibt. Das für ein Beispiel erforderliche Minimum beträgt 2 Stapel. Die Anzahl der Stapel muss natürlich endlich sein.
Wenn ich recht habe, dass es keinen Beweis gibt, sollte es einen einfacheren induktiven Beweis geben. Wahrscheinlich basierend auf dem, was nach jeder Warteschlange passiert (verfolgen Sie, wie sich dies auf den schlimmsten Fall der Warteschlange auswirkt, wenn alle Elemente in der Warteschlange vorhanden sind).
quelle
Hinweis: Dies soll ein Kommentar zur funktionalen Implementierung von Echtzeitwarteschlangen (Worst-Case mit konstanter Zeit) mit einfach verknüpften Listen sein. Ich kann aufgrund des guten Rufs keine Kommentare hinzufügen, aber es wäre schön, wenn jemand dies in einen Kommentar ändern könnte, der an die Antwort von antti.huima angehängt ist. Andererseits ist es etwas lang für einen Kommentar.
@ antti.huima: Verknüpfte Listen sind nicht dasselbe wie ein Stapel.
s1 = (1 2 3 4) --- eine verknüpfte Liste mit 4 Knoten, die jeweils auf den rechten zeigen und die Werte 1, 2, 3 und 4 enthalten
s2 = geknallt (s1) --- s2 ist jetzt (2 3 4)
Zu diesem Zeitpunkt entspricht s2 popped (s1), das sich wie ein Stapel verhält. S1 steht jedoch weiterhin als Referenz zur Verfügung!
Wir können immer noch in s1 schauen, um 1 zu erhalten, während in einer ordnungsgemäßen Stack-Implementierung Element 1 von s1 weg ist!
Was bedeutet das?
Die jetzt erstellten zusätzlichen verknüpften Listen dienen jeweils als Referenz / Zeiger! Eine endliche Anzahl von Stapeln kann das nicht.
Nach dem, was ich in den Artikeln / im Code sehe, nutzen alle Algorithmen diese Eigenschaft von verknüpften Listen, um Referenzen beizubehalten.
Bearbeiten: Ich beziehe mich nur auf die Algorithmen für verknüpfte Listen 2 und 3, die diese Eigenschaft von verknüpften Listen verwenden, da ich sie zuerst gelesen habe (sie sahen einfacher aus). Dies soll nicht zeigen, dass sie anwendbar sind oder nicht, sondern nur erklären, dass verknüpfte Listen nicht unbedingt identisch sind. Ich werde die mit 6 lesen, wenn ich frei bin. @ Welbog: Danke für die Korrektur.
Faulheit kann auf ähnliche Weise auch Zeigerfunktionen simulieren.
Die Verwendung einer verknüpften Liste löst ein anderes Problem. Diese Strategie kann verwendet werden, um Echtzeitwarteschlangen in Lisp zu implementieren (oder zumindest Lisps, die darauf bestehen, alles aus verknüpften Listen zu erstellen): Siehe "Echtzeitwarteschlangenoperationen in Pure Lisp" (verknüpft über die Links von antti.huima). Es ist auch eine gute Möglichkeit, unveränderliche Listen mit O (1) -Operationszeit und gemeinsam genutzten (unveränderlichen) Strukturen zu entwerfen.
quelle
java.util.Stack
Objekten in Java neu implementiert habe . Der einzige Ort, an dem diese Funktion verwendet wird, ist eine Optimierung, die es ermöglicht, unveränderliche Stapel in konstanter Zeit zu "duplizieren", was Basis-Java-Stapel nicht können (aber in Java implementiert werden können), da es sich um veränderbare Strukturen handelt.Sie können dies in amortisierter konstanter Zeit mit zwei Stapeln tun:
Hinzufügen ist
O(1)
und Entfernen ist,O(1)
wenn die Seite, von der Sie nehmen möchten, nicht leer ist undO(n)
ansonsten (teilen Sie den anderen Stapel in zwei Teile).Der Trick besteht darin, zu sehen, dass die
O(n)
Operation nur jedesO(n)
Mal ausgeführt wird (wenn Sie teilen, z. B. in zwei Hälften). Daher beträgt die durchschnittliche Zeit für eine OperationO(1)+O(n)/O(n) = O(1)
.Dies mag zwar problematisch sein, aber wenn Sie eine zwingende Sprache mit einem Array-basierten Stapel (am schnellsten) verwenden, haben Sie ohnehin nur konstante Zeit amortisiert.
quelle