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

[Oliver Bandel]

On Mon, Jan 08, 2007 at 05:01:44PM +0000, Rocco Rutte wrote:
> Hi,
> 
> * Oliver Bandel [07-01-08 17:10:58 +0100] wrote:
> 
> >Ich habe wohl den Sprung vom Sort zum Parsevaum verpasst.
> >Einen Sort habe ich mirbisher nichtals Parsing-Problem betrachtet,
> >sondern eher als nachfolgenden Schritt nach dem Scannen/Parsen,
> >wenn man die Daten aus dem Inputstream extrahiert hat.
> 
> Eben das Extrahieren ist ja schon wieder parsen. Ob man jetzt bei 
> MergeSort nach günstigeren Patterns als 50:50 teilt, oder bei QuickSort 
> mit viel Aufwand nach dem besten Pivot sucht: sobald man aufteilt hat 
> man ja eine Datenstruktur mit den Informationen: Teilstück Nr. Anfang, 
> Ende (was man verarbeiten, speichern, etc. kann).
> 
> Und damit arbeitet dann der Algorithmus. So gesehen, ist QuickSort nur 
> ein Parser, und wenn man das Merge von MergeSort auch als Parsen ansieht 
> (von 2 Datenstrukturen zu nur 1), dann ist das auch nur ein Parser.
> 
[...]

Dann braucht man also DIESE Informationen, also eben Positions-Werte
innerhalb der Files. Und dasmacht IMHO keinen Sinn, diese auch
auf Platte abzulegen. Diesollten (wg. Performance) ins RAM.
Dann ist es dochletztlich das selbe wie ich es mit dem sammeln
der lseek-Positionen bereits erwähnte.
Und dann ist *das* eben die Datenstruktur,auf der man arbeitet,
also einer Abstraktion der Originaldaten.
Letztlich bleibt alles wie es war  ;-)

Gruß,
   Oliver