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

[Volker Grabsch]

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

Beide Strategien haben ihre Vor- und Nachteile.

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

Ja, genau.

Das passiert z.B., wenn die Liste schon sortiert oder entgegengesetzt
sortiert war.

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

Ja, aber die sind eben etwas aufwändiger. Vorallem dann, wenn sortierte
Daten rein kommen. Außerdem weiß ich wiegesagt nicht, wie man die
parallelisiern könnte.

Die sind dann wichtig, wenn in den Daten ständig gesucht wird (dann geht
nämlich Binärsuche), und eher selten etwas eingefügt wird.

Geht es aber nur ums Sortieren, ist Mergesort viel einfacher und
schneller.

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

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.

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

> 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. Warum
quälst du dich mit C rum? Ich meine, mindestens C++ wird doch wohl drin
sein.

Und nein, C++ ist nicht bloß C mit Klassen. Es ist viel mehr, es ist
Ausdrucksstark, und es hat einige einzigartige Konzepte und Prinzipien.
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.

Du kannst es dir vielleicht so vorstellen, als ob ein C-Programmierer
Ocaml-Code schreibt, oder ein Haskell-Programmierer Ocaml-Code schreibt.
Ocaml *kann* imperativen Stil, aber den sollte man sparsam einsetzen.
Genauso *kann* C++ auch mit char* umgehen, man sollte dennoch std::string
nutzen. Und C++ *kann* Strings in Listen aufspalten und wieder
zusammensetzen, aber die API ist darauf ausgerichtet, Strings in einem
anderen Stil zu verarbeiten, nämlich sie wie Ein/Ausgabe-Streams zu
behandeln. Das führt meistens zu viel übersichtlicherem, eleganteren
Code, ist aber C-Programmierer, und ganz besonders für Java/Python/...-
Programmierer (wie mich) total ungewohnt (gewesen :-)).

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.

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

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

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

Lerne, mit Streams umzugehen. Sowohl in C++ als auch in Ocaml.

Merge-Sort arbeitet auf Streams hervorragend. Es gibt nichts an
Merge-Sort, das dich zu Arrays, einfach verketteten Listen, oder
sonstigen Datenstrukturen zwingt.

Selbst du Baumstrukturen im RAM zwingt dich genaugenommen keiner,
du kannst ja die des Dateisystems nehmen.

Wenn du z.B. einen Parser schreibst, der einen Eingabestream in
(verschachtelte) Token zerlegt, dann ruft der Parser bestimmte
Code-Teile auf, jenachdem ob gerade z.B. eine Array-Definition
beginnt, oder eine Zahl kommt. Richtig?

Wenn du nun Funktionen wie "start_array", "end_array", "number"
hast, dann entspricht die Aufruf-Reihenfolge dieser Funktionen
doch genau der Struktur des Programmes.

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.

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)

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

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

Es spricht nichts dagegen kleinere Datenmengen (wenige GB) komplett
im RAM zu sortieren.

Aber gerade Merge-Sort erlaubt dir doch folgendes:

1. in Bruchstücke aufteilen und sortieren
-----------------------------------------

* lese aus der Eingabedatei ca. 1GB an Datensätzen in den RAM
* sortiere sie im RAM. (z.B. per Mergesort oder Quicksort)
* speichere sie als:
    part0
* lese nun weitere Datensätze ein, sortiere sie, speichere sie in:
    part1
* und so weiter, bis die Eingabedatei zuende ist:
    part2
    ...
    part99

2. Bruchteile mergen
--------------------

* öffene die Dateien part0,...,part99
* lese jeweils einen Datensatz
* speichere sie in einem 100-elementigen array dat[]
* suche das Minimum dieser 100 Datensätze
    (z.B. ist der von part55 der kleinste, also dat[55])
* Schreibe diesen Datensatz in die Ausgabedatei
* lese neuen Datensartz von part55
* schreiben ihn in dat[55]
* suche Minimum,
    ...

Das wäre ein Merge-Sort, aber fällt dir was auf? Keine verketteten
Listen, sondern höchstens ein kleines Array fester Größe. Wie kommt
das? Du mergst doch schließlich riesige Listen.

Ganz einfach: Du hast riesige Listen, gehst sie aber nur Element für
Element durch. Du benutzt also die Datei-Streams direkt als Listen.


Übrigens, wenn du Probleme mit großen Dateien vermeiden willst, dann
kannst du diesen Teil auch sauber auslagern. Du könntest Schritt 1
aufspalten in:

1a. Brückstücke erzeugen
------------------------

* lese ca. 1GB an Datensätzen aus großer Eingabedatei
* speichere sie in part0
* lese weiteres 1GB an Datensätzen aus großer Eingabedatei
* speichere sie in part1
u.s.w.

(hier brauchst du nur jeweil einen Datensatz im RAM zu haben,
verbrauchst also kaum Resourcen, und nur hier brauchst du dich
mit großen Dateien rumärgern)


1b. Bruchstücke sortieren
-------------------------

* mache Mergesort oder Quicksort getrennt für part1, ...


2. Bruchteile mergen
--------------------

* ...


Okay, vielleicht hat nun Teil 2 noch Probleme mit großen Dateien,
aber die kannst du umgehen, indem das Ding einfach nach stdout
schreibt, und du die Ausgabe umleitest. Dann hat wenn überhaupt
nur noch die Shell ein Problem. Aber ich glaube nicht, dass das
LargeFile-Problem auftritt, wenn man nur sequentiell in eine große
Datei schreibt.

Ach ja, und wo du das parallelisieren kannst, ist auch klar, oder?
Du kannst part0 bis part99 auf verschiedenen Rechnern sortieren
lassen, bzw. bei einem Multiprozessorsystem von verschiedenen
Prozessen gleichzeitig.

Außerdem kannst du Teil 2 Varrieren, indem du z.B. erst 10 Prozesse
hast, die folgendes Mergen:

    part0, ..., part9    ->  part0-9
    part10, ..., part19  ->  part10-19
    ...
    part90, ..., part99  ->  part90-99

Auch das ist super parallelisierbar, und jeder einzelne Prozess
braucht ja nur 10 Datensätze im RAM halten zu können. Zum Schluss
mergst du noch

    part0-9, part10-19, ...  ->  ausgabedatei

Wieviele Prozesse du gleichzeitig startest, musst du selbst ausknobeln,
halte die Programme also flexibel. Und wieviel du auf einmal mergst
(2 wie im Lehrbuch, oder 10 wie hier im Beispiel), musst du ebenfalls
selbst rauskriegen.

Übrigens müssen die Zwischendateien part0, ..., part99 sowie
part0-9, ..., part90-99 keine Dateien sein. Unter Unix kannst du auch
FIFOs dafür nehmen.

Du hättest dann 3 eigenständige Werkzeuge (split, sort, merge), die
du via Shell-Script miteinander verbindest.

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


Viele Grüße,

    Volker

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