Priority Queue Performance

P

Plauzi92

Aktives Mitglied
Hi, ich hätte da mal eine Verständnisfrage zu Priority Queues. In der PQ wird ja die Sortierung immer aufrecht erhalten (oder nach jeder Änderung wieder hergestellt).
Das bedeutet doch, dass "im Hintergrund" irgendein Sortierverfahren laufen muss. Wenn ich stattdessen eine Liste nutze, und die Sortierung mit einem Sortierverfahren im Code quasi selbst herstelle, wird es dann spürbare Performanceunterschiede geben? Allerdings unter der Annahme, dass mein Sortierverfahren nicht signifikant schlechter ist, als das der PQ. Die Frage rührt daher, dass ich bei der Implementation der PQ eine Klasse für den Comparator erstellte, um festzulegen nach welchem Schlüssel wie sortiert werden soll. Das wirkt auf mich komplizierter als einfach eine Liste zu sortieren. Geht es einfach nur darum, den Code in der Klasse, in der man die PQ nutzt, möglichst gering zu halten, oder gibt es einen tatsächlichen Geschwindigkeitsvorteil? Wäre einfach mal interessant zu wissen, da ich mit den PQs irgendwie nicht richtig warm werde.

Viele Grüße
 
H

httpdigest

Top Contributor
Bei einer PriorityQueue (die intern via "Priority Heap" implementiert ist), ist selten eine komplette "Neusortierung" notwendig, wenn du in sie einen neuen Wert hinzufügst oder entfernst. Die asymptotische Laufzeit ist für beide Operationen O(log(n)). Das ist besser als die asymptotische Laufzeit für Sortieren einer Liste mit O(n log(n)).
Allerdings... sind das wie gesagt asymptotische Laufzeiten, und Cache-Hits vs. Cache-Misses können einen grossen konstanten Faktor ausmachen, so dass für Listen von vielleicht mehreren tausend Elementen immer noch ein Resortieren der Liste schneller sein kann als eine PriorityQueue.
Das musst du aber einfach benchmarken/testen.
Letztlich hängt es auch einfach von deinem Anwendungsfall ab. Wenn du einmal eine Liste erzeugst, diese einmal sortierst, und danach die Elemente einfach nur nach der sortierten Reihenfolge nach rausholst, dann wird eine Liste immer das beste sein.

Einen Comparator kannst du für beides immer angeben (Listen sortieren oder PriorityQueue nutzen), oder du nutzt eben die natürliche Ordnung der Elemente (bzw. deren Comparable<T> Implementierung).
 
mrBrown

mrBrown

Super-Moderator
Mitarbeiter
Listen und PriorityQueue sind btw auch nicht einfach gegeneinander austauschbar, über eine PriorityQueue kannst du z.B. nicht in sortierter Reihenfolge iterieren.


Wofür willst du die Queue denn nutzen?
 
P

Plauzi92

Aktives Mitglied
Danke für die Antworten :)
Wofür willst du die Queue denn nutzen?

Jetzt gerade habe ich keinen spezifischen Anwendungsfall. Das letzte mal ging es um den A* Algorithmus für den man eben eine sortierte Liste braucht. Die Implementation der PQ war auch nicht wirklich ein Problem, da gibt es ja etliche Beispiele im Netz. Tatsächlich ging es mir hier nur um das allgemeine Verständnis.
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
A Priority Queue / Comparator Java Basics - Anfänger-Themen 6
T Priority-Queue Java Basics - Anfänger-Themen 9
P Priority Queue Java Basics - Anfänger-Themen 6
K Priority Queue - wo ist denn jetzt der Vorteil? Java Basics - Anfänger-Themen 7
Chabub Hilfe bei Stacks und Queue Java Basics - Anfänger-Themen 2
G Stack und Queue Arbeitsblatt Java Basics - Anfänger-Themen 3
F Queue zyklisch Java Basics - Anfänger-Themen 8
D Queue vs. Stack Java Basics - Anfänger-Themen 6
L Queue mithilfe von 2 Stacks erstellen Java Basics - Anfänger-Themen 1
B Automatisierung von Jobs / @EJB Scheduler / Verhinderung, dass Queue überläuft Java Basics - Anfänger-Themen 2
J Queue Warteschlange Java Basics - Anfänger-Themen 3
J Liste,Queue,Stack sortieren Java Basics - Anfänger-Themen 2
Y Unendlicher Ringbuffer (Queue) Java Basics - Anfänger-Themen 49
C Stack und Queue in Aktion (Bitte Hilfe für die Klausur) Java Basics - Anfänger-Themen 7
E Stack vs Queue - Gemeinsamkeiten / Unterschiede Java Basics - Anfänger-Themen 4
H Collections StackOverflowError in einer Queue Java Basics - Anfänger-Themen 3
R Klassen Die lineare Datenstruktur Queue Java Basics - Anfänger-Themen 3
JokerBlacky Klassen Klasse Queue Klasse mit Attributen anhängen und auslesen können Java Basics - Anfänger-Themen 4
K Queue enq Fehler Java Basics - Anfänger-Themen 2
F Thread der auf eine Queue wartet, sicher beenden Java Basics - Anfänger-Themen 4
A Queue (Array) leeren Java Basics - Anfänger-Themen 1
F HTTP Get Queue Java Basics - Anfänger-Themen 7
J Queue zyklisch auslesen Java Basics - Anfänger-Themen 4
B Generische Queue programmieren Java Basics - Anfänger-Themen 5
S Integer/Value-Paar in Prio-Queue ohne Comparator Java Basics - Anfänger-Themen 5
P Array queue problem Java Basics - Anfänger-Themen 1
L Queue programmieren via BlueJ Java Basics - Anfänger-Themen 5
B Multithreading und eigene Queue entwickeln Java Basics - Anfänger-Themen 3
I Erste Schritte Queue Java Basics - Anfänger-Themen 14
G Queue auf einer Seite löschen, andre Seite schreiben Java Basics - Anfänger-Themen 3
G Queue mit int oder float Java Basics - Anfänger-Themen 3
Q queue.remove Element trotzdem noch vorhanden. Java Basics - Anfänger-Themen 10
M Compiler-Fehler Queue als ArrayList mit Exceptions Java Basics - Anfänger-Themen 3
S Fehler beim Auslösen des ActionListeners in Verbindung mit einer Queue Java Basics - Anfänger-Themen 5
B Queue mit Daten aus einem Stack füllen Java Basics - Anfänger-Themen 21
P Collections Queue mittels ArrayList Java Basics - Anfänger-Themen 2
T Collections Queue<? extends Number> add() offer() Java Basics - Anfänger-Themen 13
S Queue als doppelt verkettete Liste Java Basics - Anfänger-Themen 2
R NullPointerException in Queue-Implementierung Java Basics - Anfänger-Themen 11
B Queue problem! Java Basics - Anfänger-Themen 2
R Queue abhören und Message in Browser ausgeben Java Basics - Anfänger-Themen 3
T Erstellung von Queue mit verkketten listen Java Basics - Anfänger-Themen 3
kulturfenster Stack / Queue Implementationen Java Basics - Anfänger-Themen 11
W Iterator in Queue Java Basics - Anfänger-Themen 5
Q An erste Stelle in eine Queue eintragen Java Basics - Anfänger-Themen 4
H Stack und Queue Java Basics - Anfänger-Themen 6
M Threadsichere Queue in Java 1.5? Java Basics - Anfänger-Themen 2
G Int-Queue in String-Queue umwandeln Java Basics - Anfänger-Themen 5
A Queue erweitern Java Basics - Anfänger-Themen 13
P Queue, Stacks, Listen Java Basics - Anfänger-Themen 7
S Queue als Array implementiert get()? Java Basics - Anfänger-Themen 4
S Queue als verkettete Liste Java Basics - Anfänger-Themen 9
S Queue Java Basics - Anfänger-Themen 30
K Prüfen, ob Queue leer ist Java Basics - Anfänger-Themen 5
P Performance Array und Liste Java Basics - Anfänger-Themen 13
S Performance von byte[], short[], int[]..? Java Basics - Anfänger-Themen 24
I Erste Schritte Resource Bundle - Alles in einem File oder mehrere? => Faktor Performance Java Basics - Anfänger-Themen 2
E Hilfe zur Performance Verbesserung gesucht Java Basics - Anfänger-Themen 1
G Performance - höhere Anzahl Swing Elemente Java Basics - Anfänger-Themen 5
S Performance-/Stress Test für Webanwendung Java Basics - Anfänger-Themen 2
R Datei kopieren: Performance erhöhen Java Basics - Anfänger-Themen 10
S Wie performance lastig sind rekursionen Java Basics - Anfänger-Themen 13
N Bessere Performance durch final: wann denn überhaupt? Java Basics - Anfänger-Themen 28
J Softwaresynthesizer Performance? Java Basics - Anfänger-Themen 11
I Anzahl einer Liste (Performance) Java Basics - Anfänger-Themen 2
J Performance Vergleich von if-Abfragen mit mehreren Bedingungen Java Basics - Anfänger-Themen 9
S Performance HashMap<=>Array Java Basics - Anfänger-Themen 17
J Arrays erweitern - Performance vs Speicherverbrauch Java Basics - Anfänger-Themen 6
M Einträge in Dateien zählen - Performance-Problem Java Basics - Anfänger-Themen 10
S unterschied in performance Java Basics - Anfänger-Themen 4
hdi Worst-Performance-Award für Arbeiten mit ListModel Java Basics - Anfänger-Themen 7
hdi Performance Frage (Threads,Swing) Java Basics - Anfänger-Themen 4
V Performance Lesen und Schreiben aus/in Streams Java Basics - Anfänger-Themen 4
C große Matrizen, Performance, (Pointer?) Java Basics - Anfänger-Themen 6
G import .; - Speicherauslastung, Performance Java Basics - Anfänger-Themen 14
G Performance Java Basics - Anfänger-Themen 18
C Performance IO vs. NIO Java Basics - Anfänger-Themen 5
S dynamic arrays/ performance Java Basics - Anfänger-Themen 2
RaoulDuke Arbeitsweise / Speichernutzung / Performance Java Basics - Anfänger-Themen 10

Ähnliche Java Themen

Anzeige

Neue Themen


Oben