Priority Queue Performance

[Plauzi92]

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

 

[httpdigest]

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]

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?

 

[Plauzi92]

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.