Eine Prioritätswarteschlange, die eine effiziente Priorität Update ermöglicht?

StackOverflow https://stackoverflow.com/questions/450180

Frage

UPDATE : Hier ist meine Implementierung von Hash-Timing-Wheels . Bitte lassen Sie mich wissen, wenn Sie eine Idee haben, die Leistung und die Parallelität zu verbessern. (20-Jan-2009) 

// Sample usage:
public static void main(String[] args) throws Exception {
    Timer timer = new HashedWheelTimer();
    for (int i = 0; i < 100000; i ++) {
        timer.newTimeout(new TimerTask() {
            public void run(Timeout timeout) throws Exception {
                // Extend another second.
                timeout.extend();
            }
        }, 1000, TimeUnit.MILLISECONDS);
    }
}

UPDATE : Ich löste dieses Problem, indem Sie

Andere Tipps

Nach bestem Wissen und Gewissen (Ich schrieb ein Papier über eine neue Prioritätswarteschlange, die auch die letzten Ergebnisse überprüft), keine Prioritätswarteschlange Implementierung wird die Grenzen der Fibonacci-Heaps sowie konstante Zeiterhöhung-Taste.

Es gibt ein kleines Problem mit dem wahrsten Sinne des Wortes zu bekommen. Wenn Sie in O (1) erhöhen Schlüssel bekommen könnte, dann könnte man in O löschen bekommen (1) - nur den Schlüssel zu + unendlich erhöhen (Sie die Warteschlange umgehen kann voll von vielen + Infinitys wobei einige Standard Amortisation Tricks ). Aber wenn find-min ist auch O (1), das bedeutet, delete-min = find-min + löschen wird O (1). Das ist unmöglich in einem vergleichsbasierten Prioritätswarteschlange, da die Sortierung gebunden impliziert (einfügen alles, dann entfernen one-by-one), dass

  

n * Insert + n * delete-min> n log n.

Der Punkt hier ist, dass, wenn Sie eine Priorität-Warteschlange unterstützen Erhöhung schlüssel in O (1) mögen, dann sind Sie eine der folgenden Strafen akzeptieren müssen:

Aber noch einmal, zum besten meines Wissens hat niemand die letzte Option getan. Ich habe es immer als Chance für neue Ergebnisse in einem ziemlich einfachen Bereich der Datenstrukturen gesehen.

Verwenden Sie Hashed Zündwinkelscheibe - Google ‚Hash Hierarchical Timing-Wheels' für weitere Informationen. Es ist eine Verallgemeinerung der von den Menschen hier gemachten Antworten. Ich hätte gerne ein Hash-Timing-Rad mit einer großen Radgröße bevorzugen hierarchische Räder Timing.

Einige Kombination von Hashes und O (log N) Strukturen sollten das tun, was Sie fragen.

Ich bin mit der Art und Weise zu deuteln versucht, das Problem sind zu analysieren. In Ihrem Kommentar oben, sagen Sie

  

Da das Update sehr sehr häufig auftreten. Lassen Sie uns sagen, dass wir M Nachrichten pro Verbindung senden dann die Gesamtzeit wird O (MNlogN), die ziemlich groß ist. - Trustin Lee (6 Stunden)

, die absolut richtig ist, so weit wie es geht. Aber die meisten Leute die ich kenne würde auf die Kosten konzentrieren pro Nachricht , auf der Theorie, dass, wie Sie App mehr und mehr Arbeit hat, zu tun, natürlich, es wird mehr Ressourcen benötigen.

Also, wenn Ihre Anwendung eine Milliarde Steckdosen offen hat gleichzeitig (ist das wirklich wahrscheinlich?) Die Einführungskosten nur etwa 60 Vergleiche pro Nachricht ist.

Ich werde Geld darauf wetten, dass diese vorzeitige Optimierung ist: Sie haben nicht wirklich die Engpässe gemessen in Ihrem System mit einer Performance-Analyse-Tool wie Codeanalyst oder VTune

.

Wie auch immer, es ist wahrscheinlich eine unendliche Anzahl von Möglichkeiten zu tun, was Sie fragen, wenn Sie nur noch entscheiden, dass keine einzelne Struktur wird tun, was Sie wollen, und Sie wollen eine Kombination der Stärken und Schwächen der verschiedenen Algorithmen.

Eine Möglichkeit ist es, die Buchse Domäne N in eine Anzahl von Buckets der Größe B zu unterteilen, und Raute dann jede Buchse in einem von denen (N / B) Schaufeln. In diesem Eimer ist ein Haufen (oder was auch immer) mit O (log B) Aktualisierungszeit. Wenn eine obere an N gebunden nicht im Voraus festgelegt ist, kann aber variieren, dann können Sie mehr Eimer dynamisch erstellen, die eine kleine Komplikation hinzufügt, aber es ist sicherlich machbar.

Im schlimmsten Fall wird der Watchdog-Timer hat (N / B) Warteschlangen für Exspirationen zu suchen, aber ich nehme an der Watchdog-Timer ist nicht erforderlich, Leerlaufbuchsen in einer bestimmten Reihenfolge zu töten!  Das heißt, wenn 10 Steckdosen Leerlauf in der letzten Zeitscheibe geht, ist es nicht, dass die Zeit-out diese Domäne zuerst für die eine Suche müssen, damit umgeht, dann finden, das die zweite Zeitüberschreitung usw. Es ist einfach die (N / B) Satz von Buckets scannen und alle Timeouts aufzuzählen.

Wenn Sie mit einer linearen Anordnung von Schaufeln nicht zufrieden sind, können Sie eine Prioritätswarteschlange von Warteschlangen verwenden, aber Sie wollen, dass die Warteschlange zu vermeiden, auf jede Nachricht zu aktualisieren, sonst bist du wieder da, wo Sie begonnen haben. Stattdessen definieren einige Zeit, die als die tatsächliche Zeit-out weniger ist. (Say, 3/4 oder 7/8 davon) und Sie setzen nur die Low-Level-Warteschlange in die High-Level-Warteschlange, wenn es längste Zeit, überschreitet.

Und auf die Gefahr der Offensichtliche, wollen Sie nicht Ihre Warteschlangen verkeilt auf verstrichene Zeit. Die Tasten sollten sein starten Zeit. Für jeden Datensatz in den Warteschlangen, würde die verstrichene Zeit muß ständig aktualisiert werden, aber die Startzeit jeden Datensatz ändert sich nicht.

Es gibt eine sehr einfache Art und Weise alle Einsätze zu tun und entfernt in O (1), unter Ausnutzung der Tatsache, dass 1) Priorität auf Zeit basiert und 2) haben Sie wahrscheinlich eine kleine, feste Anzahl von Timeout-Dauer.

  1. Erstellen Sie eine regelmäßige FIFO-Warteschlange alle Aufgaben zu halten, die in 10 Sekunden Timeout. Da alle Aufgaben identische Timeout Dauern haben, können Sie einfach bis zum Ende einfügen und entfernen von Anfang an die Warteschlange zu halten sortiert.
  2. Erstellen Sie eine andere FIFO-Warteschlange für Aufgaben mit 30-Sekunden-Zeitdauer. Erstellen Sie mehrere Warteschlangen für andere Timeout Dauer.
  3. abzubrechen, entfernen Sie das Element aus der Warteschlange. Dies ist O (1), wenn die Warteschlange als eine verkettete Liste implementiert ist.
  4. Neuterminierung kann als Abbrechen-Einsatz erfolgen, da beide Operationen sind O (1). Beachten Sie, dass Aufgaben auf unterschiedliche Warteschlangen neu geplant werden.
  5. Schließlich zu kombinieren all FIFO-Warteschlangen in eine einzige Gesamtprioritätswarteschlange, hat das Haupt einer jede FIFO-Warteschlange in einem regulären Haufen teilnehmen. Der Kopf dieses Haufens wird die Aufgabe mit dem am ehesten ablaufenden Timeout aus allen Aufgaben sein.

Wenn Sie m Anzahl verschiedener Timeout Dauer haben, die Komplexität für jede Operation der Gesamtstruktur ist O (log m). Die Insertion ist O (log m) aufgrund der Notwendigkeit, bis zu suchen, die einfügen Warteschlange. Remove-min ist O (log m) für die Heap-Wiederherstellung. Canceling ist O (1), aber schlimmsten Fall O (log m), wenn Sie den Kopf einer Schlange sind abgebrochen wird. Da m eine kleine, festgelegte Zahl ist, O (log M) im wesentlichen O (1). Es funktioniert nicht mit der Anzahl der Aufgaben skalieren.

Ihr spezielles Szenario schlägt einen Ringpuffer zu mir. Wenn der max. Timeout beträgt 30 Sekunden, und wir wollen Buchsen mindestens nutzen jede Zehntelsekunde ernten, dann einen Puffer von 300 doppelt verketteten Listen, einem für jedes Zehntel einer Sekunde in diesem Zeitraum. Um ‚increaseTime‘ auf einen Eintrag, entfernen Sie sie aus der Liste in es und fügen Sie es dem für seinen neuen zehnten bis zweiten Periode (beide konstant Zeitbetrieb). Wenn eine Periode endet, erntet nichts in der aktuellen Liste übrig bleiben (vielleicht, indem sie einen Reaper-Thread Zuführung) und voran die aktuellen Listenzeiger.

Sie haben eine harte Begrenzung für die Anzahl der Elemente in der Warteschlange stehen -. Gibt es eine Grenze, um TCP-Sockets

Daher wird das Problem begrenzt. Ich vermute, dass jede kluge Datenstruktur langsamer sein wird als integrierte Typen verwendet wird.

Gibt es einen guten Grund, nicht java.lang.PriorityQueue zu benutzen? Nicht entfernen () behandeln Ihre Operationen in log (N) Zeit kündigen? Dann ist Ihre eigene Warte implementieren basierend auf der Zeit, bis der Punkt auf der Vorderseite der Warteschlange.

Ich denke, alle Aufgaben in einer Liste speichern und Iterieren durch sie am besten wäre.

Sie müssen (Richtung), um den Server auf einige ziemlich bullige Maschine an die Grenzen zu bekommen laufen, wo diese Kosten wichtig sein?

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top