Coders Chit-Chat

Quote:

Originally Posted by ლʕಠᴥಠʔლ @Snow Also auch Tutorials z.B. zu Quicksort oder LLRBBST?

Quicksort könnte man sicherlich machen, überhaupt sind Sortieralgorithmen ja wichtig :O

Was soll LLRBBST heißen? Habe dazu nur einen Eintrag in Google gefunden und der führt zu einer Implementierung eines Rot/Schwarz-Baumes. Das kenne ich aber höchstens als R(ed)B(lack)B(inary)S(earch)T(ree), wofür steht das LL?

Left Leaning.

Wurde 2008 von Robert Sedgewick erfunden /gefunden.
Selbe asymptotische Komplexität wie ein normaler Red-Black, nur gefühlte tausend mal einfacher zu implementieren.

Quote:

Originally Posted by ლʕಠᴥಠʔლ Left Leaning. Wurde 2008 von Robert Sedgewick erfunden /gefunden. Selbe asymptotische Komplexität wie ein normaler Red-Black, nur gefühlte tausend mal einfacher zu implementieren.

Danke, hab gerade noch mal in meine alten Vorlesungsfolien geguckt, da ist das tatsächlich nur auf 3 Folien angerissen, hätte ich es gebraucht, hätte ich mich nicht daran erinnert :(

Werde ich gleich mal implementieren und in meinen magischen Ordner packen.

Quote:

Originally Posted by .StarSplash Quicksort könnte man sicherlich machen, überhaupt sind Sortieralgorithmen ja wichtig :O

Wieso sind die für den gemeinen (Hobby-)Programmierer wichtig? Ich komme mit Arrays.sort() recht weit.

Wichtig im Sinne von: wichtig, wenn man Algorithmen behandelt.

Für jemandem, dem völlig am Hintern vorbei geht, was in seinem Code passiert und was eventuell besser laufen könnte, für den ist das natürlich nicht sonderlich wichtig und wohl auch nicht interessant. Wenn man sich aber ein gewisses algorithmisches Grundverständnis aneignen will, kommt man um Sortieralgorithmen nicht herum. Es geht ja auch nicht darum, dass du dir jeden Sortieralgorithmus selbst neu implementierst, damit verschlimmbesserst du höchstwahrscheinlich eine Menge.

Die Wichtigkeit von Algorithmen und ADT, auch wenn es bei vielen nur das Verständnis ist, ist wirklich sehr wertvoll. Ich habe mit 12 angefangen zu "programmieren". Jetzt bin ich 20 und studiere und Algo/ADT war echt eins der Module wo ich am meisten und die wertvollsten Sachen gelernt hab bisher finde ich, obwohl ich sagen muss, das 1 Semester dafür lange nicht ausreicht.

Mitwirken an nen Tutorial dazu würde ich mich auch bereit erklären, auch wenn ich nicht ganz soviel Zeit habe.

Quote:

Wieso sind die für den gemeinen (Hobby-)Programmierer wichtig? Ich komme mit Arrays.sort() recht weit.

Auf den Sortieralgorithmus selbst kommt es nicht an, du solltest weiterhin array.sort verwenden (da es sich dabei meist um ein recht kompliziertes gemischtes verhalten z.b. eine Kombination aus quick und Heapsort handelt).
Worauf es ankommt ist das Verständnis für asymptotische effizienz (sowohl in Laufzeit als auch in Speicher) und als Beispiel dafür eignen sich Sortieralgorithmen extrem gut. Da diese recht leicht zu verstehen sind, und dennoch alle Fälle abdecken, z.B. Bubble sort mit der Komplexität n^2, Mergesort mit n*logn, allerdings nicht inplace, Heapsort n*logn inplace, dafür nicht stabil, quicksort worst case in n^2 und average in n*logn, inplace, nicht stabil, dafür geringeren konstanten aufwand als heapsort.

Auch etwas schönes zu dem Thema, viele Leute denken wenn sie große Mengen an Daten Verarbeiten wollen brauchen sie einen Schnelleren PC, schnelleren Compiler, schneller Sprache (erste Reaktion ist meistens "ich brauche C") aber zunächst sollte man sich über seinen Algorithmus Gedanken machen, so kann ein PC A der 10x schneller ist als der PC B bei einem Algorithmus mit einer Laufzeitkomplexität von n^2 nur n+1 Daten verarbeiten in der selben Zeit in der PC B n Daten verarbeitet.

Im Klartext heißt das, hast du einen PC mit Java und sortierst eine Liste mit 100 Eintragen via Bubble sort und benötigst dafür s Sekunden, so bekommt ein schnellerer PC mit C, der um einen Faktor 10 schneller ist (das ist ne ganze Menge) nur eine Liste von 101 Eintragen in der Selben zeit s hin.

Und daher ist solches Wissen auch als "normale" Entwickler recht wichtig, zum einen weil es mir auf den sack geht wenn ich irgendwo lese: Das ist zu langsam. Dann nehm halt C (weil das einfach zu meist nicht wirklich stimmt), zum anderen weil man damit unabhängig von Programmiersprache, PC, OS, Wetter, und was weiß ich nicht noch allem die Geschwindigkeit (und den Speicherverbrauch) eines Algorithmuses analysieren und Bewerten kann

Quote:

Die Wichtigkeit von Algorithmen und ADT, auch wenn es bei vielen nur das Verständnis ist, ist wirklich sehr wertvoll. Ich habe mit 12 angefangen zu "programmieren". Jetzt bin ich 20 und studiere und Algo/ADT war echt eins der Module wo ich am meisten und die wertvollsten Sachen gelernt hab bisher finde ich, obwohl ich sagen muss, das 1 Semester dafür lange nicht ausreicht.

Also ich hätte an meiner Uni einfach Mathe Nebenfach mit Optimierung 1 und 2 nehmen können, und im Master kann man sich ja auch nochmal spezialisieren





PS: Auch ein sehr wichtiges Thema finde ich Verifikation (Hoare Kalkül) auch wenn die Anwendung sehr lutschen kann ist das meiner Meinung nach auch etwas was jeder Entwickler zumindest mal gehört haben sollte

PPS: Auf Youtube und Itunes U gibt es sogar die Vollständige Vorlesung Algorithmen 1 vom KIT, für jeden der sich dafür interessiert (keine Ahnung wie gut diese VL ist, ich war nie beim KIT)

Quote:

Originally Posted by .StarSplash Wichtig im Sinne von: wichtig, wenn man Algorithmen behandelt. Für jemandem, dem völlig am Hintern vorbei geht, was in seinem Code passiert und was eventuell besser laufen könnte, für den ist das natürlich nicht sonderlich wichtig und wohl auch nicht interessant. Wenn man sich aber ein gewisses algorithmisches Grundverständnis aneignen will, kommt man um Sortieralgorithmen nicht herum. Es geht ja auch nicht darum, dass du dir jeden Sortieralgorithmus selbst neu implementierst, damit verschlimmbesserst du höchstwahrscheinlich eine Menge.

Er hat aber durchaus Recht damit, dass es für viele Gebiete der Programmierung mittlerweile einfach irrelevant ist, es einem also am Hintern vorbei gehen darf, wie die Sachen intern ablaufen (ich wiederhole explizit nicht das "was besser laufen könnte", weil das impliziert, dass es ohne dieses Wissen schlechter läuft und das trifft nicht notwendigerweise zu).
Die Standardbibliotheken sind voll mit fertigen, effizienten Algorithmen und Datenstrukturen. Zwar kann es sinnvoll sein, die wichtigsten Randinfos zu diesen im Kopf zu haben (wann macht ein Hash-Set Sinn, welches Sortierverfahren nehme ich, wenn ich parallelisieren möchte usw.), aber selbst das ist schon in einigen Bereichen unwichtig geworden, weil die Unterschiede für das angestrebte Ziel einfach nicht von Relevanz sind oder diese Auswahl bereits von der Laufzeitumgebung getroffen wird.

Versteh mich nicht falsch, ich bin selbst ein Befürworter davon, dass man wissen sollte (eigentlich vielmehr wissen wollen sollte), was unter der Haube abläuft, aber gerade der markierte Satz vermittelt den Eindruck, man wäre ein schlechter Programmierer, nur weil man das nicht weiß, selbst wenn man in seinem Anwendungsfall ein gutes Recht hat, solche Dinge zu vernachlässigen. Und das ist nichts weiter als elitäres Gehabe.

Gutgut, ich hätte mich vielleicht differenzierter ausdrücken sollen/können/müssen.

Mit "was in seinem Code passiert" war nicht unbedingt gemeint dass man den Algorithmus vom Arrays.sort kennen oder gar können muss, auch wenn das natürlich ein nobles Ziel wäre, stattdessen wollte ich damit eher auf die Laufzeit anspielen, deshalb auch "was eventuell besser laufen könnte". Ich meine eben, dass ein guter Programmierer die Qualität seines Codes abschätzen können sollte, und da ist neben der Lesbarkeit/Verständlichkeit für andere die Laufzeit ein entscheidendes Kriterium.

Für eine Laufzeitabschätzung braucht man eben etwas algorithmisches Denken und um sich das anzueignen kommt man an Sortier- und Suchalgorithmen kaum vorbei, das sind schließlich wohl die, die sich vom naiven Ansatz bis zur optimalen Lösung am besten veranschaulichen lassen und die den größten "Aha"-Effekt erzielen.

Natürlich gilt es das auch in Relation zur Erfahrung des Programmierers zu setzen, wer sich das erste mal an einer komplexeren Aufgabe versucht, dem kann schlecht vorgeworfen werden, dass er nicht sofort versucht sie optimal zu lösen. Wer aber nach 10 Jahren Programmierens noch nie etwas vom worst-case gehört hat, bei dem würde ich mir ernsthaft Gedanken machen. Und ich glaube nicht, dass das elitäres Gehabe ist :o

Quote:

Mit "was in seinem Code passiert" war nicht unbedingt gemeint dass man den Algorithmus vom Arrays.sort kennen oder gar können muss, auch wenn das natürlich ein nobles Ziel wäre, stattdessen wollte ich damit eher auf die Laufzeit anspielen, deshalb auch "was eventuell besser laufen könnte". Ich meine eben, dass ein guter Programmierer die Qualität seines Codes abschätzen können sollte, und da ist neben der Lesbarkeit/Verständlichkeit für andere die Laufzeit ein entscheidendes Kriterium.

Das habe ich schon verstanden, mein Post zielte aber darauf ab, dass auch diese Art Laufzeitbewertung in manchen Bereichen zunehmend in den Hintergrund rückt. Wenn ich eine Webanwendung schreibe, wird der Flaschenhals bei der Anbindung oder bei der Datenbank liegen, selten aber in der effizienten Gestaltung einer for-Schleife. Mit der wachsenden Anzahl von Frameworks wird zudem immer mehr kritische Logik in die Hände von großen Unternehmen und/oder Communities gegeben, die den Code entsprechend qualitativ gestalten, sodass davon immer weniger in der Verantwortung des geneigten Hobbyentwicklers verweilt.

Dennoch:

Quote:

Für eine Laufzeitabschätzung braucht man eben etwas algorithmisches Denken und um sich das anzueignen kommt man an Sortier- und Suchalgorithmen kaum vorbei, das sind schließlich wohl die, die sich vom naiven Ansatz bis zur optimalen Lösung am besten veranschaulichen lassen und die den größten "Aha"-Effekt erzielen.

Genau daran zweifle ich ehrlich gesagt. Grundlegende Dinge wie "Anstatt fünfmal diese große Funktion aufzurufen, weil ich an fünf Stellen ihren Rückgabewert brauche, könnte ich das Ergebnis nach dem ersten Aufruf auch einfach in einer Variablen speichern" sollten auch ohne tiefgreifendes theoretisches Wissen jedem ersichtlich sein. Und ich behaupte mal ganz frech, dass solche trivialen Abwägungen den Großteil ausmachen.
Mit gesundem Menschenverstand kommt man in vielen Dingen schon recht weit, dafür brauche ich nicht 3 Semester Algorithmen und Datenstrukturen gelernt zu haben.

Ich musste bei noch keinem meiner privaten Projekte das asymptotische Laufzeitverhalten überprüfen, um effizienten (oder sagen wir zumindest nicht-ineffizienten) Code zu schreiben.

Ich brauche mal eine Alternative zu system("pause").
Meine Konsolenanwendungen schließen sich im Debugger sonst immer, ich möchte aber den Output noch sehen.

Quote:

Originally Posted by Hype Ich brauche mal eine Alternative zu system("pause"). Meine Konsolenanwendungen schließen sich im Debugger sonst immer, ich möchte aber den Output noch sehen.

cin.get(); aus der std namespace müsste funktionieren (ich gehe davon aus dass du c++ meinst)

Quote:

Originally Posted by MrSm!th Ich musste bei noch keinem meiner privaten Projekte das asymptotische Laufzeitverhalten überprüfen, um effizienten (oder sagen wir zumindest nicht-ineffizienten) Code zu schreiben.

Ich schon.

Beispiel:
Es ging dabei um mehrere asynchrone Streams, aus denen ich jeweils parallel und effizient Infos ziehen muss und per WebSockets entsprechend verteile.
Hab einfach die benötigten Zugriffszeiten je nach Konvergenz numerisch bestimmt.
Also nichts weltbewegendes, fande ich aber interessant :P.


Wird sich natürlich zukünftig ändern, die Daten werden immer mehr und es wird immer mehr zusammen vernetzt.

Na ja, ich finde es ja im Allgemeinen auch nicht doof. Aber ich denke trotzdem, dass es für den Hobby-Programmierer spannendere Themen gibt ...

Quote:

Originally Posted by warfley Im Klartext heißt das, hast du einen PC mit Java und sortierst eine Liste mit 100 Eintragen via Bubble sort und benötigst dafür s Sekunden, so bekommt ein schnellerer PC mit C, der um einen Faktor 10 schneller ist (das ist ne ganze Menge) nur eine Liste von 101 Eintragen in der Selben zeit s hin.

Nicht eher sqrt(10) * 100 = ca. 330?

Quote:

Originally Posted by warfley Dann nehm halt C (weil das einfach zu meist nicht wirklich stimmt), zum anderen weil man damit unabhängig von Programmiersprache, PC, OS, Wetter, und was weiß ich nicht noch allem die Geschwindigkeit (und den Speicherverbrauch) eines Algorithmuses analysieren und Bewerten kann

Minus Konstanten und Cache Effizienz.

Quote:

Originally Posted by warfley PS: Auch ein sehr wichtiges Thema finde ich Verifikation (Hoare Kalkül) auch wenn die Anwendung sehr lutschen kann ist das meiner Meinung nach auch etwas was jeder Entwickler zumindest mal gehört haben sollte

Hast du das jemals in der Praxis benötigt? :confused:

Quote:

Originally Posted by algernong Nicht eher sqrt(10) * 100 = ca. 330?

nope Log(10) + 100 = 101 (zumindest laut der VL)

Quote:

Originally Posted by algernong Hast du das jemals in der Praxis benötigt? :confused:

Tatsache, ich habe es nie erwartet aber als ich bei einem Fehler am verzweifeln war habe ich mit Hoare tatsächlich den Fehler gefunden