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

[Oliver Bandel]

On Sun, Jan 07, 2007 at 12:54:56AM +0100, Volker Grabsch wrote:
> On Sat, Jan 06, 2007 at 02:58:32PM +0100, Oliver Bandel wrote:
> > On Sat, Jan 06, 2007 at 01:21:31AM +0100, Volker Grabsch wrote:
> > > > > Was sind die genauen Anforderungen?
> > > > 
> > > > Developing, while taregt moves ;-)
> > > 
> > > Dann sollte Informationsbeschaffung an erster Stelle stehen, nicht
> > > die Algorithmen.
> > 
> > Wat'n Spruch....tse.
> 
> Ja, hast schon recht, die rein spekulativen Teil-Threads lassen wir mal
> lieber beiseite.
> 
> > > > > 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?
> > > 
> > > Ich will der Firma, in der du arbeitest, natürlich nichts unterstellen,
> > > aber deiner Beschreibung zufolge "riecht" es danach, als ob du zu
> > > strenge Vorgaben bekommst, die dich daran hindern, eine *wirklich* gute
> > > Lösung zu erarbeiten.
> > 
> > Nein, nicht wirklich.
> [...]
> > Naja, nee, ist schon ganz cool da. Aber das Chaos (eher zu wenig
> > Vorgaben) kann aber auch manchmal richtig nerven. Eben keine Infos...
> > Naja, ich trags mittlerweile mit Fassung. :)
> 
> Achso, also das andere Extrem. Mehr eine Hippie-Bude als ein
> Militärgelände.  ;-)
> 

Nun, Hippiebude würden diesicherlich nicht auf sich sitzen lassen,
aber "man Dilbert" könnte passen ;-)



> > Was nerv, sind die Windows-PCs für's Einloggen auf der Maschine.
> > Letztens haben mir die dummen Admins von der Windows-Front einfach meinen
> > Account gesperrt. Der Abend war dann nicht mehr sehr arbeitsreich und nächsten Tag
> > bin ich dann auch erst 10h30 da aufgetaucht.
> > 
> > Aber wenn das Netz lahm ist oder derWindows-PC herum zickt oder so,
> > dann kriege ich da doch noch nen Schub Aggris;-)
> > Man tippt seinen Code, und plötzlich passiert garnix mehr, oder so.
> > Oder putty spinnt. (Oder die Admins schalten sich einfach drauf und deswegen
> > spinnt der Rechner?!)
> 
> 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.


[...]
> Und ja, ich bin auch Admin (z.B. für Hostingkunden, aber auch damals zu
> Schulzeiten im Schulnetzwerk), es macht Spaß, und ich habe nie auch nur
> das Bedürfnis verspürt, solche Aktionen zu starten. Wenn ich doch mal
> jemanden gestört habe, dem ich eigentlich helfen wollte, habe ich mich
> dafür entschuldigt. Bin ich abnormal?
> 
> (Meine Theorie: Ich verdränge die Angst, nicht das Admin-Gen zu besitzen.)

Hmhhh.... lassDich doch mal sreenen ;-)

Aber es könnte sein, daß das dann auf Deiner gesundeheutskarte eingetragen wird...
...und dann denken alle, die das wissen: "Der kann das ab, lasst uns den mal
ärgern..." und dann reichen die 42 Leben nicht mehr, weil die dann in zwei
Monaten aufgebraucht sind ;-)



> 
> > [...]
> > > > > 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.
> > > 
> > > Ich bin es *gerade* in der Uni gewohnt, Dinge ohne Angst hinterfragen zu
> > > können. Selbst in der Arbeit kann ich meine Auftraggeber mit
> > > "weiterführenden Gedanken" nerven. Und wenn sie nein sagen, dann erfahre
> > > ich in der Regel auch den Grund, und bin wieder etwas schlauer.
> > 
> > Klar.
> > Aber es kann eben auch ein Nein dabei heraus kommen.
> 
> Was soll das?
> 
> Ich: "Und wenn sie nein sagen, dann ..."
> Du:  "Aber es kann eben auch ein Nein dabei heraus kommen."

Wenn Du den Tonfall hättest hören/lesen können, mit demes gedacht wurde,
würdest Du verstehen, daß das sinnvoll ist, was da stand.

=> Falsches Medium.


> 
> So kann man nicht miteinander reden. Ich mache mir die Mühe, deine Texte
> aufmerksam zu lesen, und dasselbe erwarte ich auch von dir.

Ählisch gesacht, habe ich manches Deiner anderen Mail teils überflogen.
Sorry, ich weiss, das ist nicht freundlich.

Vielleicht sollte ich mir angewöhnen, so wie Dues machst, manchmal
Tage oder wochenlang eine Antwort aufzuschieben, dafür aber dann
die Tuhe gehabt zu haben, alles in Gänze zu lesen.
Allerdings würde da meine Motivation fürdie Sache evtl. von anderem
Tagesgeschehen aufgegessen werden und so spät eintrudelnde Antworten
sind dann irgendwie auch out-of-Kontext, weil der im Memory bereits
verblasst ist.

Also tschuldigung.

[...]
> Und deiner DSL nachher einer schicke Optik zu verpassen, weil nicht
> jeder die vielen Klammern der S-Expressions mag, ist viel angenehmer
> als gleich einen Parser, Interpreter, etc. zu schreiben. Die Grenze
> zwischen Unterprogrammen und Interpreter verschwindet. Schon genial,
> so eine programmierbare Programmiersprache.
> 
> Aus diesem Aspekt heraus ist das jedenfalls hochinteressant.
> 
> > > Und der
> > > Interpreter deiner DSL, worin schreibst du den?
> > 
> > Soll ich antworten, oder weisst Du die Antwort bereits? ;-)
> 
> Das hast du aus dem Zusammenhang gerissen. Es ging um die Frage,
> welche Programmiersprachen du verwendest, und du hast u.A. die
> Antwort "DSL" gegeben. Die rhetorische Frage sollte dir eigentlich
> klar machen, dass du die Antwort damit nur verschoben hast, weil
> du immer noch einen Interpreter für die DSL schreiben musst.

Und ich dachte, Du wolltest wirklich wissen,
welche Spracheich zum Implementieren einer DSL ich
nehmen würde. Und ich nahm an, daß Du das ohnehin weisst.

Woher soll ich ahnen,daß eseine rhetorische Frage war?
Tonfall?
=> falsches Medium.

> 
> > > > Und bei einem schlechten
> > > > Programmierer ist es auch egal,ob er 20 Jahre Erfahrung hat, denn
> > > > er wird immer Grütze schreiben!
> > > 
> > > Bin ich deshalb ein schlechter Programmierer, weil ich's nicht auf
> > > Anhieb richtig[tm] gemacht habe? Weil ich erst nach ein paar Wochen
> > > etwas über RAII gelesen habe?
> > 
> > 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.

 
[...]
> Die Antwort in C war dann: Kein "new", stattdessen lokale

Seit wann kennt C "new"?

> Objekt-Variablen, RAII-Prinzip beachten, Referenzen und Objektkopien
> statt Pointer. Schon verschwindet ne Menge Boilerplate-Code. Das
> ganze ist bugfreier, und viel, viel weniger potentielle Segfaults.
> Bis auf eine einzige Ausnahme kein einziges "delete". Das heißt,
> keine Memory-Leaks, und trotzdem ohne Garbage-Collector. Das ist
> etwas, das C++ einzigartig macht. Völlig ungewohnt aus Python,
> Java, C, ...

Hmhhh, bin kein C++ Spezi. Klingt aber nett/interessant, was Du schreibst.



> 
> Seit ich die Konzepte und Prinzipien von C++ besser verstanden habe,
> mag ich die Sprache sogar.


Kann sein, daßmir da das Verständnis noch fehlt ;-)


> 
> > Aber es gibt Leute, die einfachgrundsätzlich zu
> > faul sind, Fehlerbedingungen abzufragen oder
> > nicht gewillt sind ihre Programmiertechniken anzupassen.
> 
> Nun, das ist eine andere Baustelle. Gibt's natürlich auch, und dieses
> Phänomen ist unabhängig von der Programmiersprache, da stimme ich zu.
> :-)

Ja, und deswegen plädiere ich fürProgrammiersprachen, die einem
diese Art von Pfuscherei wenigstens schwer machen, bzw. einem
dabei helfen, eigene Fehler frühzeitig ausfindig zumachen.

> 
> > ...es gibt eben Leute, die arbeiten gerne mit dem Debugger.
> > ...und es gibt andere, die brauchen keinen Debugger.
> > 
> > So einfach ist das.
> 
> Es gab ein paar Unsauberkeiten, die wir allein mit Debug-Messages
> nicht finden konnten. Sie resultierten aus einem teilweise falschen
> Verständnis von C++, ohne Debugger hätten wir das nicht gefunden.

Naja gut, manchmal mag man den schon brauchen; wenn man an Code anderer
Leute arbeitet,die Unsinn verzapft haben ;-)

> 
> Aber ansonsten: Ja, ich stimme zu, wenn man ordentlich entwickelt,
> braucht man den Debugger kaum. Man debuggt gleich beim Schreiben,
> und zahlt dort einen viel niedrigeren Preis als später in der
> Fehlersuche. Dieses Prinzip namens "Inkrementelle Programmierung"
> ist aber uralt, und wird *eigentlich* jedem Neuling mit als erstes
> beigebracht.

Ich dachte das ist erst, seit man den alten Wein (alter Wein, schöner,
alter Jahrgang,lecker) in neue Schläuche füllte (und Zucker und/oder Glykolalc
dazu gab) und es XTreme-programming nannte, erst bekannt geworden?!



> 
> > > Natürlich gilt das nur für sequentielle Zugriffe, aber genau das
> > > meinte ich: Wenn du 100 MB chaotischer Daten sortierst, mach es im
> > > RAM.
> > 
> > Ja, gerne. Aber nur, wenn genug RAM drin ist.
> > Sonst swapt dieMaschine und man hat nix gewonnen.
> 
> Ich schrieb mein Beispiel unter der Annahme, dass es mehrere GB RAM
> gibt, wie du selbst geschrieben hast. Auch hier: Bitte nicht meine
> Aussagen aus dem Kontext reißen. Das bringt doch nichts.

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; ausser, ich frage nach einem Dingens, dann habe ichaber auch
danach gefragt. Die Frage war mit dem Hinweis auf das Mergesort
allerdings bereits beantwortet.
Was danach kam war teils sehr interessant, aber the urge of interest of knowing
was then slightly gone away.

Ich hätte mirbestimmt schon was feines ausgedacht, wenn die Aufgabe
weiter gegangen wäre. Und wenn wirklich was schwieriges dabei wäre,
wo ich mal jemand hätte fragen müssen, hätteich dann ja fragen können.

Du kamst aber gleich mit weitergehenden Lösungen,
was ja sehr nett ist, allerdings nicht mehr auf mein
brennendes Interesse stiess, da die eigentliche Frage bereits beantwortet
wurde.

Es ist daher keine wirkliche Diskussion mehr, sondern driftet
ins Monologisieren ab. Wäreein Uni-Job mit Vorlesungen nicht was für Dich?
Oder Seminare geben?


[...]
> > > > Wir sind wieder an dem Punkt, wowir wegen anderer Sprachwahl
> > > > aneinander vorbei reden.
> > > 
> > > Ist möglich. Worum es mir ging, war, dass man keine extra
> > > Datenstrukturen im RAM aufbauen braucht, wenn man sie nachher
> > > doch wieder nur abläuft. Dann kann man die Ein- und Ausgabefunktioen
> > > auch direkt verbinden.
> > 
> > Dann hast Du aber trotzdem eine ("extra") Datenstrukturim RAM,
> > nur daß diese etwas anderes repräsentiert: eben die
> > Reihenfolge der Funktionen, die Du ausführen willst.
> 
> ... hmm, das scheitert genauso wie letztes Mal. Ich weiß nicht,
> wie ich das verständlich rüber bringen soll.

Vielleicht willst Du etwas rüber bringen, wasmich *derzeit*
nicht interessiert. Damit will ich nicht sagen, daß ich das
grundsätzlich uninteressant finde. Aber erstens knobele ich selber
gerne und zweitens hatte ich ja auch garnicht danach gefragt.


> 
> Andererseits magst du ja Rätsel.


JAAAAAAAA! :)

Ich mag Rätsel. Aber ich mag nicht grundsätzlich immer und alle Rätsel.
Viele Rätsel finde ich langweilig.
Manche aber nicht. :)



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



[...] 
> Aber der Speicherbedarf des Compilers soll nicht O(N) betragen, sondern
> nur O(T)! Nach deiner Aussage müssen alle Programm-Tokens sowieso
> irgendwie im RAM liegen, d.h. du würdest niemals unter O(N) kommen.
> Ich behaupte jedoch, du kannst den Compiler so schreiben, dass in
> O(T) arbeitet. Dein Programm kann also auch 100x so groß sein. Solange
> er nicht "komplizierter" ist (also tiefer verschachtelte Sprachelemente
> hat), braucht der Compiler genauso wie RAM wie vorher.
[...] 

Ohne näher drauf einzugehen (weil das nicht meiner Fragestellung entspricht),
erinnert mich das, ohne das Detail durchgedacht zu haben, an tail-recursion.
(Constant Stack Space).

Aber das ist ja im Moment nicht meine Baustelle.


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


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


> Aber vielleicht bist du in der Lage, es dir selbst
> zu erschließen.

Möglicherweise.

> Viel Glück dabei!

Danke.

> 
> 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. Vielleichtist es auch völlig neu.
Wer weiss...


> 
> > > > I/O ist langsam.
> > > > Vielleicht meinen wir doch was anderes?
> > > 
> > > Seuqentielles Lesen aus dem Stream ist nicht langsamer. Ständiger
> > > Lese- und Schreibzugriff natürlich schon. Vielleicht meintest du
> > > ja den.
> > 
> > Wenn ich random access brauche und immer wieder
> > rewind()mache und von vorne lese, nützt eine schnelle
> > Leserei nix, wenn ich diePositionen im File,
> > die ich brauche, sowieso kenne.
> 
> Ja, aber wenn du z.B. nur ein paar kBytes zurück-"seekst", brauchst
> du keine Angst vor der Performance zu haben. Dann lieber den einfacheren
> Code mit "seek" schreiben, statt einen künstlichen zweiten Cache zu
> bauen.

Und wenn es nicht nur ein paar kBytes sind?
Wieder: spekulativ.


> 
> > Mehr als diese allgemeine Aussage kann man hier nicht treffen,
> > denn sonst können wir gleich ein Buch schreiben.
> > (Keine schlechte Idee, eigentlich, was? :))
> 
> Ein Buch über KISS, und warum verfrühte Optimierung böse ist,
> mit zahlreichen Beispielen "richtig" <-> "falsch". Das wäre
> lustig, ja.
> 

Daslustigste sind Codebeispiele.
Manche sehen fast aus wie uuencodet files ;-)
Sowas wie versehentlich obfuscated.
Aber manch einer programmiert jaobfuscated,damit sein Job sicher ist.
Kann sich damit aber ins Knie schiessen.


Gruß,
   Oliver