Hallo,
ich muß ein Array (FreePascal, Sprache ist aber eigentlich egal) mit 1 Mio einträgen sortieren. Welcher Algorithmus wäre empfehlenswert?
Ich habe ein paar Ausprobiert, bei rekursiven steigt das Programm aus, ganz einfache dauern zu lange…
ANtwort am besten per Mail.
Alex
Ich habe ein paar Ausprobiert, bei rekursiven steigt das
Programm aus, ganz einfache dauern zu lange…
Wie meinst du „steigt das Programm aus“? Falls in der Sprache wirklich keine Rekursionen erlaubt sind (was ich mir bei der Bezeichnung „Pascal“ nicht denken kann), dann kannst du eigentlich jeden Algorithmus auch iterativ implementieren, auch QuickSort, MergeSort und Konsorten.
Welchen Algorithmus du anwendest hängt von verschiedenen Faktoren ab, hauptsächlich wie die Elemente des Arrays angeordnet sind (verschiedene Algorithmen haben verschiedene Worst-/Best-Case-Verhalten) und wieviele verschiedene Arten von Elementen du hast.
Grüße, Robert
Array mt 1 Mio Einträgen?
Hallo Robert
Wäre da nicht irgend eine DB sinnvoller? Und wenns nur eine alte DBase DB ist? Da gibts doch sicher auch unter Windows eine relationale Freeware-DB???
Grüsse Peter
Nachtrag:
EJB und Komponente. Der Kollege ist ausser Haus, daher sind die Argumente ausstehend - entschuldige! Grundsätzlich zielte seine Argumente auf die erheblich dünnere Funktionsschicht von EJB im Vergleich zu CORBA 3 / COM+. D.h. das EJB eine Middleware für Java ist und fertig. Vergleichbar mit Einzeller zu Säugetieren.
Wäre da nicht irgend eine DB sinnvoller? Und wenns nur eine
alte DBase DB ist? Da gibts doch sicher auch unter Windows
eine relationale Freeware-DB???
Hmmm, kommt IMHO ganz darauf an was er damit wirklich machen will, aber du hast Recht 1 Million von was auch immer schreien vordergründig nach einer DB. 
EJB und Komponente. Der Kollege ist ausser Haus, daher sind
die Argumente ausstehend - entschuldige! Grundsätzlich zielte
seine Argumente auf die erheblich dünnere Funktionsschicht von
EJB im Vergleich zu CORBA 3 / COM+. D.h. das EJB eine
Middleware für Java ist und fertig. Vergleichbar mit Einzeller
zu Säugetieren.
Das stimmt schon, glaub aber nicht, dass sich das auf die Einstufung als „Komponentenstandard“ auswirkt. Im Gegenteil, die Funktionsschicht macht IMHO eher die Middleware als den Komponentenstandard aus.
Grüße, Robert
Ich habe ein paar Ausprobiert, bei rekursiven steigt das
Programm aus, ganz einfache dauern zu lange…Wie meinst du „steigt das Programm aus“?
Speicher reicht nicht aus (wg. der ganzen Rekusionen…)
Falls in der Sprache
wirklich keine Rekursionen erlaubt sind
doch
(was ich mir bei der
Bezeichnung „Pascal“ nicht denken kann), dann kannst du
eigentlich jeden Algorithmus auch iterativ implementieren,
auch QuickSort, MergeSort und Konsorten.Welchen Algorithmus du anwendest hängt von verschiedenen
Faktoren ab, hauptsächlich wie die Elemente des Arrays
angeordnet sind (verschiedene Algorithmen haben verschiedene
Worst-/Best-Case-Verhalten) und wieviele verschiedene Arten
von Elementen du hast.
Also: es ist ein 100x100x100-Array, je „Pixel“ hat eine Zahl gespeichert. Ich muß nun diese Pixel in aufsteigender Reihenfolge bearbeiten.
Welcher Algorithmus wäre gut? Hast Du einen guten Web-Link?
Alex
Speicher reicht nicht aus (wg. der ganzen Rekusionen…)
Aua.
Hab mal kurz gesucht, hab leider keinen Weblink über die iterativen Varianten gefunden, hab nur das Buch aus der entsprechenden VO bei uns an der Uni.
Allerdings wirst zumindest beim Quicksort ähnliche Schwierigkeiten haben, da arbeitet man mit einem Stack über den man sich Bereiche merkt, und der wird auch ziemlich schnell voll sein. Mergesort weiß ich leider nicht wirklich wie der iterativ arbeitet, schätzomativ aber ähnlich.
Für den Zweck gibts dann sogenannte „External Sorting“ Verfahren, die extra dafür gedacht sind für große Datenmengen, such mal mit einer Suchmaschine nach „external sorting algorithm“, da kommt einiges.
Vielleicht hilft auch ein balanced Tree. Ich hab aber leider keine wirklichen Erfahrungen mit großen Datenmengen, alles was größer als ein paar hundert Datensätze war hatte ich bis jetzt immer in einer DB. :o)
Grüße, Robert
Für den Zweck gibts dann sogenannte „External Sorting“
Verfahren, die extra dafür gedacht sind für große Datenmengen,
such mal mit einer Suchmaschine nach „external sorting
algorithm“, da kommt einiges.
Danke, werde mal schauen.
Vielleicht hilft auch ein balanced Tree. Ich hab aber leider
keine wirklichen Erfahrungen mit großen Datenmengen, alles was
größer als ein paar hundert Datensätze war hatte ich bis jetzt
immer in einer DB. :o)
Nur wg. der Sortierung eine Datenbank einzubinden erschein mir bicht sinnvoll. Sonst würde ich es natürlich machen…
Mir ist auch Portabilität wichtig (sollte die Rechengeschwindigkeit von einem PC mit einem besseren Algorithmus nicht ausreichen, werde ich auf einen Cray umsteigen müssen …)
Alex
yO!
Das mit der Datenbank erscheint mir auch nicht sinnvoll. Schließlich muß die DB ja auch sortieren.
Wie wärs wenn du deine Liste in mehrere Listen aufteilst, diese dann sortierst und anschließend wieder zusammenmischst?
Das kostet natürlich mehr Speicher.
Bei einer angenommen Stringlänge von 50 Zeichen und 1.000.000 Einträgen wären das dann 2 x 500 x 1.000.000 Byte 95,4 MB
vielleicht hilfts dir ja.
cu, holli
Oder noch einfacher:
grober PSEUDOCODE (2 Listen La (Ausgangsliste), Lz (Zielliste)
solange La(1) definiert
lies La(1)
suche sortierlog. Position in Lz
La(1) in Lz einfügen
La shiften (1. Element verwerfen, Restelemente um 1 vorrücken)
/solange
Nur wg. der Sortierung eine Datenbank einzubinden erschein mir
bicht sinnvoll.
Naja, eventuell auch fürs speichern, suchen etc., aber das kannst du am besten beurteilen.
Mir ist auch Portabilität wichtig (sollte die
Rechengeschwindigkeit von einem PC mit einem besseren
Algorithmus nicht ausreichen, werde ich auf einen Cray
umsteigen müssen …)
Das wäre glaube ich übertrieben. Um wieder die Datenbank anzuführen, für eine gute DB sind 1 Mio. Datensätze in einer Tabelle ein Pappenstiel, auch auf einem gut ausgestatteten PC. Die arbeiten halt hochoptimiert und ein Normalsterblicher kann sich kaum das antun was ein Oracle im Hintergrund so alles macht.
Grüße, Robert
Schließlich muß die DB ja auch sortieren.
Jo, aber die Leute die deren Mechanismen geschrieben haben, haben recht viel Zeit damit verbracht.
Aber nur fürs Sortieren braucht man sicher keine DB, hat halt auch viele andre Vorteile.
Wie wärs wenn du deine Liste in mehrere Listen aufteilst,
diese dann sortierst und anschließend wieder zusammenmischst?
Das ist in etwa was die schon angsprochenen „External Sorting“-Algorithmen tun.
Grüße, Robert
Rein theoretisch nicht mal so schlecht, solange du die Einfügeposition binär suchst, kommst du auf n*log(n).
Allerdings ist die Frage wie du das Einfügen machen willst, das wäre extrem langsam, wenn du nicht irgendwie mit einer verpointerten Liste rumtrickst.
Aber ansich sollte sich doch wohl quicksort irgendwie in dieser Sprache auch so implementieren lassen, dass er nicht wegen der Rekursionstiefe aussteigt (braucht der wirklich soviele Rekursionsschritte für 1 Million Elemente?)
Bruno
http://www.uni-magdeburg.de/burdack/quicksort/Studie…
[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]
yO!
Das mit der Datenbank erscheint mir auch nicht sinnvoll.
Schließlich muß die DB ja auch sortieren.Wie wärs wenn du deine Liste in mehrere Listen aufteilst,
diese dann sortierst und anschließend wieder zusammenmischst?
Ich glaube, das ist zu umständlich
Das kostet natürlich mehr Speicher.
Bei einer angenommen Stringlänge von 50 Zeichen und 1.000.000
Einträgen wären das dann 2 x 500 x 1.000.000 Byte
95,4 MB
Keine Stringlänge! Jeweils ein Byte!
Alex
yO!
Das kostet natürlich mehr Speicher.
Bei einer angenommen Stringlänge von 50 Zeichen und 1.000.000
Einträgen wären das dann 2 x 500 x 1.000.000 Byte
95,4 MBKeine Stringlänge! Jeweils ein Byte!
Alex
Hallo Alex,
Hab ich das richtig verstanden?! Du hast ein Array mit 1.000.000 Elementen und der Typ eines Elements ist ein Byte. Wenn dem so ist, dann mach doch einfach ein Array mit 256 Einträgen und zähle in einem Eintrag die Anzahl der gefundenen Werte. D.h. wenn die Daten etwa wie folgt aussehen:
1, 2, 3, 4, 3, 3, 1, 0
würde das Array für die ersten fünf Werte wie folgt aussehen:
[1, 2, 1, 3, 1, …]
Nun kannst Du einfach sortieren, durch Ausgabe des Array
0, 1, 1, 2, 3, 3, 3, 4,
Die Array-Elemente geben an, wie oft eine Zahl ausgegeben werden soll.
Zum „sortieren“ ist die Laufzeite n (wow linear! 
) die Ausgabe dann c*n mit c
genau darauf bin ich auch gekommen
…
Hallo,
ich finde es eigenartig, dass Du Speicherprobleme bei rekursivem Sortieren Deiner 1Mio Eintraege bekommst.
Immerhin benoetigst Du bei paarweisem Vergleich (z.B. Quicksort oder Mergesort) nur 20 oder 21 Rekursionsstufen zur erfolgreichen Abarbeitung. Sollte eigentlich klappen, wenn Du Deine zu sortierenden Daten NICHT als Werteparameter sondern als Variablenparameter ueber die Schnittstelle Deiner Sortierhandlung uebergibst. Vieleicht nutzt Du auch das falsche Speichermodell fuer Deinen Compiler, so dass Dir z.B. nur 64K zur Verfuegung stehen?!
Wenn Du genaue Empfehlungen fuer einen Algorithmus haben willst, dann musst Du mehr Infos ueber Deine Daten preisgeben. Zur Verfuegung stehender Speicherplatz, Schluesselart, Datensatzgroesse, Speichermedium … .
Gruss Bolo