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

[Volker Grabsch]

On Wed, Jan 03, 2007 at 08:42:39PM +0100, Oliver Bandel wrote:
> On Wed, Jan 03, 2007 at 05:32:33PM +0100, Volker Grabsch wrote:
> [...] 
> > Auch wenn Quicksort bekannter ist und häufiger eingesetzt wird, hat
> > das doch eher was mit den Datenstrukturen zu tun (Arrays in C/Fortran/...).
> > Verwendet man hingegen verkettete Listen, in funktionalen Sprachen
> > etwas ganz Natürliches, dann ist auf jeden Fall Mergesort das Mittel
> > der Wahl.
> 
> Interessanter Aspekt... das mit den funktionalen Sprachen :)
> 
> Aber Listen sind doch eher ineffektiv.
> Nimmt man da nicht besser Baumstrukturen?

Du musst die Aufspaltung von "A B C D E F G H" ja nicht so machen:

    A B C D  |  E F G H

Du kannst ja auch so zerlegen:

    A C E G  |  B D F H

Das ist eine etwas geschicktere Halbierung der Liste. Programmtechnisch
natürlich schwieriger, jetzt den richtigen Kontrollfluss hinzukrigen.
In OCaml könnte man dafür das Stream-Interface versuchen. In Python
und Haskell gibt ebenfalls ähnliche Konstrukte. Auch in LISP/Scheme
müsste man das mit Boardmittel hinkriegen, oder diese Boardmittel
problemlos schreiben können. Schicke Sache, so eine programmierbare
Programmiersprache.

In C/C++/Java/Pascal/... bist du da natürlich erschossen. Da wird's
sehr aufwändig und viel komplizierter.
 


Wenn du Binärbäume einsetzt, dann geht natürlich noch was ganz anders:
Insertion-Sort. Das heißt, die Daten werden sequentiell durchgegangen
und sortiert in einen Binärbaum eingetragen. Das ist ebenfalls elegant
und flink, der Baum könnte jedoch entarten, und dann hast du wie beim
Quicksort plötzlich O(n^2).

Das Merging zweier sortierter Binärbäume ist haarig, daher kann ich
mir nicht vorstellen, wie man Insert-Sort parallelisieren könnte. Aber
ansehen kannst du es dir ja trotzdem mal. Zur Allgemeinbildung gehört
der auf jeden Fall dazu.


> Also ich werde mir dann gleich mal das Mergesort anschauen.
> Ist jadoch eine recht interessante Sache mit dem parallelisierten
> Sort.

Wofür brauchst du das überhaupt? Rein akademisches Interesse? Oder eine
Übungsaufgabe? Oder ein reales Problem, das dahinter steckt?


Viele Grüße,

    Volker

-- 
Volker Grabsch
---<<(())>>---
Administrator
NotJustHosting GbR