Algorithmus gesucht
-
volkard schrieb:
n Arrays der Länge m
a) Einen Heap benutzen, der die Frontkarten verwaltet. O(log(n)*n*m)
(Gar nicht mal so einfach zu proggern, aber die Standard-Lösung noch aus Zeiten der Bandlaufwerke.)b) Alle aneinanderhängen, Sortieren, Duplikate löschen. O(log(n)*n*m+log(m)*n*m)
(Sehr einfach und nichmal so übel.)c) Stets zwei mergen, bis es nur noch eine ist. O(log(n)*n*m)
(Auch optimal, ach, uff. Bißchen doof zu programmieren, weil man ein wenig rumverwalten muß, um immer zwei kurze zu einem langen zu machen, statt alle nacheinander an eine zu hängen. rekursiv?)Verstehe nicht, wieso diese genial einfache Lösung ignoriert wird. Denn nur diese nutzt die Vorsortierung aus und reduziert einen Faktor der Komplexität auf die Anzahl der Bänder (Verzeihung: "Mengen"
)Vor 25 Jahren kam das im Informatikstudium noch als Standardalgorithmus vor Quicksort und B-Bäumen
Der Overhead balancierter Bäume wird erst dann wirtschaftlich, wenn n und m richtig große Werte annehmen und die Vergleiche der Element-Werte "teuer" sind.
Ciao, Allesquatsch
-
Allesquatsch schrieb:
volkard schrieb:
n Arrays der Länge m
a) Einen Heap benutzen, der die Frontkarten verwaltet. O(log(n)*n*m)
(Gar nicht mal so einfach zu proggern, aber die Standard-Lösung noch aus Zeiten der Bandlaufwerke.)b) Alle aneinanderhängen, Sortieren, Duplikate löschen. O(log(n)*n*m+log(m)*n*m)
(Sehr einfach und nichmal so übel.)c) Stets zwei mergen, bis es nur noch eine ist. O(log(n)*n*m)
(Auch optimal, ach, uff. Bißchen doof zu programmieren, weil man ein wenig rumverwalten muß, um immer zwei kurze zu einem langen zu machen, statt alle nacheinander an eine zu hängen. rekursiv?)Verstehe nicht, wieso diese genial einfache Lösung ignoriert wird. Denn nur diese nutzt die Vorsortierung aus und reduziert einen Faktor der Komplexität auf die Anzahl der Bänder (Verzeihung: "Mengen"
)a) ist doch die klassische Bänder-Variante.
-
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...
-
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...
