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

Mo Jan 8 17:10:58 CET 2007

On Sun, Jan 07, 2007 at 09:41:15PM +0100, Volker Grabsch wrote:
> On Sun, Jan 07, 2007 at 11:30:00AM +0100, Oliver Bandel wrote:
[...]
> > > Was ist denn das? Die Administration darf doch nicht zur Archillesverse
> > > der Entwicker werden. Ihr Job ist doch das genaue Gegenteil: Die
> > > Entwickler zu entlasten, sodass sie ihre Arbeit ungestört und
> > > reibungslos erledigen können.
> > 
> > Sind halt Windows-Admins und verhalten sich demnach Erwartungsgemäß. :->
> > 
> > Die Unix-Admins sind da ganz fit.
> 
> Arroganz und Boshaftigkeit unterstellt man doch normalerweise den
> Unix-Admins, oder?  ;-)
> 

Daß sie fit sind heisst ja nicht, daß sie nicht auch arrogant oder böshaft
sein können. ;-)
Ich sage aber nicht, daß sie es seien.

[...]
> > > > Ich weiss ja nicht, was für Code Du produziert hast.
> > > > Wichtig beim Programmieren ist, daß man potentielle
> > > > Fehlerfälle alle abfragt/abfängt, oder dies zumindest
> > > > vor hat. Wenn man was übersieht, ist das eben Pech.
> > > 
> > > Nein, das Problem war genau andersherum: Es gab zu viel von solchem
> > > Code. Sinnlose Abfragen von NULL und sonstawas. Und warum? Weil wir
> > > (2-Mann-Team, ich mit einem Freund) ständig Pointer benutzt haben,
> > > als wären wir in C.
> > 
> > Ich rede ja auch von dem, was ICH habe sehen dürfen in Code von anderen
> > Leuten, und was ich da grauselig fand.
> 
> Wieder ein Missverständnis. Ich dachte, dich würde auch interessieren,
> was *ich* für Code prozuziert habe. ("Ich weiss ja nicht, was für Code
> Du produziert hast.")

Ist ja auch mal interesant zu lesen, was Du produziert hast, klar.
Aber ich hatte den Eindruck, daß Du meine Äußerungen direkt auf
Deinen Code bezogst; ich meinte aber den Krams, den ich von anderen
Leuten vorfand. Deinen Code habe ich noch nicht gesehen, kann
also nichts dazu sagen und muss mich quasiauf das verlassen, was
Du mir mitteilst. Konkret äußern kann ich mich zu Deinem Code
erst nach Sichtkontakt. ;-)  (Begegnung der dritten Art;-))

> 
> > Die ganze Diskussion bringt schon seit langem nix mehr.
> > Wir haben den Punkt,wowir aufhören sollten, bereits lange überschritten.
> > Ausserdem mag ich gerne selber knobeln, statt vorgefertigte Lösungen
> > miranzuschauen;
> 
> Cool. Dann war die Idee meines Rätsels vielleicht gar nicht so verkehrt.
> 

Stimmt schon. :)
Aber Rätsel aus der Luft heraus (oder dem hohlen Bauch)
ohne konkrete Anwendungfinde ich weniger spannend.
Das habe ich in Kindestagen gern gemocht, doch irgendwann
habe ich gemerkt, daß ich es spannender finde, wenn ich
damit dieWelt, oder wenigstens eine Firma, oder wenigstens
den Tag retten kann ;-)

Eine konkrete Anwendung wäre da also als Motivation ganz hilfreich
(oder gute Bezahlung :)).

> > > Also probier ich mal was: Ich gebe
> > > dir ein Rätsel auf, und wenn du das gelöst hast, hast du auch
> > > verstanden, was ich meine.
> > 
> > Ich gebe Dir ein Rätsel auf:
> > 
> >   Wie kann man es schaffen, daß jemand Anderes Interesse an einem Rätsel hat,
> >   das einen selbst sehr interessiert hat, und von dem man möchte,
> >   daß der Andere sich auch dafür interessiert und es be-rätselt?
> 
> Für mich war das nie ein Rätsel, sondern eine Selbstverständlichkeit.
> 
> Du behauptest, man müsse eine komplexe Datenstruktur (in irgendeiner
> Form) komplett im RAM haben.

Nachdem ich diese Mailvon Dir nun gelesen habe, weiss ich was Du eigentlich
meinst und stelle fest, daß das, was Du dabehauptest,daßich es behaupten
würde, nicht stimmt.
Endlich weissich, was Du dachtest, daßich es denke.

Wieder mal aneinander vorbei geredet.

> Selbst dann, wenn man sie nur ausbauen
> und der Reihe nach ablaufen will. Das stimmt einfach nicht.

Das habe ich auch nie behauptet.
Wieder: Missverständnis.

> Und es
> steckt nichtmal irgendein abgefahrener total komplizierer Trick
> dahinter.

Eben.

> 
> Wenn dich das Thema nicht interessiert, ist das deine Sache. Aber dann
> behaupte bitte nicht konsequent das Gegenteil und missachte meine
> Erklärungsversuche.

Ich behaupte nicht das gegenteil und missachte Deine Erklärungsversuche,
sondern ich habe offenbar nicht verstanden, was Du mirunbedingt erklären
wolltest,sonst hätte ich gemerkt, daßich das schon weiss und Diur da
garnicht wiederspreche sondern zustimme!

> 
> > > Nochmal zusammengefasst:
> > > * billiger 1-Pass-Compiler
> > > * Laufzeit:       O(N)
> > > * Speicherbedarf: O(T)
> > > 
> > > Ich hoffe, das Rätsel ist inhaltlich klar. Du kannst jederzeit fragen.
> > [...]
> > 
> > Wozu soll ich das wissen?
> 
> Weil dort eine fundamentale Erkenntnis hintersteckt, was eine Datenstruktur
> ist und was nicht. Hier konkret: Ein Parsebaum ist nicht zwangsläufig
> etwas, das im RAM liegt, oder das überhaupt zu einem gegebenen Zeitpunkt
> vollständig vorliegen muss.

Es liegt üblicherweiseim RAM, wenn man es als Parsebaum auch konstruiert.
Und es ist auch sinnvoll, es im RAM statt aufPlatte auszuführen, wegen der
Bearbeitungsgeschwindigkeit.

> 
> Lazy Evaluation ist vielleicht ein Stichwort, aber es funktioniert z.B.
> beim Parsen auch mit ganz normalen C-Boardmitteln. Flex und Bison
> demonstrieren das eigentlich ganz gut.

Aha, eben an dieser Stelle habe ich gemerktr, worauf Du hinaus willst.
Ja, man kann auch die Sachen einfach abarbeiten, statt erst einen
Parsebaum aufzubauen und den dann nochmal durchzugehen.
Das war übrigens, alsich mich das erste malmitlex/yacc beschäftigt hatte,
auch mein erster Ansatz.

Ich finde es aber wesentlich flexibler, einen Parsebaum aufzubauen und aus
der erzeugten Datenstruktur möglicherweise mehrere Ausgangsformate zu generieren,
falls es sich um Dokumentengeneratoren handelt, bzw.mehrere Prozessor-Maschinencodes,
falls es ein Compiler ist.
Für nen Interpreter würde ja gut ausreichen, wenn man eine direkte Bearbeitung hat.

Es gibt eben dieLeute,die die aten quasi abknabbern aus dem Inputstream,
und andere Leute, die lieber Datenstrukturen aufbauen.
Ich mag beide Ansätze, aber bevorzuge wegen Flexibilität der Softwarelösung,
eher den Aufbau interner Datenstrukturen.
Aber das tue ich nicht immer. Ist nur eine leichte Neigung.

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.

Aber falls es auch Sinn macht, den Sort selbst als Parseproblem zu sehen,
dann kannst Du mir das mal erläutern, denn diese Sichtweise wäre mir
tatsächlich neu.

> 
> > > Ich würde dir die Antwort auf das Rätsel gern verraten und erklären, aber
> > > das versuche ich ja schon die ganze Zeit. Ich bin offensichtlich nicht
> > > dazu in der Lage.
> > 
> > Und warum bist Du dazu nicht in der Lage?
> > Woran scheitert es?
> 
> Das wusste ich bisher auch nicht. Momentan denke ich aber, es scheitert
> am mangelnden Interesse des Lesers.
> 

In dem Falle, wie bisher wieder anienannder vorbeigeredet wurde,
musste sich beimir jaDesinteresse einstellen. ;-)

Irgendwie haben wir beide eine ausgesprochene Neigung,uns
gegenseitig misszuverstehen, was? Das kenne ich in Diskussionen
mit Dir garnicht anders. ;-)
Aber vielleicht kriegen wir das ja noch irgendwie mal geregelt.

> > > Du wirst mit einer tiefen und meines Erachtens nach wichtigen Einsicht
> > > belohnt.
> > 
> > Möglicherweise.
> > Vielleichtist es auch nichts neues, aber eröffnet eine andere Sichtweise auf
> > etwas bekanntes.
> 
> Sorum ist es besser formuliert, ja.
> 

Das war's dann aber diesmal nicht.

> Oder noch genauer gesagt, es zerstört eine falsche Sichtweise auf etwas
> Bekanntes. Falsche Vorstellungen von abstrakten Gebilden sind sehr
> gefährlich. Sie verleiten dazu, Dinge und Eigenschaften hinein zu
> interpretieren, die gar nicht da sind.
> 
> Mit den Worten von Tom DeMarco: "Nicht das, was wir *nicht* wissen,
> bringt uns zu Fall ... sondern das, was wir fälschlicherweise zu
> wissen glauben."
> (aus: "Der Termin")

Aus dem Gedächtnis zitiert (möglicherweise slightly different):

  "It's our light, not our darkness, that we fear."
                                        (N. Mandela)

> 
> Ich persönlich finde es sehr wichtig, falschen Anschauungen entgegen
> zu wirken. Deshalb habe ich mir damals wie heute diese ganze Mühe
> gemacht. YMMV.

Frei nach einem ähnlichen Zen-Spruch:

   Wer weiss ob es richtig oder falsch ist? ;-)

Gruß,
   Oliver