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 ArrayLists-Ergänzungen als amortisierte konstante Zeit betrachtet werden, da für eine Hinzufügung möglicherweise eine Neuzuweisung des zugrunde liegenden Arrays erforderlich ist, nämlich O (n).

Sind die amortisierte konstante Zeit und die konstante Zeit effektiv gleich oder muss ich mir eine Struktur ansehen, die nicht bei jeder Addition eine vollständige Neuzuweisung erfordert?

Ich frage dies, weil ich mir, abgesehen von Array-basierten Strukturen (die meines Wissens immer Amortized Constant Time-Ergänzungen enthalten werden), nichts vorstellen kann, das die Anforderungen erfüllt:

  • Alles, was auf einem Baum basiert, hat bestenfalls O (log n) -Zugriff.
  • Eine verknüpfte Liste kann möglicherweise O (1) -Zusätze enthalten (wenn ein Verweis auf den Schwanz beibehalten wird), aber a Die zufällige Entfernung sollte bestenfalls O (n) sein.

Hier ist die vollständige Frage, falls ich einige wichtige Details überglast habe:

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

Kommentar s

  • Gibt die Zuweisung an, wie zufällige Entfernungen durchgeführt werden? Erhalten Sie einen Index zum Entfernen oder einen Verweis auf ein Warteschlangenelement?
  • ‚ gibt keine Einzelheiten an. Die Anforderungen sind nur eine Struktur, die die Warteschlangenschnittstelle implementiert und O (1) -Zusätze und -Entfernungen enthält.
  • Abgesehen davon muss ein anpassbares Array mit wachsendem O (n) nicht unbedingt O (1) hinzugefügt werden : Dies hängt davon ab, wie wir das Array vergrößern. Das Wachsen um einen konstanten Betrag a ist immer noch O (n) für die Addition (wir haben eine 1/a Chance für eine O (n) -Operation), wächst aber um Ein konstanter Faktor a > 1 ist O (1), der zur Addition amortisiert wird: Wir haben eine (1/a)^n Chance auf eine O (n) -Operation, aber das Die Wahrscheinlichkeit nähert sich Null für große n.
  • ArrayLists verwenden letztere richtig?
  • Der Autor der Frage (ich) dachte an die amortisierte Lösung mit konstanter Zeit. Ich ‚ werde dies in der nächsten Ausgabe klarstellen. (Obwohl hier die Konstantzeit im ungünstigsten Fall mit der Technik der Amortisation erreicht werden kann.)

Antwort

Amortisierte konstante Zeit kann fast immer als äquivalent zur konstanten Zeit angesehen werden, ohne die Besonderheiten Ihrer Anwendung und die Art der Verwendung zu kennen, die Sie planen In dieser Warteschlange besteht die größte Wahrscheinlichkeit, dass Sie abgedeckt werden.

Eine Array-Liste hat das Konzept der Kapazität , das im Grunde der größten Größe / Länge / Anzahl der Elemente entspricht, die wurde bisher jemals von ihm verlangt. Was also passieren wird, ist, dass sich die Array-Liste am Anfang immer wieder neu zuordnet, um ihre Kapazität zu erhöhen, wenn Sie weitere Elemente hinzufügen. Irgendwann entspricht die durchschnittliche Anzahl der pro Zeiteinheit hinzugefügten Elemente jedoch zwangsläufig der durchschnittlichen Anzahl der Elemente Pro Zeiteinheit entfernt (andernfalls würde Ihnen ohnehin der Speicher ausgehen). Zu diesem Zeitpunkt hört das Array auf, sich neu zuzuweisen, und alle Anhänge werden zum konstanten Zeitpunkt von O (1) ausgeführt.

Allerdings Beachten Sie, 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 . 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.

Kommentare

  • Verdammt, guter Punkt beim Entfernen; Ich habe ‚ das nicht berücksichtigt. Und da wir ‚ Elemente nach dem Zufallsprinzip entfernen, bedeutet ‚ technisch nicht, dass es ‚ ist Ist in diesem Sinne sowieso keine Warteschlange mehr?
  • Ja, das bedeutet, dass Sie es nicht wirklich als Warteschlange behandeln. Ich weiß jedoch nicht, wie Sie die zu entfernenden Elemente finden möchten. 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 kein Glück.Wenn es Ihnen egal ist, ob die Reihenfolge der Elemente verstümmelt ist, ist alles in Ordnung.
  • Es wird erwartet, dass meine RandomQueue die Queue -Schnittstelle und für die mitgelieferte remove -Methode, die zufällig entfernt werden soll, anstatt den Kopf zu platzen, sollte also nicht ‚ Sie können sich nicht auf eine bestimmte Bestellung verlassen. Ich denke, angesichts der Zufälligkeit sollte der Benutzer ‚ nicht erwarten, dass er eine bestimmte Reihenfolge einhält. Ich habe die Aufgabe in meiner Frage zur Klarstellung zitiert. Vielen Dank.
  • Ja, dann scheint es Ihnen gut zu gehen, wenn Sie nur sicherstellen, dass das Entfernen des Elements wie von mir vorgeschlagen erfolgt.
  • Eine letzte Sache, wenn Sie nicht ‚ macht nichts. Ich ‚ habe mehr darüber nachgedacht, und ‚ scheint nicht ‚ zu sein Es ist möglich, sowohl “ true “ O (1) -Additionen als auch “ true “ O (1) zufällige Entfernung; ‚ ist ein Kompromiss zwischen der 2. Sie haben entweder eine einfach zugewiesene Struktur (wie ein Array), die das Entfernen, aber keine Addition ermöglicht, oder eine Chunk-zugewiesene Struktur wie eine Linked- Liste, die Ergänzungen enthält, aber keine Entfernung. Ist das wahr? Nochmals vielen Dank.

Antwort

Die Frage scheint speziell nach konstanter Zeit zu fragen und nicht nach einer amortisierte konstante Zeit . In Bezug auf die zitierte Frage sind sie also nicht effektiv gleich *. Befinden sie sich jedoch in realen Anwendungen?

Das typische Problem bei der amortisierten Konstante ist, dass Sie gelegentlich die aufgelaufenen Schulden bezahlen müssen. Während Einfügungen im Allgemeinen konstant sind, müssen Sie manchmal den Aufwand erleiden, alles erneut einzufügen, wenn ein neuer Block zugewiesen wird.

Wo die Differenz zwischen konstanter Zeit und amortisierter konstanter Zeit für eine Anwendung relevant ist, hängt davon ab, ob Diese gelegentlich sehr langsame Geschwindigkeit ist akzeptabel. 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 während der Ausführung nur einmal effektiv bezahlen.

Bei reaktionskritischen Anwendungen sind diese Zeiten möglicherweise nicht akzeptabel. Wenn Sie eine kurzfristige Bearbeitungsgarantie erfüllen müssen, können Sie sich nicht auf einen Algorithmus verlassen, der diesen gelegentlich überschreitet. Ich habe bereits an solchen Projekten gearbeitet, aber sie sind äußerst selten.

Es hängt auch davon ab, 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. Für die meisten Anwendungen ist dies wahrscheinlich in Ordnung, insbesondere für Server mit längerer Lebensdauer und einer Obergrenze für die Elemente im Container.

* Hier gibt es jedoch ein kleines Problem. Um einen Allzweckcontainer zu erstellen Konstante Zeit für das Einfügen sein Eines von zwei Dingen muss gelten:

  • Der Container muss eine feste maximale Größe haben, oder
  • Sie können davon ausgehen, dass die Speicherzuweisung einzelner Elemente eine konstante Zeit ist

Kommentare

  • “ Leberserver “ scheint hier eine seltsame Formulierung zu sein. Meinen Sie vielleicht “ Live-Server „?

Antwort

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

  • Latenz- Sensible Systeme benötigen eine konsistente Leistung. In einem solchen Szenario müssen wir das Worst-Case-Verhalten des Systems hervorheben. Beispiele sind weiche Echtzeitsysteme wie z s Spiele, die eine konsistente Framerate erreichen möchten, oder Webserver, die innerhalb eines bestimmten engen Zeitrahmens eine Antwort senden müssen: Die Verschwendung von CPU-Zyklen ist besser als die Verspätung.
  • Durchsatzoptimierte Systeme kümmern sich nicht darum gelegentliche Verzögerungen, solange die maximale Datenmenge auf lange Sicht verarbeitet werden kann. Hier sind wir vor allem an der fortgeführten Wertentwicklung interessiert. Dies ist im Allgemeinen bei der Eingabe von Zahlen oder anderen Stapelverarbeitungsaufträgen der Fall.

Beachten Sie, dass ein System unterschiedliche Komponenten haben kann, die unterschiedlich kategorisiert werden müssen. Z.B. Ein moderner Textprozessor hätte einen latenzempfindlichen UI-Thread, aber durchsatzoptimierte Threads für andere Aufgaben wie Rechtschreibprüfung oder PDF-Exporte.

Auch die algorithmische Komplexität spielt oft keine Rolle, wie wir es könnten Denken Sie: Wenn ein Problem an eine bestimmte Anzahl gebunden ist, sind tatsächliche und gemessene Leistungsmerkmale wichtiger als das Verhalten „für sehr große n “.

Kommentare

  • Leider habe ich sehr wenig Hintergrund.Die Frage endet mit: “ Die Operationen add (x) und remove () in einer RandomQueue sollten in konstanter Zeit pro Operation “ ausgeführt werden.
  • @Carcigenicate, es sei denn, Sie wissen, dass das System latenzempfindlich ist. Die Verwendung einer amortisierten Komplexität zur Auswahl einer Datenstruktur sollte absolut ausreichend sein.
  • Ich habe den Eindruck, dass dies der Fall sein könnte eine Programmierübung oder ein Test. Und schon gar nicht so einfach. Absolut wahr, dass es sehr selten wichtig ist.

Antwort

Wenn Sie nach einer „amortisierten konstanten Zeit“ gefragt werden Algorithmus, Ihr Algorithmus kann manchmal lange dauern. Wenn Sie beispielsweise std :: vector in C ++ 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 dauert viel Zeit. Wenn Sie jedoch eine Million Objekte hinzufügen, können Sie 999.980 schnelle und 20 langsame Operationen ausführen, 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 „amortisierte konstante Zeit“.

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.