Was bringen mir Algorithmen und Datenstrukturen?

Sehr interessant, solche Erzählungen wie deine hier liest man äußert selten. Es sollte viel mehr solche Praxisgeschichten geben, das motiviert unheimlich sich mit der Informatik näher zu beschäftigen. Kann man eigentlich sagen, dass die Wahl der richtigen Algorithmen viel wichtiger als die Performance der Programmiersprache ist?

Durch die Vorlesungsvideos werde ich wohl erst einmal mit Java weiter machen, das geht mir irgendwie um Längen schneller von der Hand. C++ verlieren ich nicht aus den Augen, aber ich will auch mal voran kommen mit den Algos.

Nutzt man eigentlich in der Praxis mehr Libs oder macht man da auch viel selbst? Wenn ja, was macht man selbst und was kommt aus Libs?

Gregor

Logn schrieb:

Kann man eigentlich sagen, dass die Wahl der richtigen Algorithmen viel wichtiger als die Performance der Programmiersprache ist?

Im Prinzip ja, aber...

Letztendlich sind das zwei Aspekte bei der Realisierung einer Lösung für eine Problemstellung, die relativ unabhängig von einander sind. Eigentlich solltest Du immer den "besten Algorithmus" in der "am Besten geeigneten Programmiersprache" realisieren. Wobei es natürlich immer etwas subjektiv und kontextabhängig ist, was das Beste ist. Es spielen meistens verschiedene Kriterien eine Rolle.

Na, ich will Java und C++ lernen, obwohl Java irgendwie ziemlich schnell zu lernen ging. Programmieren will ich allerdings auch mal für Mikrocontroller, weswegen ich mir auch C kurz angeschaut habe. Am meisten habe ich aber vor auch für mobile Geräte was zu machen und da ist Java ja wohl der Platzhirsch.

Wenn man das so sieht brauche ich C++ eigentlich überhaupt nicht. Warum ich damit angefangen habe? Nun, es gilt es die schwierigste und komplizierteste Sprache und das wollte ich mal verifizieren. Im Vergleich zu Java komme ich mit C++ unglaublich langsam zum Ziel, was wahrscheinlich aber auch an meiner C++-Unkenntnis liegt.

Mir wurde ja schon gesagt, dass man nicht viele Sprache nebeneinander lernen soll. Ja mag sein, aber ich will und wollte halt vergleichen. Im Moment denke ich, dass ich mit C und Java schon eine optimale Wahl getroffen habe.

Mechanics

Logn schrieb:

Kann man eigentlich sagen, dass die Wahl der richtigen Algorithmen viel wichtiger als die Performance der Programmiersprache ist?

Grundsätzlich ja. Aber wenn man irgendwann bei ähnlich optimalen Algorithmen angekommen ist, lohnen sich Mikrooptimierungen wieder, da kann man immer noch Faktor 2-3 rausholen. Also, wenn du mit einer naiven Lösung 5 Stunden brauchst, dann braucht man nicht weiterreden. Aber wenn du einen besseren Algo gefunden hast und bei 15 Minuten Laufzeit bist, kann man die 15 Minuten mit C++ vielleicht auf 5 runterdrücken. Und das kann man dann auch dem Kunden gegenüber argumentieren. Was, die Konkurrenten brauchen 15 Minuten? Das müssen ja komplette Vollidioten sein, wir schaffen das in 5. Der Punkt ist vielleicht gar nicht so sehr, dass es auf die 10 Minuten Unterschied ankommen würde, sondern dass die Konkurrenten Idioten sind und man mit denen nicht zusammenarbeiten sollte
Oder es geht irgendwann darum, ob man irgendwas in Echtzeit machen kann, oder ob man dann nach jeder Mausbewegung 2 Sekunden wartet.

Logn schrieb:

Nutzt man eigentlich in der Praxis mehr Libs oder macht man da auch viel selbst? Wenn ja, was macht man selbst und was kommt aus Libs?

Standardsachen wie Quicksort wird wohl kaum jemand selber programmieren, außer als Übung. Für Numerik gibts auch recht gute Bibliotheken. Was wir aber z.B. selber implementiert haben, sind Clustering Algorithmen, viele Algos im 3D Bereich, auch einen eigenen 3D Kernel. Das sind Bereiche, wo es viele neue Ideen in Form von Papers gibt. Aber so ein Paper ist erstmal nichts, was man direkt verwenden könnte. Das sind oft Sachen, die die Autoren auch nur so ein bisschen in Form eines Prototyps ausprobiert haben. Da muss man oft noch viel weiterforschen und rumprobieren, bis man sagen kann, ob man das überhaupt verwenden kann.

Logn schrieb:

Wenn man das so sieht brauche ich C++ eigentlich überhaupt nicht. Warum ich damit angefangen habe? Nun, es gilt es die schwierigste und komplizierteste Sprache und das wollte ich mal verifizieren.

und - stimmt es? Oder sind APL und Forth doch schwieriger? oder TeX?

Logn schrieb:

Ja mag sein, aber ich will und wollte halt vergleichen. Im Moment denke ich, dass ich mit C und Java schon eine optimale Wahl getroffen habe.

mag sein. Erwarte aber vielleicht keinen grenzenlosen Beifall für die Wahl in einem C++ Forum

Logn schrieb:

Nutzt man eigentlich in der Praxis mehr Libs oder macht man da auch viel selbst? Wenn ja, was macht man selbst und was kommt aus Libs?

das kann man so allgemein nicht beantworten. Die Auswahl der in einem Projekt zu verwendenden Libraries hängt von Faktoren ab wie:

Verfügbarkeit (auf der Zielplattform)

Existenz von Bindings zur Zielsprache

Kosten

Lizenzarten (und deren Verträglichkeit innerhalb eines Projektes)

Aktualität und Zukunftssicherheit (hat man beispielsweise die Resourcen, eine womöglich irgendwann nicht mehr gewartete open-source Library selber zu pflegen?)

u.s.w.

Jester

Gregor schrieb:

@Jester: Ok, Komplexitätstheorie insgesamt ist vielleicht zu weit gegriffen. Für die Praxis wird es vermutlich recht wenig bringen, das PCP Theorem oder so im Detail zu kennen. Aber Du kennst doch das Buch "Computers and Intractibility", oder? So etwas, was da gebracht wird, ist glaube ich sehr nützlich. ...nicht nur der hintere Teil.

Ja, das finde ich auch nützlich. Aber schafft man es echt irgendwo (an einer Uni) Informatik zu studieren und an NP-Vollständigkeit und polynomiellen Reduktionen vorbeizukommen? Ich dachte das lernen wirklich alle.

Danach ist allerdings in weiten Teilen fraglich, ob es für die Praxis Sinn ergibt sich da weiter mit zu beschäftigen. Ein großer Teil der Komplexitätstheorie befasst sich mit wesentlich schwierigeren Problemen, die man ohnehin nicht für die Praxis lösen kann (polynomielle Hierarchie zum Beispiel). Da finde ich es für die Praxis sinnvoller Techniken zu erwerben wie man mit schweren Problemen praktisch umgehen kann. Auch dafür gibt es ja einen riesigen Fundus an Techniken. Zum Beispiel generische Methoden wie gemischt ganzzahlige lineare Programmierung, SAT-Formulierungen, etc. Das hat aber mit eigentlicher Komplexitätstheorie nur noch am Rande zu tun. Wird man weniger generisch, landet man schnell beim Entwurf effizienter Algorithmen -- das ist dann aber auch nicht mehr so richtig Komplexitätstheorie.

Gregor

Jester schrieb:

Gregor schrieb:

@Jester: Ok, Komplexitätstheorie insgesamt ist vielleicht zu weit gegriffen. Für die Praxis wird es vermutlich recht wenig bringen, das PCP Theorem oder so im Detail zu kennen. Aber Du kennst doch das Buch "Computers and Intractibility", oder? So etwas, was da gebracht wird, ist glaube ich sehr nützlich. ...nicht nur der hintere Teil.

Ja, das finde ich auch nützlich. Aber schafft man es echt irgendwo (an einer Uni) Informatik zu studieren und an NP-Vollständigkeit und polynomiellen Reduktionen vorbeizukommen? Ich dachte das lernen wirklich alle.

Ich hatte damals im Pflichtptrogramm nur eine Vorlesung im 3. Semester, in der es um "Berechenbarkeit und Komplexität" ging. Wenn ich mir das Skript von damals so angucke, dann ging es zwischen den Seiten 158 und 160 um Komplexitätsklassen, zwischen 160 und 174 um NP-vollständige Probleme. Und das war es dann. Der Großteil des Skripts hat mehr mit Berechenbarkeit zu tun. Man sieht ja an den Seitenzahlen, wie wenig Komplexitätstheorie da letztendlich drin ist.

Im Hauptstudium mussten wir dann 3 von 4 Theorie-Grundlagenvorlesungen hören. In einer davon ging es um "Automaten und Komplexität". Im zugehörigen Skript handelt eins von 10 Kapiteln von Komplexitätstheorie (Etwa 30 von 360 Seiten). Ich persönlich habe diese Vorlesung nichtmal gehört. Was ich an Komplexitätstheorie kennengelernt habe, habe ich mir größtenteils nach dem Studium selbst beigebracht.

Aus meiner Sicht war das bisschen Komplexitätstheorie, das ich im Studium hatte, zumindest wesentlich zu wenig, um ein Gefühl dafür zu kriegen, wann ein Problem NP-vollständig sein könnte. Wir haben damals vielleicht um die 5 NP-vollständige Problemstellungen kennengelernt und das ist IMHO einfach zu wenig. Ich weiß nicht, ob wir überhaupt einmal in einer Übungsaufgabe zeigen mussten, dass ein Problem NP-vollständig ist. Viele Übungsaufgaben kann es zu diesem Thema zumindest nicht gegeben haben. Auf gar keinen Fall wurden uns damals Wege gezeigt, wie man mit NP-vollständigen Problemstellungen umgehen könnte, wenn man auf sie trifft. Ich glaube zum Beispiel, dass ich im Studium nicht einmal das Wort "Approximationsalgorithmen" gehört habe.

Um die Ehre der Webentwickler mal zu retten:
Auch wenn man eine Webanwendung macht kann es ganz nützlich sein etwas über Komplexität zu wissen. Beispielsweise wünschen sich Designer oft eine bestmögliche Platzausnutzung und wollen beispielsweise http://packery.metafizzy.co/ benutzen. In diesem Falle hat der Autor konkret das Problem (bin-packing) benannt. Jemand der sich mit Komplexität auskennt würde nun erkennen: Ok, wir können Packery benutzen, aber nur, wenn wir nicht zu viele Rechtecke haben, weil es sonst zu langsam wird. Antwort vom Designer: Ok, Geschwindigkeit ist mir für den User an dieser Stelle wichtiger...dann lassen wir das mit Packery gleich bleiben.

Das ist übrigens ein Beispiel, welches ich in etwa so erlebt habe.

Es mag ein paar Lichter unter den Webentwickler geben, aber in der Regel arbeiten da Leute die eben kaum von irgendwas eine Ahnung haben, außer den hundert Frameworks und siebentausend Buzzwords in diesem Bereich.