[linux-l] [OT]: algorithmische Frage: Sort parallelisieren

[olafBuddenhagen at gmx.net]

Hallo,

On Wed, Jan 03, 2007 at 07:11:23AM +0000, Rocco Rutte wrote:

> Wieso ist MergeSort im Vergleich zu QuickSort schneller und besser?
> Beide gehören zur selben Klasse, für man zeigen kann, dass es nicht
> mehr schneller geht (die Komplexität, nicht die Implementierung).

Das bedeutet nur, dass typischer Weise etwa die gleiche Anzahl
Operationen gebraucht werden -- was aber noch lange nicht heißt, dass
die Algorithmen die gleiche Performance bieten! QuickSort als
"optimalen" Algorithmus zu bezeichnen ist eine hartnäckige Falschheit,
die sich schwer ausmerzen lässt, da man den Blödsinn immer wieder in
Büchern findet...

Das Stichwort heißt Datenlokalität. Sobald man mit etwas größeren
Datenmengen arbeitet, spielt die Anzahl der durchgeführten Operationen
nur noch eine untergeordnete Rolle. Viel wichtiger ist es, wie effektiv
die Caches genutzt werden -- ein ungecachter Zugriff auf den
Hauptspeicher ist bei heutigen Prozessoren um etwa zwei Größenordnungen
langsamer als normale Befehle. Wenn es sich um wirklich große
Datenbestände handelt, und somit auch noch die Festplatte im Spiel ist,
kommen natürlich diverse Größenordnungen drauf...

Ein Algorithmus mit guter Datenlokalität arbeitet überwiegend mit Daten
die dicht beieinander liegen, statt ständig im gesammten Datenbestand
umherzuspringen. Ich habe mich da nie wirklich reingelesen oder
reingedacht, aber QuickSort soll in dieser Hinsicht sehr schlecht sein,
wohingegen MergeSort wesentlich besser dasteht.

Eine gewisse Datenlokalität ist auch Vorraussetzung um parallelisieren
zu können -- nur so kann man einzelnen Threads Teile des Datenbestandes
zuweisen, damit sie sinnvoll zusammen arbeiten können.

-Olaf-