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

[Oliver Bandel]

Moin,


On Fri, Jan 05, 2007 at 02:14:53AM +0100, Volker Grabsch wrote:
> On Thu, Jan 04, 2007 at 08:04:03AM +0100, Oliver Bandel wrote:
> > > > 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.
> 
> Nein, ist sie nicht. Von mir aus nennen wir die Listenelemente eben
> nicht
>     A B C D E F G H
> sondern
>     x1 x2 x3 x4 x5 x6 x7 x8
> 
> Du kannst sie so zerlegen:
>     x1 x2 x3 x4  |  x5 x6 x7 x8
> oder so:
>     x1 x3 x5 x7  |  x2 x4 x6 x8


Ach so war das gemeint ;-)

 
[...]
> > > 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? ;-)
> 
> Ich meinte die Allgemeinbildung über Sortier-Algorihmen. Wenn dich das
> Wort stört, formuliere ich es eben um:
> 
> Zum Grundwissen über Sortieralgorithmen gehört der Insert-Sort auf
> jeden Fall dazu.
> 
> > 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.
> 
> "Datenbankmigration", das kann alles und nichts bedeuten.
> 
> Was sind die genauen Anforderungen?
> 

Developing, while taregt moves ;-)


[...]
> Kommen regelmäßig große Haufen unsortierter Daten rein, die ihr
> sortieren müsst?
> 
> Ist die Sortierung nur einmalig nötig?  (dann könntet ihr aber auch
> einen Bubblesort nehmen und wartet eben 2 Wochen)
> 
> Wie muss auf die Daten zugegriffen werden? Werden sie sequentiell
> abgearbeitet? Wird ständig gesucht? ...
> 
> Ist nur die Migration langsam, oder auch der Zugriff?
> 
> > ...vielleicht wird das auch nochmals aufgegriffen, dann habe ich da wieder
> > eine sehr interessante,spannende Aufgabe. Ansonsten stehen halt noch andere
> > Sachen an.
> 
> Da sind so viele offene Fragen. Je nach Antwort könnte eine gute
> Lösung auch vollkommen anders aussehen. Ich finde es übrigens etwas
> anrüchig, dass du nur die Algorithmen und nicht die Datenstrukturen
> in Frage stellst.
[...]

Was findest Du daran anrüchig?


> 
> Und vergiss nicht: Das Dateisystem ist eine hochoptimierte hierarchische
> Datenbank. Das wird ebenfalls sehr gerne unterschätzt.

Es ist fürmanche Zwecke recht brauchbar; aber nicht für alle; deswegen
sind Datenbanken eben doch wichtig.
Davon abgesehen kann ich als Rad im Getriebe nicht vorgeben, welche
Richtung das Auto fahren soll.


> 
> > 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...
> 
> Das hat mich auch gewundert. Die nächste anrüchtige Stelle. Du darfst
> den Algorithmus wählen, nicht jedoch die Programmiersprache.

In manchen Projekten gibt es Vorgaben.
Oder gibt es diemöglicherweise.
In Deiner Hobby-Programmierung mag das anders aussehen,
aber selbst in der Unimuss man dem Profnormalerweise Häppchen vorwerfen,
die er haben will.

> Warum
> quälst du dich mit C rum? Ich meine, mindestens C++ wird doch wohl drin
> sein.

Pfui. C++? Mag ich nicht. DieSyntax ist so Bloatig.

Habe ausserdem mal nachgefragt und OCaml wäre kein Problem,
soweit jedenfalls der jetzige Stand... :)


> 
> Und nein, C++ ist nicht bloß C mit Klassen. Es ist viel mehr, es ist
> Ausdrucksstark, und es hat einige einzigartige Konzepte und Prinzipien.

C++ ist nichts für meinen Geschmack.
Ausdrucksstarksind OCaml und bes. Haskell.
Oder noch besser DSLs.

> Wie ich selbst schmerzlich einsehen musste, liegen weite Welten
> zwischen:
> * C++ Code, der von C-Programmierern geschrieben wurde
> * C++ Code, der von Java-Programmierern geschrieben wurde
> * C++ Code, der von C++-Programmierern geschrieben wurde
> Letzteres ist sehr sauber und elegant, und eine hochinteressante
> herangehensweise.

Es liegen auch Welten zwischen einem <programmiersprache>-Programmierer
und dem nächsten Programmierer in <programmiersprache>.
Ein guter wird die Eigenheiten einer Sprache kennen, also auch,
wenn er von einer anderen Sprache herkommt.Und bei einem schlechten
Programmierer ist es auch egal,ob er 20 Jahre Erfahrung hat, denn
er wird immer Grütze schreiben!

 
[...]
> Ich will jetzt nicht C++ in den Himmel loben, aber wenn du kein Ocaml
> nehmen darfst, dann nimm C++. Das ist mächtiger als Java und *viel*
> mächtiger als C.

Wenn man hier eine perlre-Lib hätte, wäre die C-Lösung schon OK,
denn alles andere liesse sich schon mit C's Bordmitteln und Unix-API
gut machen.

> 
> > Da ich Perlund C einsetzen soll
> > und OCaml offiziell nicht angesagt ist (kann ja mal nach dem Okay für OCaml fragen;-))
> > dauert alles ewig... :(
> 
> Perl *geht* ja auch noch, aber da kannst du mit Performance
> argumentieren. Gegen C kannst du mit Buffer-Overflows argumentieren.

Hatte bei dem einen Programm dummerweise gedacht, es geht mit C besser,
da ich nichtsicher war,ob Perl mit LargeFiles klar kommt.
Da ist aber eine 64-Bit-Version von Perl 5.8.4 installiert und die
scheint kein Problem zu haben damit. Hmhhh.


> 
> Wenn du für Ocaml kein okay kriegst, vielleicht wenigstens für C++.
> 

*würg*  ;-)



> > 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.
> 
> Ähhm, die Dikussion hatten wir vor einiger Zeit schonmal. Also
> nochmal *seufs*:
> 
> Eine Liste ist ein abstraktes Konzept. Ob dahinter eine Datenstruktur
> im RAM liegt, oder eine sequentiell durchlaufene Datei, ist völlig
> nebensächlich.
[...]

Ja, ist mir klar.
Das stimmt aber nur, wenn man es so abstrakt betrachtet und mit
der Brille durchschaut, die genau dieses Ergebnis hervorbringt.

Schautman mit der Performance-Brille, dann erhält man da ein anderes
Ergebnis.
RAM ist eben am schnellsten, und da, wo Zeit Geld kostet, sollte man die
nicht unbedingt mitI/O verballern.

 
[...]
> Der "Parse-Baum" ist ein abstraktes Gebilde. Er kann durch eine
> Datenstruktur im RAM repräsentiert sein. Aber er kann auch einfach
> nur als die Aufruf-Reihenfolge entsprechender Callback-Funktionen
> definiert werden.

Diese Funktionen liegen aber auch im RAM.
Du bestätigst also, wasich meine.
Wir sind wieder an dem Punkt, wowir wegen anderer Sprachwahl
aneinander vorbei reden.



> 
> Wenn du z.B. vom Parser einen Baum im RAM aufbaust, bloß um diesen
> danach Knoten für Knoten abzuarbeiten, dann macht es doch keinen
> Unterschied, ob die Funktionen "start_array", etc. beim Drüberlaufen
> über die Datenstruktur aufgerufen werden, oder direkt vom Parser.
> 
> Gerade in Ocaml mit dem Stream-Interface, oder in Python & Co.
> bei Iteratoren, oder auch mittels Closures, kannst du doch deinen
> Code so schreiben, als ob du über eine Datenstruktur rennst, ohne
> dass dies wirklich passiert. (in Wahrheit wackelt der Parser den
> Eingabestrom ab)

I/O ist langsam.
Vielleicht meinen wir doch was anderes?

Man kann auch die zu sortierenden Elemente in der Datei,
gepointert via File-Poitioning, indizieren.
Die Sortierung selbst würde ich aber immer im RAM machen.

Man braucht dann erst zum Schluß, falls das Ergebnis wieder in
einer Dateilanden soll, alles der Reihe nach auslesen.
Aber die reine Sortierung soll im RAM laufen.

Sozusagen, perlish ausgedrückt, werden die Daten ge-Tie-t.
Trifft aber auch nicht ganz, wasich meine, denn bei Tie
ist dieKopplungIMHO zu fest. Ich meine eher sowas wie
Indizierung.


> 
> Erst dann, wenn du dich in den Daten hin und her bewegen musst,
> musst du sie in den RAM laden.

Mussich dann nicht mal, wenn ich es somache,wie ich meinte.
Aber umdie Daten zu erkennen muss ich siewenigstens einmal lesen,
oder wenigstens das, was die Ordnung erkennen lässt (evtl. Dateininterne
Ordnung, FixedLengthRecords oder CRLF oder was was ich).
Wenn ich das gelesen habe, kann ich im RAM sortieren.


Ich denke, wir diskutieren mit zu wenig konkreten Fakten
und deswegen wird es schwammig,weiljeder das diskutiert, was er
an konkretem voraussetzt, daß der andere es gemeint haben könnte.

Die Aufgabenstellung wurdemir aber nicht genau genug vorgegeben,
so daß wir beide uns da auf Glatteis bewegen.

 
[...]
> Oder du machst die Verbindung auch im Programmcode, dann musst du
> aber Multi-Threading programmieren, vorallem in C ist das Käse.
[...]

Naja, geht schon.
Da gibt'sschlimmeres, wie zum Beipiel eine solide Stringbearbeitung
neuprogrammieren zu müssen, weil man die sinnvollen Libs nicht
zur Verfügung hat.

Threds-Zeugs geht noch so. Dalohnt sich der Tippaufwand wenigstens ;-)


Aber in OCaml ist das selbstverständlich wesentlich einfacher :)

(Wenn ich da nicht irgendwas verpasst habe, sieht's bei Perl da richtig mau aus.)


Gruß,
   Oliver