PDA

Archiv verlassen und diese Seite im Standarddesign anzeigen : Beste Datenstruktur für bestimmten Anwendungsfall


Gast
2008-08-31, 15:46:59
Da ich durch Profiling herausgefunden habe, dass der von mir verwendete Java TreeSet ( http://java.sun.com/j2se/1.5.0/docs/api/java/util/TreeSet.html ) den Flaschenhals bildet, wollte ich mal fragen, was für folgendes Szenario die eurer Meinung nach beste Datenstruktur wäre:

Pro Schleifendurchlauf wird das Objekt aus der Struktur, bei dem ein bestimmtes Attribut (double) am kleinsten ist, geholt und entfernt. Anschließend werden dann 0 bis n neue Elemente hinzugefügt. Das ganze läuft so lange bis die Datenstruktur leer ist.
Die maximale Anzahl an Elementen in dem TreeSet war bisher bei 100 aber das könnte sich möglicherweise auch ändern (ich würde also ungern eine feste Struktur nehmen, die nicht vergrößerbar ist)...

Es gibt ja zahlreiche Abwandlungen von Baumstrukturen, TreeSet macht glaube ich einen Rot-Schwarz-Baum. Was würdet ihr denn in diesem Fall anwenden? Das TreeSet hat halt vermutlich relativ viel Overhead; z.B. wird bei mir dann millionenfach die compareTo-Methode aufgerufen, die zwar an sich schnell ist aber bei so vielen Aufrufen dann auch irgendwann ein Faktor wird. Möglicherweise könnte man das reduzieren? Hat jemand hierzu Ideen?

Monger
2008-08-31, 15:58:39
Sets müssen ja sicherstellen, dass kein Element doppelt vorkommt. Dazu muss sowohl die Equals als auch die hashCode Methode korrekt überschrieben werden - machst du das?
Weil wenn nicht, landen möglicherweise all deine Objekte im selben Hash Bucket, und die Suche wird folgerichtig schweinelangsam.

Wenn darüber hinaus es dir egal ist ob dein Element mehrfach in der Datenstruktur vorkommt, solltest du dir überlegen ob du wirklich ein Set brauchst. Tut es eine Linked List vielleicht auch? Die ist bei Einfüge/Löschoperationen ebenfalls recht fix.

Trap
2008-08-31, 16:03:57
Das was du haben möchtest nennt sich Priority Queue und in der Java Standardbibliothek gibt es keine sinnvolle Implementierung davon (decreaseKey() fehlt).

Ich hab mir das selbst geschrieben, basierend auf einem binary heap. Ist um Größenordnungen schneller als TreeSet.
Dazu muss sowohl die Equals als auch die hashCode Methode korrekt überschrieben werden - machst du das?
Er benutzt TreeSet, nicht HashSet.

Monger
2008-08-31, 16:13:53
Er benutzt TreeSet, nicht HashSet.

Trotzdem wird in der API zum TreeSet dringend angemahnt, den Vertrag zu Equals zu erfüllen. Wohl nicht ohne Grund.

Gast
2008-08-31, 16:33:12
Equals() ist implementiert aber ziemlich nutzlos weil diese Methode nie aufgerufen wird (zumindest kommt der Debugger an dem dort gesetzten Breakpoint an).

@Trap: Meinst du sowas wie hier: http://java.sun.com/j2se/1.5.0/docs/api/java/util/PriorityQueue.html ?

Trap
2008-08-31, 16:40:18
@Trap: Meinst du sowas wie hier: http://java.sun.com/j2se/1.5.0/docs/api/java/util/PriorityQueue.html ?
Wenn deine Werte, nach denen sortiert wird, konstant bleiben funktioniert das.

Oft braucht man aber auch das Verringern der bereits in der PQ enthaltenen Werte, das unterstützt das Interface nicht, die Datenstruktur eigentlich schon.

rad05
2008-08-31, 16:45:14
So wie ich das verstanden habe, führst du pro Durchlauf nur eine Entfernenoperation, aber n Einfügeoperationen durch. Wenn n groß ist, solltest du auf ein schnelles Einfügen Wert legen. Da ist einen Baumstruktur nicht optimal. Ein Baum ermöglich schnelles Suchen, aber ein Änderungen in der Struktur (einfügen, löschen) kann teuer (langsam) sein.

Berni
2008-08-31, 17:08:05
Oft braucht man aber auch das Verringern der bereits in der PQ enthaltenen Werte, das unterstützt das Interface nicht, die Datenstruktur eigentlich schon.
Da hast du recht, hätte ich auch schonmal gebraucht und hatte es damals dann über ein remove und add gelöst was wohl nicht wirklich effizient sein dürfte. Ist deine Implementierung vielleicht verfügbar?

Trap
2008-08-31, 17:29:07
Meine Implementierung hat ein Interface mit dem ich nicht ganz glücklich bin. Grundsätzlich wär das nicht schwer zu ändern, aber es war bis jetzt nie nötig.

https://sharesource.org/svn/graphalgoviz/trunk/src/graphviz/queues/HeapPQueue.java
Benutzung wie immer auf eigene Gefahr ;)

robobimbo
2008-08-31, 17:55:30
Die Standard Priority Queue von Java ist nix?

http://java.sun.com/javase/6/docs/api/java/util/PriorityQueue.html
http://java.sun.com/javase/6/docs/api/java/util/concurrent/PriorityBlockingQueue.html

Trap
2008-08-31, 18:19:43
Das Priority Queue aus der Java Bibliothek ist wohl ok (hab es nie probiert), aber es kann kein decreaseKey().

Monger
2008-08-31, 20:42:49
Das Priority Queue aus der Java Bibliothek ist wohl ok (hab es nie probiert), aber es kann kein decreaseKey().

Was soll denn ein decreaseKey machen? :confused:

Berni
2008-08-31, 23:52:34
Was das macht siehst du ja auf der verlinkten Seite. Wenn ein Element, das bereits in der Liste ist einen kleineren Wert erhält, so muss man das Element nicht erst löschen und dann neu einfügen sondern kann mit decreaseKey() einfach ein Neusortieren dieses Elements auslösen.
In der Regel spart dies einiges an Rechenoperationen. decreaseKey() führt ja nur siftup() auf dem Element auf während bei Verwendung von add() und remove() je ein siftup() und ein siftdown() ausgeführt werden würden!
Die Funktion könnte man aber wohl auch bei der original PriorityQueue hinzufügen.

Sephiroth
2008-09-01, 00:14:36
Was soll denn ein decreaseKey machen? :confused:
na das gegenteil von increase key :-| ... gehört aber eher zur pflicht beim min-heap (min-priority queue)


INCREASE-KEY(S, x, k) increases the value of element x's key to the new value k,
which is assumed to be at least as large as x's current key value.

berni hat's ja schon geschrieben: du sparst dir löschen und wieder einfügen und bekommst es so in einer operation hin.

DocEW
2008-09-01, 10:26:06
Lohnt sich denn wirklich eine eigene Implementierung nur wegen eines (kleinen) konstanten Faktors in der Laufzeit einer speziellen Operation? Und deine Version funktioniert auch nur mit int/long, oder?

Ectoplasma
2008-09-01, 11:57:28
Dazu muss sowohl die Equals als auch die hashCode Methode korrekt überschrieben werden - machst du das?


Er benutzt TreeSet, nicht HashSet.

Das meinte Trap.
hashCode() bei TreeSet? ... wohl kaum. :wink:

Trap
2008-09-01, 12:21:41
Meine Implementierung geht nur mit den speziellen Datentypen, ja.

Mein Anwendungsfall ist kürzeste Wege Suche, da gibt es pro Knoten 1 add, 1 remove, aber potentiell sehr viele decreaseKey. In der ersten Anwendung, in der ich das benutzt habe, hat die Suche mehrere Minuten gedauert und die PQ hat 90% der Zeit davon gebraucht. Ein konstanter Faktor langsamer ist da nicht so toll, noch dazu ist er nicht unbedingt klein.

Berni
2008-09-01, 15:40:55
Also wenn man eine eigene Klasse baut, kann das um einen großen Faktor schneller sein. Man kann z.B. sich die compareTo()-Methode sparen und das ganze in der Queue hardcoden, was große Mengen an Funktionsaufrufen spart. Außerdem fallen bei einer eigenen Klasse auch noch jede Menge Casts weg. Ein einzelner Funktionsaufruf und ein einzelner Cast machen nicht viel Performance aus - Millionen aber schon (und auf die kommt man schnell mit der Standard-Implementierung wenn man Wegsuche macht).
Für eine Standardanwendung, die ein paar Werte reinlegt, ists natürlich vollkommen ausreichend die vorgegebenen Klassen zu nutzen.

Gast
2008-09-01, 23:09:07
1.) Wie viele Elemente werden es in Zukunft ca. werden. Es macht einen Unterschied, ob man es wirklich nur mit den 100 oder mit 1 Million zu tun hat. Bei 1K käme man z.B. schon gut mit einer B-Baum Abwandlung mit 2 Ebenen zu Recht. Bzw. fix mit 3 Ebenen.

2.) Wie viele Schleifendurchläufe werden es ca. sein bzw. wie lange dauert bei dir momentan ein Schleifendurchlauf?

3.) Werden die Elemente nach einem bestimmten Muster eingefügt (aufsteigend, absteigend, zufällig, unbestimmt (vielleicht aufsteigend, vielleicht nicht))

4.) Wenn du wirklich Performance willst, so würde ich von den vordefinierten Bäumen generell abraten. Die ganzen Methodeaufrufe sind in Java extrem lahm, da die Methoden erst dynamisch gesucht werden müssen.

5.) Wenn du eine B-Baum Abwandlung machst, so würde ich nur den Double in einem (natürlich sortierten) Array von ca. 30-60 Elementen speichern inkl. einer Referenz auf das wirkliche Objekt. Damit sind die Operationen wesentlich schneller und du kannst auch den Platz in den Buckets mehr verschwenden.

mekakic
2008-12-15, 14:56:20
Kennt jemand eine schnelle Implementation einer PriorityQueue die eben das Aktualisieren von dem Top Element unterstützt?

Also wenn man sich das erste Element per Referenz rausholt, daran was ändert und der Queue sagt: "sortiere mir das mal neu"; bei der STL Implemenation muß ich das Element rauskopieren und wieder neu einfügen. Bei Boost habe ich dazu nix gefunden und mein Profiler hat mir gesagt, daß ich damit (ist eine Art zyklisches Eventsystem) doch einiges an Zeit verbringe.

Trap
2008-12-15, 15:26:32
Eine auf einem Binärheap basierende PQ hat durch den Heap eine balancierte Baumstruktur.

Die Anzahl der Vertauschung durch die Veränderung des Werts ist maximal die Höhe des Baums, beim Aktualisieren vertauscht man von der Wurzel ausgehend, beim Löschen und neu Einfügen von einem Blatt ausgehend. Was schneller ist, hängt vom neuen Wert ab, wenn er nah am Wert der Wurzel ist, ist Aktualisieren schneller, wenn er nah am Wert der Blätter ist, ist Löschen+Einfügen schneller.

Eventuell ist für deine Anwendung eine bucket-basierende PQ sinnvoller (z.B. mit radix heap), die Voraussetzungen dafür sind ganzzahlige und nach oben beschränkte Prioritäten. Verändern einer Priorität ist damit in konstanter Zeit möglich.

mekakic
2008-12-16, 10:28:05
Danke, also meine Prioritäten sind Int64 mit dem Zeitpunkt der nächsten Ausführung und danach ist die PQ auch sortiert - das nächste Element liegt immer vorn, aber beschränkt sind sie nicht wirklich. Die Zeiten werden immer größer und die kleinste liegt immer vorn.

Dahinter stehen Events, die zyklisch geschickt werden müssen (jeder Typ hat sein eigenes Zeitfenster). Dazu wird geschaut, ob das erste Event abgeschickt werden kann, das wird gemacht und der Zeitpunkt für das nächste Verschicken wird aktualisiert und wieder in die Liste eingetragen. Dies wird solange gemacht, bis zu dem Punkt, daß das oberste Element noch nicht verschickt werden kann. Dann wird bis zum nächsten Event geschlafen.

Die Zeitpunkte der einzelnen Events haben einen großen Spielraum - von 10ms bis 300000ms. Auch die Anzahl der gleichzeitigen Elemente in der PQ kann sehr unterschiedlich sein, von nur 1-3 zu maximal etwa um 50.

Bietchiebatchie
2008-12-17, 20:53:49
Auch die Anzahl der gleichzeitigen Elemente in der PQ kann sehr unterschiedlich sein, von nur 1-3 zu maximal etwa um 50.
Also anders gesagt: die PQ ist nahezu leer ;)

Falls die Performance in deinem Fall wirklich so wichtig ist, würde ich auch alle simplen Standardcontainer wie Arrays, Listen, vector/arraylist etc. durchprobieren.
Denn es es ist sehr gut möglich, dass der Overhead von einer PQ größer ist als z.B. das Kopieren eines 10-elementigen (implizit sortierten) Arrays in ein 11-elementiges (incl. neuem Element).
Bei einer so niedrigen Anzahl von Elementen kann man einfach nicht genau sagen, welche Datenstruktur am besten ist, da die Performance doch zusehr von dem konkreten Anwendungsfall abhängt => einfach ausprobieren und messen.