Werden Constant Time und Amortized Constant Time effektiv als gleichwertig angesehen?

16

Ich muss eine RandomQueue schreiben, die das Anhängen und zufällige Entfernen in konstanter Zeit (O (1)) ermöglicht.

Mein erster Gedanke war, es mit einer Art Array zu unterstützen (ich habe eine ArrayList gewählt), da Arrays über einen Index ständigen Zugriff haben.

Beim Durchsehen der Dokumentation wurde mir jedoch klar, dass die Additionen von ArrayLists als Amortized Constant Time betrachtet werden, da für eine Addition möglicherweise eine Neuzuweisung des zugrunde liegenden Arrays erforderlich ist, nämlich O (n).

Sind Amortized Constant Time und Constant Time effektiv gleich, oder muss ich eine Struktur betrachten, die nicht bei jeder Addition eine vollständige Neuzuweisung erfordert?

Ich frage dies, weil ich neben Array-basierten Strukturen (die meines Wissens immer Amortized Constant Time-Zusätze enthalten) nichts finden kann, was die Anforderungen erfüllt:

  • Alles, was auf einem Baum basiert, hat bestenfalls Zugriff auf O (log n)
  • Eine verknüpfte Liste könnte möglicherweise O (1) -Additionen enthalten (wenn ein Verweis auf den Schwanz beibehalten wird), eine zufällige Entfernung sollte jedoch bestenfalls O (n) sein.

Hier ist die vollständige Frage. Für den Fall, dass ich einige wichtige Details übersehen habe:

Entwerfen und implementieren Sie eine RandomQueue. Dies ist eine Implementierung der Warteschlangenschnittstelle, bei der die Operation remove () ein Element entfernt, das unter allen Elementen, die sich derzeit in der Warteschlange befinden, gleichmäßig zufällig ausgewählt wird. (Stellen Sie sich eine RandomQueue als eine Tasche vor, in der wir Elemente hinzufügen oder zufällige Elemente erreichen und blind entfernen können.) Die Operationen add (x) und remove () in einer RandomQueue sollten pro Operation in konstanter Zeit ausgeführt werden.

algorithms complexity Karzigenat
quelle
Gibt die Zuordnung an, wie zufällige Entfernungen durchgeführt werden? Erhalten Sie einen Index zum Entfernen oder einen Verweis auf ein Warteschlangenelement?
Es gibt keine Einzelheiten. Die Anforderungen sind lediglich eine Struktur, die die Warteschlangenschnittstelle implementiert und O (1) -Zusätze und -Entfernungen enthält.
Carcigenicate
Nebenbei bemerkt - ein Array, dessen Größe geändert werden kann und bei dem O (n) wächst, muss nicht unbedingt den Zusatz O (1) enthalten: Dies hängt davon ab, wie wir das Array vergrößern. Das Wachstum um einen konstanten Betrag a ist immer noch O (n) für die Addition (wir haben die 1/aChance auf eine O (n) -Operation), aber das Wachstum um einen konstanten Faktor a > 1ist O (1) für die Addition amortisiert: Wir haben die (1/a)^nChance auf ein O (n) Operation, aber diese Wahrscheinlichkeit nähert sich Null für große n.
Am
ArrayLists verwenden letztere richtig?
Carcigenicate
1
Der Verfasser der Frage (ich) dachte an die amortisierte konstante Zeitlösung. Ich werde das in der nächsten Ausgabe klarstellen. (Obwohl hier die Konstantzeit im ungünstigsten Fall unter Verwendung der Technik der Entamortisation erreicht werden kann .)
Pat Morin,

Antworten:

10

Amortisierte konstante Zeit kann fast immer als mit konstanter Zeit gleichgesetzt werden. Ohne Kenntnis der Besonderheiten Ihrer Anwendung und der Art der Nutzung, die Sie für diese Warteschlange planen, besteht die größte Wahrscheinlichkeit, dass Sie abgedeckt werden.

Eine Array-Liste hat das Konzept der Kapazität , die im Grunde genommen der größten Größe / Länge / Anzahl von Elementen entspricht, die bisher für sie erforderlich waren. Was also passieren wird, ist, dass sich die Array-Liste zu Beginn immer wieder neu zuordnet, um ihre Kapazität zu erhöhen, während Sie ihr Elemente hinzufügen. Irgendwann entspricht die durchschnittliche Anzahl der pro Zeiteinheit hinzugefügten Elemente jedoch zwangsläufig der durchschnittlichen Anzahl der Elemente werden pro Zeiteinheit entfernt (andernfalls würde Ihnen ohnehin der Speicher ausgehen). An diesem Punkt hört das Array auf, sich selbst neu zuzuordnen, und alle Anhänge werden zu einer konstanten Zeit von O (1) erfüllt.

Beachten Sie jedoch, dass das zufällige Entfernen aus einer Array-Liste standardmäßig nicht O (1), sondern O (N) ist, da Array-Listen alle Elemente nach dem entfernten Element um eine Position nach unten verschieben, um den Platz des entfernten Elements einzunehmen Artikel. Um O (1) zu erreichen, müssen Sie das Standardverhalten überschreiben, um das entfernte Element durch eine Kopie des letzten Elements der Array-Liste zu ersetzen, und dann das letzte Element entfernen, damit keine Elemente verschoben werden. Aber wenn Sie das tun, haben Sie nicht mehr genau eine Warteschlange.

Mike Nakis
quelle
1
Verdammt, guter Punkt für Umzüge; Das habe ich nicht bedacht. Und da wir zufällig Elemente entfernen, heißt das technisch nicht, dass es sowieso keine Warteschlange mehr in diesem Sinne ist?
Carcigenicate
Ja, das bedeutet, dass Sie es nicht wirklich als Warteschlange behandeln. Aber ich weiß nicht, wie Sie die zu entfernenden Gegenstände finden wollen. Wenn Ihr Mechanismus, sie zu finden, erwartet, dass sie in der Reihenfolge, in der sie hinzugefügt wurden, in der Warteschlange vorhanden sind, haben Sie Pech. Wenn es Ihnen egal ist, ob die Reihenfolge der Artikel verstümmelt ist, dann geht es Ihnen gut.
Mike Nakis
2
Ich erwarte, dass ich RandomQueuedie QueueSchnittstelle implementiere und die mitgelieferte removeMethode zufällig entferne, anstatt den Kopf zu platzen. Es sollte also keine Möglichkeit geben, sich auf eine bestimmte Reihenfolge zu verlassen. Angesichts der Zufälligkeit sollte der Benutzer meiner Meinung nach nicht erwarten, dass eine bestimmte Reihenfolge eingehalten wird. Ich habe die Aufgabe in meiner Frage zur Klarstellung zitiert. Vielen Dank.
Carcigenicate
2
Ja, es scheint, als ob es Ihnen gut gehen wird, wenn Sie nur sicherstellen, dass das Entfernen des Elements so erfolgt, wie ich es vorgeschlagen habe.
Mike Nakis
Eine letzte Sache, wenn Sie nichts dagegen haben. Ich habe mehr darüber nachgedacht, und es scheint nicht möglich zu sein, sowohl "echte" O (1) -Additionen als auch "echte" O (1) -Zufallsentfernungen vorzunehmen. Es ist ein Kompromiss zwischen der 2. Sie haben entweder eine einfach zugewiesene Struktur (wie ein Array), die das Entfernen, aber nicht das Hinzufügen ermöglicht, oder eine stückweise zugewiesene Struktur wie eine verknüpfte Liste, die das Hinzufügen, aber nicht das Entfernen ermöglicht. Ist das wahr? Nochmals vielen Dank.
Carcigenicate
14

Die Frage scheint spezifisch nach einer konstanten Zeit und nicht nach einer abgeschriebenen konstanten Zeit zu fragen . In Bezug auf die angeführte Frage sind sie also nicht effektiv die gleichen *. Sind sie jedoch in realen Anwendungen?

Das typische Problem bei amortisierten Konstanten ist, dass Sie gelegentlich die aufgelaufenen Schulden bezahlen müssen. Während Einfügungen im Allgemeinen konstant sind, müssen Sie manchmal den Aufwand für das erneute Einfügen von Daten erleiden, wenn ein neuer Block zugewiesen wird.

Wo der Unterschied zwischen konstanter Zeit und abgeschriebener konstanter Zeit für eine Anwendung relevant ist, hängt davon ab, ob diese gelegentliche sehr langsame Geschwindigkeit akzeptabel ist. Für eine sehr große Anzahl von Domains ist dies im Allgemeinen in Ordnung. Insbesondere wenn der Container eine effektive maximale Größe hat (wie Caches, temporäre Puffer, Arbeitscontainer), können Sie die Kosten effektiv nur einmal während der Ausführung bezahlen.

Bei reaktionskritischen Anwendungen können diese Zeiten inakzeptabel sein. Wenn Sie eine kurzfristige Garantie benötigen, können Sie sich nicht auf einen Algorithmus verlassen, der diesen Wert gelegentlich überschreitet. Ich habe bereits an solchen Projekten gearbeitet, aber sie sind äußerst selten.

Es kommt auch darauf an, wie hoch diese Kosten tatsächlich sind. Vektoren tendieren dazu, eine gute Leistung zu erbringen, da ihre Umverteilungskosten relativ niedrig sind. Wenn Sie jedoch zur Hash-Karte gehen, kann die Neuzuweisung viel höher sein. Allerdings sind für die meisten Anwendungen wahrscheinlich gute, insbesondere längerlebige Server mit einer Obergrenze für die Elemente im Container.

* Hier gibt es allerdings ein kleines Problem. Damit ein Allzweckcontainer eine konstante Zeit für das Einfügen hat, muss eine der beiden folgenden Bedingungen erfüllt sein:

  • Der Container muss eine feste Maximalgröße haben; oder
  • Sie können davon ausgehen, dass die Speicherzuordnung der einzelnen Elemente zeitlich konstant ist.
edA-qa mort-ora-y
quelle
"Liver Server" scheint hier eine seltsame Formulierung zu sein. Meinen Sie vielleicht "Live-Server"?
Pieter Geerkens
6

Es hängt davon ab, ob Sie den Durchsatz oder die Latenz optimieren:

  • Latenzempfindliche Systeme benötigen eine konsistente Leistung. Für ein solches Szenario müssen wir das Worst-Case-Verhalten des Systems hervorheben. Beispiele sind Soft-Real-Time-Systeme wie Spiele, die eine konsistente Bildrate erzielen möchten, oder Webserver, die innerhalb eines bestimmten engen Zeitrahmens eine Antwort senden müssen: Die Verschwendung von CPU-Zyklen ist besser als Verspätung.
  • Durchsatzoptimierte Systeme kümmern sich nicht um gelegentliche Stillstände, solange die maximale Datenmenge auf lange Sicht verarbeitet werden kann. Hier interessieren uns vor allem amortisierte Leistungen. Dies ist im Allgemeinen der Fall bei der Zahlenverarbeitung oder anderen Stapelverarbeitungsaufträgen.

Beachten Sie, dass ein System verschiedene Komponenten haben kann, die unterschiedlich kategorisiert werden müssen. Zum Beispiel würde ein moderner Textprozessor einen latenzempfindlichen UI-Thread haben, aber durchsatzoptimierte Threads für andere Aufgaben wie Rechtschreibprüfung oder PDF-Exporte.

Außerdem spielt die algorithmische Komplexität oft keine so große Rolle, wie wir vielleicht denken: Wenn ein Problem an eine bestimmte Zahl gebunden ist, sind die tatsächlichen und gemessenen Leistungsmerkmale wichtiger als das Verhalten „für sehr große n “.

amon
quelle
Leider habe ich sehr wenig Hintergrundwissen. Die Frage endet mit: "Die Operationen add (x) und remove () in einer RandomQueue sollten pro Operation in konstanter Zeit ausgeführt werden."
Carcigenicate
2
@Carcigenicate Wenn Sie nicht wissen, dass das System latenzempfindlich ist, sollte es absolut ausreichend sein, die amortisierte Komplexität zur Auswahl einer Datenstruktur zu verwenden.
Am
Ich habe den Eindruck, dass dies eine Programmierübung oder ein Test sein könnte. Und schon gar nicht einfach. Absolut richtig, dass es sehr selten darauf ankommt.
gnasher729
1

Wenn Sie nach einem "Amortized Constant Time" -Algorithmus gefragt werden, kann Ihr Algorithmus manchmal sehr lange dauern. Wenn Sie beispielsweise in C ++ std :: vector verwenden, hat ein solcher Vektor möglicherweise Platz für 10 Objekte. Wenn Sie das 11. Objekt zuweisen, wird Platz für 20 Objekte zugewiesen, 10 Objekte werden kopiert und das 11. Objekt hinzugefügt braucht viel Zeit. Wenn Sie jedoch eine Million Objekte hinzufügen, können 999.980 schnelle und 20 langsame Operationen ausgeführt werden, wobei die durchschnittliche Zeit schnell ist.

Wenn Sie nach einem Algorithmus mit "konstanter Zeit" gefragt werden, muss Ihr Algorithmus für jede einzelne Operation immer schnell sein. Dies ist wichtig für Echtzeitsysteme, bei denen Sie möglicherweise die Garantie benötigen, dass jeder einzelne Vorgang immer schnell ist. "Konstante Zeit" wird sehr oft nicht benötigt, aber es ist definitiv nicht dasselbe wie "abgeschriebene konstante Zeit".

gnasher729
quelle