Algorithmus gesucht
-
dot schrieb:
Steffo schrieb:
Und der AVL-Baum riecht einfach unglaublich langsam im Vergleich zu einem Array.
O(n * ld n) kommt mir ziemlich schnell vor. Ich habe hier auch eine Implementierung in Java, die es mit der Java Collection aufnehmen kann.
Die Lösung mit Array sortieren und Duplikate löschen ist auch O(n * ld n)
Die Frage ist, wie groß die Konstanten sind und dabei wirst du in der Praxis mit dem Array vermutlich wesentlich besser aussteigen als mit irgendeinem Baum...Genau. Zumal es Quicksort mit drei Feldern gibt, was man diesbezüglich noch ein wenig vergewaltigen könnte, daß das Mittelfeld kollabiert. Oder Merge-Sort und bei jedem Merge-Schritt haut man Duplikate raus. Oder Tim-Sort, was damit vermutlich direkt keine Schmerzen hat. Und das würde ich auch noch dahigehend vergewaltigen.
-
dot schrieb:
Die Lösung mit Array sortieren und Duplikate löschen ist auch O(n * ld n)
Die Frage ist, wie groß die Konstanten sind und dabei wirst du in der Praxis mit dem Array vermutlich wesentlich besser aussteigen als mit irgendeinem Baum...Was habt ihr denn alle mit den Arrays? Man kann Bäume auch als Array implementieren. Aber ihr habt insofern recht, dass man sich die vorsortierte Eigenschaft zu Nutze machen sollte, was AVL-Bäume nicht tun.
-
Steffo schrieb:
Was habt ihr denn alle mit den Arrays? Man kann Bäume auch als Array implementieren.
Wie auch immer man den Baum speichert, du wirst beim Traversieren des Baums immer wie wild durch die Gegend hüpfen, was die Performance bei weitem nicht so gern hat wie einfach ein lineares Array durchlaufen (Cache und so)...
-
Steffo schrieb:
Was habt ihr denn alle mit den Arrays? Man kann Bäume auch als Array implementieren. Aber ihr habt insofern recht, dass man sich die vorsortierte Eigenschaft zu Nutze machen sollte, was AVL-Bäume nicht tun.
Ach komm.
Wie willste nen Baum sinnig in ein Array stecken? Nur, indem Du auf dem Array eine Mini-Speicherverwaltung implementiertst. Zum Beispiel als doppelt verketten Ring der Freispeicherknoten. Schon wieder Zusatzaufwand. (Und komm mir nicht mit linksausgerichteten Bäumen.)Mit "Array" ist hier sort&unique gemeint.
-
http://en.wikipedia.org/wiki/Binary_tree#Arrays
Wäre aber beim AVL-Baum wohl viel zu aufwändig und wahrscheinlich auch performancelastiger, bei einfachen Binärbäumen macht das aber durchaus Sinn.
-
Das funktioniert so aber nur wenn der Baum ein vollständiger Baum ist. Zumindest ist es nur dann vernünftig...
-
Steffo schrieb:
http://en.wikipedia.org/wiki/Binary_tree#Arrays
Wäre aber beim AVL-Baum wohl viel zu aufwändig und wahrscheinlich auch performancelastiger, bei einfachen Binärbäumen macht das aber durchaus Sinn.
Langsam wird mir das zu doof.
Ok, man *kann* einen Baum auch anders in ein Array zwingen. Und es macht keinen Sinn, aber auch überhaupt keinen bei einfachen Binärbäumen. Bei AVL-Bäumen würde man es hinkriegen.
Und regelmäßig macht man es mit Heaps, die ja auch Bäume sind.
-
Abgesehen davon, ist es trotzdem langsamer zu traversieren als ein lineares Array...
