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

[Oliver Bandel]

On Thu, Jan 04, 2007 at 02:14:10AM +0100, Volker Grabsch wrote:
> 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


Äh, was? Worauf willst Du hinaus?
Die Liste daoben ist schon sortiert.
Diewürdeich garnicht mehr ausienander schnippeln. :)




> 
> Das ist eine etwas geschicktere Halbierung der Liste. Programmtechnisch
> natürlich schwieriger,
[...]

?!
 
[...]
> 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).

Wieso kann der Baum entarten? Und was heisst das da?
Dumeinst, daß alles an einer Seite hängt und die Tiefe nicht gleichmäßig ist?
Und wenn Du das meinst: da gibt's doch auch Sortierbäume, bei denen man
beim Einsetzen der Daten die Tiefe Konstant hält, so daß der Baum
nicht an einer Seite "zu schwer" wird.


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

Gehört das zur Allgemeinbildung des Bäckersauch 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?

Das wurde vorgestern als mögliche neue Aufgabe in demProjekt,
wo ich arbeite, angedacht.

Bereich Datenbankmigration, fette Files mit einigen GB Größe,
so daß man da nicht soohne weiteres die algorithmischen Probleme
oder dieder FileSize ignorieren kann.

Die Sortierung läuft derzeit wohl nur SingleThreaded in einem Prozess,
und ich kenne zwar die Detailsnicht, aber wenn dieLeute mit C gearbeitet
haben und die stdlib genutzt haben, daist nurQuicksort verfügbar....

...vielleicht wird das auch nochmals aufgegriffen, dann habe ich da wieder
eine sehr interessante,spannende Aufgabe. Ansonsten stehen halt noch andere
Sachen an.
Schon die LargeFile-Probleme sind ja eine Sache für sich, die auch etwas
Suchen erfordert. Zum Beipiel treten dieseProbleme ja auch bei stat(2)
auf; da habe ich also für eins der Tools ein open mitO_LARGEFILE gemacht.
Ind erManpagezu stat stand da aber nix zu dem LargeFile-Problem.
Also ist das Programm erst mal an der Stelle abgebrochen.
Naja, und da die Namensgebung auch nicht soeinheitlich ist
(also stat und stat64 heisst es bei dem einen System, bei anderen Systemen
zum Beispiel gibt es stat64 nicht und es heisst anders.... also ist dann googlen
angesagt... tse.)

Interessant fand ich aber, daß bei OCaml (arbeite mit 3.09.3) die
LargeFile-Problematik bereits aufgegriffen wurde.
Da wäre ich ggf. mitOCamlbesser gefahren alsmit C. Schon deswegen,
weil in C vieles somühsam ist; wenn man dann nur die Mittel nehmen darf,
die der Admin erlaubt, kann man auch nicht malnach Libs schauen;
aber bei manchen Libs bin ich eh skeptisch, daß die auch sauber genug arbeiten...

Daich Perlund C einsetzen soll
und OCaml offiziell nicht angesagt ist (kann ja mal nach dem Okay für OCaml fragen;-))
dauert alles ewig... :(
Das kann schon bei so trivialen Sachen wie dem  Bearbeiten von Strings nervig sein...

Naja, ma kieken.

Jedenfalls sind Largefiles bei OCaml nicht nur im Unix-module unterstützt,
sondern auch in der gepufferten Library. :)
Habe es aber noch nichtausprobiert. Wenn heute Zeit ist, komme ich evtl.
dazu :) Auf dem Sun-System ist leider 64-Bit-Version von OCaml nicht unterstützt.
Aber da kann man dann ggf. andere Wege finden. Mit funktionaler Programmierung,
wenn man Listen/Bäume usw. statt Arrays nimmt, wird jamit Zeigern gearbeitet,
also klappt das hoffentlich auch mit großen Files.
Aber die Maschine hat eh nur 32 GB RAM, also kann man da eh nicht alles
in den RAM saugen, solange man da nicht der Einzige Benutzer ist...

Gruß,
   Oliver