DAS WETTRENNEN der Algorithmen

Ich hab schon mal nen Algorithmus geproggt der hat das logon in 12ms geschaft.

Ich habe schonmal einen Sortieralgorithmus geschrieben der eine bereits sortierte Folge in O(n) sortieren kann.

Gregor

Wie sieht es bei Sortieralgorithmen eigentlich mit der Parallelisierbarkeit aus? Sollte das nicht langsam relevant werden? Wie macht man das am Besten? Der Quicksort teilt das Problem ja schonmal auf, insofern hat man doch eigentlich recht gute Ausgangsbedingungen. Aber wie sorgt man dafür, dass die Teilprobleme ähnlich komplex sind? Oder geht man da komplett anders heran?

EDIT: Habe gerade in meinen Unterlagen einen parallelen Sortieralgorithmus gefunden, der auf Mergesort basiert. Da ist die Aufteilung natürlich einfacher und das geht wohl insgesamt recht einfach. Wie sieht es diesbezüglich aber mit Quicksort aus?

Das Sortieren ist sowieso total überbewertet. Wer muss den schon so oft riesen Datenmenge sortieren?

Dravere

Z.b. ich ... sogar als Hobbyprogger. Hab ein Programm das Daten sucht und auflistet. Das gibt manchmal Listen mit 5'000+ an Elementen, die müssen dann nach unterschiedlichen vom User verlangten Kriterien sortiert werden. Das mache ich mit einem Mergesort. Wenn ich einen Bubblesort z.b. dafür verwenden würde ... puuuh ^^ ... das würde ja nie zu ende kommen

Grüssli

Gregor

FachmannFürAlgorithmen schrieb:

Wer muss den schon so oft riesen Datenmenge sortieren?

Google!

Blue-Tiger

Gregor schrieb:

Wie sieht es bei Sortieralgorithmen eigentlich mit der Parallelisierbarkeit aus? Sollte das nicht langsam relevant werden? Wie macht man das am Besten? Der Quicksort teilt das Problem ja schonmal auf, insofern hat man doch eigentlich recht gute Ausgangsbedingungen. Aber wie sorgt man dafür, dass die Teilprobleme ähnlich komplex sind? Oder geht man da komplett anders heran?

EDIT: Habe gerade in meinen Unterlagen einen parallelen Sortieralgorithmus gefunden, der auf Mergesort basiert. Da ist die Aufteilung natürlich einfacher und das geht wohl insgesamt recht einfach. Wie sieht es diesbezüglich aber mit Quicksort aus?

Mergesort ist IMO deshalb besser fuers Paralellisieren geeignet, da er die zu verarbeitenen Daten "gleichmaessig" aufteilt. Einn paralellisierten Quicksort kann ich mir schon vorstellen, aber in der "ersten Ebene" (d.h. vor dem ersten rekursiven Aufruf) muss die Arbeit nur von 1 CPU erledigt werden (zumindest meiner Meinung nach), danach koennen die beiden zerlegten Arrays auf 2 getrennte CPUs aufgeteilt werden:

Im Optimalfall sind bei jeder Teilung sind die Teilarrays gleich gross. Da die Teilarrays "gleichzeitig" abgearbeitet werden koennen, wuerd sich die Komplexitaet in jeder Rekursionsstufe halbieren:

n + (n/2) + (n/4) + (n/8) + .... = $\sum_{i=0}^{log(n)}\frac{n}{2^i}$ was fuer n->unendlich = n*log(n)

zumindest wenn ich mich jetzt nicht verrechnet hab. Damit wuerdest du in der gleichen Komplexitaetsklasse liegen wie der normale Quicksort.

EDIT: dummes Latex

Gregor

Ohne jetzt deine Rechnung durchzugehen...

Der parallele Mergesort liegt zumindest in O(log n * log log n).

Blue-Tiger

Evtl. interessiert dich das: (vergleich paralleler Mergesort und paralleler Quicksort)
www.cis.udel.edu/~pollock/372/f04/udtools.ppt

BTW gibts zum Thema "parallel Quicksort" erstaunlich viele Papers

vielleicht ganz interessant:
http://sortieralgorithmen.de/avlsort/index.html

bzw. http://www.sortieralgorithmen.de/