Algorithmus gesucht
-
severality schrieb:
@Knivil:
Du hast sicher recht
Ich suche einen effektiven, richtigen und vor allem effizienteren AlgorithmusDas mit dem Unterschied zwischen effektiv und effizient üben wir aber nochmal!
-
seldon schrieb:
Hmm...musst du damit rechnen, viele kleine Arrays mergen zu müssen, oder geht es eher um eine kleine Handvoll langer Arrays?
Bei m Eingabearrays mit insgesamt n Elementen skaliert der einfache, direkte Merge-Algorithmus (jeweils vorne das kleinste Element raussuchen und ggf. hinten an das Ergebnisarray anhängen) mit O(m * n). Die Heap-Variante oder aneinanderhängen-sortieren-duplikate-entfernen skalieren mit O(n * log(n)). Die Frage ist also, ob zu erwarten steht, dass O(m) < O(log(n)) ist.
Die Heap-Variante mit O(n * log(m)), man hält im Heap nur die m Frontkarten.
-
Ah. Ja, die Idee ist nicht blöd.
-
Du suchst höchstwahrscheinlich nach einer allgemeinen Lösung für die Datentypen "int" oder "long" u.s.w.
Wenn du aber weißt, dass die Eingabedaten durch irgendeinen (kleinen) Wert begrenzt sind, oder der benutzte Datentyp nur wenige Wertezustände besitzt (z.B. (un)signed char, 256 verschiedene Werte), dann kann man's auch in O(m*n + c*M) realisieren, d.h. die Eingabedaten müssten nur einmal gelesen werden.n Felder mit je m Einträgen.
c: eine konstant
M: Anzahl der verschiedenen Wertezustände
-
Hmm, wie wärs mit einem binären Baum?
Du fügst alle Elemente in dem binären Baum ein und vor dem Einfügen schaust du nach, ob das Element schon vorhanden ist.- Einfügen: log(n)
- Suchen: log (n)Das Ergebnis wird wohl besser als log (n) * log(n) sein, da du ja am Anfang noch wenige Elemente hast und wenn du ein Duplikat findest, fällt das log(n) beim Einfügen weg.
EDIT: Mit n kennzeichne ich die Gesamtmenge der Elemente.
EDIT 2: Moment, du hast davon geredet, dass die Mengen schon vorher sortiert sind. Das führt dann dazu, dass der Baum entartet und sich die einzelnen Operationen auf O(n) verlängern. AVL-Bäume wären dann das Richtige für dich.
-
Hallo,
@Steffo: Ja, der AVL-Baum wäre hier passend. Wie du an log(n)*log(n) kommst ist mir ein Rätsel. Es würde bedeuten (wenn wir log als ld auffassen), dass man bei insgesamt 32 Elementen nur 5*5=25 "Operationen" oder bei 64 Elementen 36 "Operationen" brauchen würde. Etwas unwahrscheinlich. Man bedenke, dass jedes Element mindestens einmal gelesen werden muss, also nichts unter n Operationen. O( n*log(n) ) ist da etwas realistischer.
-
Hi,
ja, stimmt, da hatte ich etwas vergessen.
Du iterierst also n mal über deine Gesamtmenge. Bei jeder Iteration machst du dann folgendes:- prüfen, ob das Element schon vorhanden ist - O(ld n)
- wenn nicht vorhanden, dann einfügen - O(ld n)Angenommen, es gibt keine doppelten Elemente (worst case), dann gibt es insgesamt O( n * (ld n + ld n) ) = O( n * (2*ld n)) = O(n * ld n) Operationen.
Ich hoffe, ich liege damit einigermaßen richtig.
L. G.
Steffo
-
Und jetzt bitte berechnen, wenn jeses Element ca 64 mal vorkomt.
-
volkard schrieb:
Und jetzt bitte berechnen, wenn jeses Element ca 64 mal vorkomt.
Hmm, ich schätze mal, du willst auf ein Problem hinaus, aber ich denke, dass das eigentlich super ist, da in m*63 Fällen (es gibt m Elemente) nur gesucht und nicht eingefügt werden muss, was die Laufzeit verkürzt.
-
Steffo schrieb:
volkard schrieb:
Und jetzt bitte berechnen, wenn jeses Element ca 64 mal vorkomt.
Hmm, ich schätze mal, du willst auf ein Problem hinaus, aber ich denke, dass das eigentlich super ist, da in m*63 Fällen (es gibt m Elemente) nur gesucht und nicht eingefügt werden muss, was die Laufzeit verkürzt.
Ich schätze O(n * ld n) Operationen.
Und der AVL-Baum riecht einfach unglaublich langsam im Vergleich zu einem Array.
-
volkard schrieb:
Ich schätze O(n * ld n) Operationen.
Das stimmt, aber der Performancegewinn lässt sich hier in Komplexitätstheorie nicht ausdrücken, da Konstanten wegrationalisiert werden.
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.
-
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...
