Algorithmus gesucht

Ich brauche für ein Programm einen Algorithmus,
der aus mehreren Arrays eine "geordnete Menge" als Array konstruiert.

Beispiel:

Eingabe:
[1,2,3]
[2,3,4]
[3,4,5]

Ausgabe:
[1,2,3,4,5]

Das Ergebnisarray soll sortiert sein und es kann davon ausgegangen werden, dass die Eingabearrays auch sortiert sind.

Ich könnte das ganze natürlich ganz naiv lösen:
Gehe jedes EingabeArray durch, siehe ob Element x schon im Ausgabearray ist, adde es wenn nätig und sortiere am Schluss.
Aber ich denke dass das so ziemlich das mieseste ist, was ich machen könnte.

Ich vermute, dass dieses Problem aber "standard" ist und es schon etwas sehr effektives gibt.

knivil

Das Ergebnisarray soll sortiert sein und es kann davon ausgegangen werden, dass die Eingabearrays auch sortiert sind.

Implementiere das doch erstmal. Dann hast du eine Referenz mit der du neue Varianten testen kannst. Danach kannst du dich auf die Vereinigung von nur zwei Mengen konzentrieren. Der Sprung zu mehr als zwei ist dann nicht mehr gross.

Allgemein: Man nehme das kleinste Element der n-Arrays (steht jeweils am Anfang) und fuege es dem Resultat hinzu, wenn es noch nicht enthalten ist. Entferne das Element aus dem Array (oder verschiebe den Index). Da alle sortiert sind braucht nur mit dem zuletzt hinzugefuegtem zu vergleichen. Laufzeit O(n).

effektives

Es gibt einen Unterschied zwischen effektiv und effizient.

SeppJ

Nimm mehrere Kartenspiele, so dass du manche Karten doppelt hast. Mach dir zwei bis drei Häufchen Spielkarten, sortiere die Häufchen, lege sie so hin, dass du jeweils die niedrigste Karte eines Stapels sehen kannst. Nun baust du einen großen sortierten Stapel ohne Duplikate aus den kleinen Häufchen. Dabei sollte dir dann auffallen, dass es wesentlich bessere Methoden gibt, als deine "naive" Lösung.

volkard

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?)

Vielen Dank erstmals.

Natürlich weiß ich, dass die naive Variante nicht optimal ist und habe auch Ansätze zur Verbesserung.
(Ich wollte nur zeigen, dass ich durchaus in der Lage wäre, das Problem zu lösen und es sich nicht um eine Hausaufgabe oder ähnliches handelt)
Da ich den Algorithmus allerdings nur für ein Programm brauche, mächte ich nicht allzu viel Zeit darauf verschwenden, das Problem komplett zu durchdenken.

Ich habe gehofft, dass es schon etwas vorgefertigtes gibt, so eine Art Standardbibliothek für C etwa.

Falls das nicht der Fall ist, werde ich SeppJ's Ansatz implementieren.

@Knivil:
Du hast sicher recht
Ich suche einen effektiven, richtigen und vor allem effizienteren Algorithmus

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.

severality schrieb:

@Knivil:
Du hast sicher recht
Ich suche einen effektiven, richtigen und vor allem effizienteren Algorithmus

Das mit dem Unterschied zwischen effektiv und effizient üben wir aber nochmal!

volkard

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.

dimiKL

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.

dimiKL

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

volkard

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.

volkard

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.

Allesquatsch

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

volkard

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.

dot

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...