Beste Sprache um Algorithmen zu lernen

Ich interessiere mich für Informatik und möchte nun die verschiedestesn Algorithmen und auch DesignPattern ausprobieren. Zu welcher Sprache würdet ihr mir raten? Von welcher Sprache werde ich da am wenigsten aufgehalten?

volkard

Nur "Algorithmen", ohne daß sie wirklich eingesetzt werden? Dann nimm Java, da hast Du viele Freunde.

Wieso sollte ich sie dann nicht auch einsetzen? Laut Benchmarkseiten wie diese hier http://benchmarksgame.alioth.debian.org/u64/compare.php?lang=gpp&lang2=java ist Java nicht viel langsamer als C++. Da zählt doch dann mehr die Wahl des richtigen Algos anstelle der Sprache.

Java ist praktisch bei Berechnungen ähnlich schnell wie C++, Performance-Nachteile gibt es aber tatsächlich, was in gewissen Sprachkonzepten von Java begründet ist. So gibt es beispielsweise keine Value-Types, was dazu führt, dass immer wieder obligatorische (und im Prinzip unnötige) Rechenzeit für den Garbage Collector draufgeht.

Wie auch immer: um ein paar Algorithmen auszuprobieren tut es im Prinzip jede Sprache. Python ist z.B. eine nette Wahl, da es reichhaltige, einfach einzubindende Bibliotheken für Numerik gibt. Große Zahlen (> 2^32) sind in Python auch kein Problem, anders als bei Java, wo ein Array beispielsweise nur mit 32-Bit-Integern indiziert werden darf (und es kein unsigned gibt... ).

Hast du das gerallt?

volkard

AlgoResearch schrieb:

Wieso sollte ich sie dann nicht auch einsetzen? Laut Benchmarkseiten wie diese hier http://benchmarksgame.alioth.debian.org/u64/compare.php?lang=gpp&lang2=java ist Java nicht viel langsamer als C++. Da zählt doch dann mehr die Wahl des richtigen Algos anstelle der Sprache.

Wenn Du es eh besser weißt, warum fragst Du überhaupt?

Java deshalb, weil viele Leute ihre Demo-Algos in Java bauen. Kannst also viel abgucken⁽¹⁾. Und nicht zum Einsetzen, weil Java bekanntermaßen nicht für größere Software taugt. Unabhängig von der Geschwindigkeit, die übrigens nach Benchmarks und Behauptungen seit 20 Jahren annähernd so schnell wie C ist und theoretisch und in den nächsten paar Monaten ganz ganz bestimmt auch schneller. Hab keine Zeit für Sprachenstreit, nimm es hin oder laß es.

⁽¹⁾ Wenn ich von tollen Algos und Datenstrukturen lese, so recht frisch aus der Forschung, sagen wir zum Beispiel mal eine calendar queue, dann finde ich oft nur Java-Code dazu. Das wäre mein Hauptargument. Auch zu allen möglichen Patterns liegt Code vor.

AlgoResearch schrieb:

Wieso sollte ich sie dann nicht auch einsetzen? Laut Benchmarkseiten wie diese hier http://benchmarksgame.alioth.debian.org/u64/compare.php?lang=gpp&lang2=java ist Java nicht viel langsamer als C++. Da zählt doch dann mehr die Wahl des richtigen Algos anstelle der Sprache.

Ich glaub, du hast was auf den Augen. C++ ist dort teilweise wesentlich schneller und auch speichersparender.
Für Algorithmen kannst du jede Sprache nehmen, die dir passt.

L. G.,
IBV

Marthog

Haskell. Eingabe reinstecken und eine Ausgabe rausbekommen ist ziemlich einfach darin. Schwierig wird es nur, wenn man komplexe Zustandsuebergaenge wie im GUI, zyklische Abhaengigkeiten oder Echtzeit braucht.

Ansonsten (wenn man was imperatives will) ist die Wahl der Sprache ziemlich egal, wobei ich Python fuer kurze, nicht geschwindigkeitsrelevante Skripte (und das sind Beispielalgorithmen) sehr gut finde, weil man sehr viele hochsprachliche Konstrukte hat und sich deswegen gleich mit dem Kern des Algorithmus beschaeftigen kann. Bei groesseren Aufgaben oder richtigen Programmen, also nicht nur kleinen Hilfsskripten, empfiehlt sich dann aber doch eine typsichere Sprache.

Java schneidet in den Benchmarks uebrigens immer ziemlich gut ab, weil der Garbage Collector bei diesen kurzen, aber viele Schleifen enthaltenden Algorithmen oft kaum zum Einsatz kommt. Bei groesseren Anwendungen erzeugt man aber sehr viele Objekte, die man oft direkt danach wieder wegwirft und muss deswegen ziemlich oft aufraeumen.

Marthog schrieb:

Haskell.

Für klassische Algorithmen denkbar ungeeignet. Arrays mit konstantem Index-Zugriff gibt es nicht (oder sind nur unschön einbaubar). Graphen sind auch eine Herausforderung (siehe z.B. https://www.haskell.org/haskellwiki/The_Monad.Reader/Issue5/Practical_Graph_Handling).

Haskell ist toll, aber um Algorithmen zu lernen würde ich Haskell definitiv nicht empfehlen, da die Lazy Evaluation eine weitere Kompexität hinzufügt.

Gregor

Wenn es darum geht, Algorithmen zu lernen, empfehle ich eine Sprache, die Dir nicht im Weg ist. Wenn also die Herausforderung darin liegt, die Sprache zu verstehen und meinetwegen Compilerfehler zu beheben, die man nicht versteht, dann hat man die falsche Sprache genommen.

Wenn Du eine Sprache sehr gut beherrscht, dann solltest Du die nehmen. Wenn nicht, dann solltest Du eine Sprache wählen, die nicht zu schwer ist. Die Empfehlung von Java ist in diesem Zusammenhang durchaus nachzuvollziehen. Abhängig vom generellen Themengebiet, um das es bei den Algorithmen gehen soll, sind aber auch andere Sprachen sehr geeignet. Wenn es zum Beispiel um numerische Algorithmen geht, spricht nichts gegen Fortran.

Ich empfehle Dir aber auch, Dich mit Sprachen auseinanderzusetzen, die einem mehr Freiheiten lassen (zum Beispiel C++) oder einem exotischen Programmierparadigma folgen (zum Beispiel Haskell oder Prolog). Bestimmte Algorithmen können auch besser in solchen Sprachen formuliert werden.

volkard

Gregor schrieb:

Prolog

Prolog geht kurzgefaßt so: Um die Zahlen von 1 bis 10 auszugeben, definiere ich, daß eine Tolle Zahl eine Zahl ist, die ausgegeben wird und deren Nachfolger eine Tolle Zahl ist. Außerdem definiere ich, daß 11 eine Tolle Zahl ist und lasse dann das Prolog-System beweisen, daß 1 eine Tolle Zahl ist. Schwupps, hat man die Zahlen von 1 bis 10 auf dem Bildschirm.

Ich fürchte, ich würde von Prolog abraten, um Algorithmen zu lernen. Will ich bei Quicksort das erste oder das mittlere Element als Pivot nehmen? Das erste hab ich mit einer Klausel, fürs Mittlere brauche ich fünf mit zwei Rekursionen. Ich fürchte, der Stil würde sich auch versauen und jedes Gefühl dafür, was für den Prozessor leichte und was schwere Arbeit ist.

Gregor

@volkard: Ich denke, es gibt einige Algorithmen, bei denen es recht interessant ist, sie mal in Prolog umzusetzen. Zum Beispiel Breitensuche und Tiefensuche.

Ethon

Java hat den Vorteil einen GC mitzubringen, dh man muss sich nicht den Code mit smart pointern bzw manueller Speicherverwaltung vollbauen.
Simplifiziert das Schreiben von Datenstrukturen zum Lernen durchaus.

volkard schrieb:

Und nicht zum Einsetzen, weil Java bekanntermaßen nicht für größere Software taugt.

Ach Volkard.

Um Algorithmen zu lernen würde ich ganz klar C empfehlen.

Grund:

Wie will man effizient mit Algorithmen umgehen können, wenn man nicht einmal weiß, wie z.B. eine Liste intern unter der Haube arbeitet?
Dafür sind Sprachen mit Zeigerartithmetik sinnvoll, C bietet das, C++ ebenfalls, aber Java bietet dies nicht.

Ethon

Und du meinst dass du in C eine Liste anders implementierst als in Java nur weil du die Knoten per malloc statt per new holst?
Habe auch noch nie Zeigerarithmetik bei einer Listenimplementierung in C++ gebraucht und wüsste auch nichgt wo man die einsetzen könnte.

Ethon schrieb:

Und du meinst dass du in C eine Liste anders implementierst als in Java nur weil du die Knoten per malloc statt per new holst?
Habe auch noch nie Zeigerarithmetik bei einer Listenimplementierung in C++ gebraucht und wüsste auch nichgt wo man die einsetzen könnte.

struct list_node {
  uintptr_t prev_xor_next;
  int data;

  node *next(node *prev) { return (node*)(prev_xor_next^(uintptr_t)prev); }
  node *prev(node *next) { return (node*)(prev_xor_next^(uintptr_t)next); }
}

Ethon

Wer soetwas programmiert der reibt sich auch mit Mayonaise ein und rennt "Ich bin ein Hamburger" schreiend auf der Straße herum.

Nathan

Ethon schrieb:

Wer soetwas programmiert der reibt sich auch mit Mayonaise ein und rennt "Ich bin ein Hamburger" schreiend auf der Straße herum.

Naja, aber sowas ist schon praktisch, geht in Java soweit auch nicht:

struct node
{
    node *next;

    node(const char *str, node *next) noexcept
    :  next(next)
    {
        void* mem = this;
        std::strcpy(static_cast<char*>(mem) + sizeof(node), str);
    }

    const char* get_str() const noexcept
    {
        const void *mem = this;
        return static_cast<const char*>(mem) + sizeof(node);
    }
};
...
auto mem = ::operator new(sizeof(node) + std::strlen(str) + 1);
auto n = ::new(mem) node(str, head_);
head_ = n;

So spart man sich die zweite Allokation für den String.

Ethon

Das sind komplette Mikrooptimierungen mit gewaltigen Nachteilen (eine Hölle zum Debuggen). Wer eine Liste verstehen lernen möchte interessiert sich nicht dafür.
Wenn man in einer Liste Zeiger sparen muss (!) dann nimmt man sowieso kein Java.

Dein Beispiel würde in Java keinen Sinn machen da in Java Strings Referenztypen sind und sowieso vom GC verwaltet werden. Die liegen irgendwo im Stringpool oder Heap und die Nodes würden sowieso keinen Speicher für die Strings anfordern.

Habe soetwas übrigens mal ausprobiert. Zwar nicht mit einer Liste aber mit einer Hashtable "optimiert" für String-Keys. Eine Verbesserung war gerade so messbar, auf jeden Fall nicht signifikant.

Nathan

Ethon schrieb:

Das sind komplette Mikrooptimierungen mit gewaltigen Nachteilen (eine Hölle zum Debuggen).

Naja, so viel Debuggen muss man jetzt bei einer einfach verketteten Liste auch nicht. Und man kann sich auch bequem im Debugger das Ergebnis von get_str() anschauen.

Dein Beispiel würde in Java keinen Sinn machen da in Java Strings Referenztypen sind und sowieso vom GC verwaltet werden. Die liegen irgendwo im Stringpool oder Heap und die Nodes würden sowieso keinen Speicher für die Strings anfordern.

Ah ja, stimmt, da war was in Java.

Habe soetwas übrigens mal ausprobiert. Zwar nicht mit einer Liste aber mit einer Hashtable "optimiert" für String-Keys. Eine Verbesserung war gerade so messbar, auf jeden Fall nicht signifikant.

Bei mir ists auch ein Hashtable. Hab mit dieser Optimierung bei allen englischen Wörtern eine Geschwindigkeitsvorsprung von 10-15ms. Das ist nicht viel, aber gemessen an dem Aufwand den ich hatte das zu schreiben, lass ich die einfach drin.

Die "Beste" Programmiersprache zum Algorithmenlernen gibt es so nicht, mehrere Sprachen/Mathe-Systeme kennen ist nicht verkehrt, da verschiedene Lösungsansätze möglich.
Aktuell: C-Sprachtyp, nicht zuletzt wegen der C-und C++ orientierten Pseudo"Sprachen". (verschachtelte for-schleifen kennen/können ist hilfreich)(c/c++/java/...) egal. Relativ beliebt, auch zum hacken, ist python, viele gute Algos leicht nachvollziehbar.
Ergänzend: Funktionale Programmierung, Haskell oder Lisp. Zwei gute Bücher:
"Land of Lisp" und "The Haskell Road to Logic, Math and Programming". Prolog-Interpreter kannst du damit (Lisp/Haskell) selber schreiben. Für Haskell spricht u.a. Interpreter, eine ausgefeilte Grammatik und Werkzeuge, die nahe an der Mathe-Abstraktion liegen. Hier muß man aber erstmal Kunstgriffe mit Rekursion (und rekursiven Datentypen!) gut verstehen wie auch den Einsatz von Hilfsfunktionen oder Beschleunigervariablen.

Historisch: Fortran/Basic/Assembler - aber auch C -> Aber C hat keinen Interpreter :(.
Viele Klassische Mathe-Algos wurden in Fortran entwickelt, und später nach C übersetzt (f2c-prg/Unix oder so).

Man kann es zuerst mit der Programmiersprache versuchen, die einem am meisten Spaß macht. Und da teilen sich die Geschmäcker in beliebten Flamewars.

Ethon

Nathan schrieb:

Ethon schrieb:

Das sind komplette Mikrooptimierungen mit gewaltigen Nachteilen (eine Hölle zum Debuggen).

Naja, so viel Debuggen muss man jetzt bei einer einfach verketteten Liste auch nicht. Und man kann sich auch bequem im Debugger das Ergebnis von get_str() anschauen.

Ging mir dabei um die XOR-Liste. Ein Debugger zeigt einem schön an was in der Liste drin ist. Das klappt bei der XOR-Liste nicht.
Es geht ja nicht darum die Liste zu debuggen sondern Code, der die Liste verwendet.