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

Rocco Rutte pdmef at cs.tu-berlin.de
Mo Jan 8 18:01:44 CET 2007


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.

   bye, Rocco
-- 
:wq!



Mehr Informationen über die Mailingliste linux-l