Beste Sprache um Algorithmen zu lernen

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.

Erhard Henkes

Klar geht alles irgendwie. Ich würde zu C raten, der Sprache für Betriebssysteme. Da findet man ausreichend Material und solide Bücher.

Erhard Henkes schrieb:

Klar geht alles irgendwie. Ich würde zu C raten, der Sprache für Betriebssysteme. Da findet man ausreichend Material und solide Bücher.

Und? Du übernimmst den Code ja nicht 1:1 aus dem Buch. Wenn da was in C erklärt ist, funktioniert es auch in C++.
Es braucht nur einen einmaligen Aufwand, die Entwicklungsumgebung passend einzurichten.

Shade Of Mine

Java ist aus den Gründen die volkard genannt hat am besten geeignet um Algorithmen zu lernen.

Python wäre eine alternative weil die Sprache sehr schön und praktiscg ist - aber es gibt sehr wenig Beispielcode.

C bzw. C++ wäre interessant wenn man mikro optimierungen machen will.

Alles in allem gewinnt hier denke ich Java um längen.

Um Algorithmen zu machen braucht man gute Container. Java Collections sind so gut wie unbrauchbar, da die Generics viel zu viele Einschränkungen haben und Int-Arrays Workarounds brauchen und und und.

C# ist ok und C++ ist ok, aber Java geht nicht.

um Algorithmen zu studieren, dürfte es jede Turing-vollständige Beschreibungsmethode tun, auch Pseudo-Code oder Python.

Will man die Implementation von Algorithmen studieren, ist es natürlich ein Unterschied, ob man dazu eine objektorientierte oder funktionale Sprache, ob man Caml, Assembler oder Fortran nimmt.

großbuchstaben schrieb:

um Algorithmen zu studieren, dürfte es jede Turing-vollständige Beschreibungsmethode tun, auch Pseudo-Code oder Python.

Turing-vollständig setzt eine formale Spezifikation voraus, was Pseudo-Code nicht erfüllt.

Turing-vollständig setzt unendlichen Speicher voraus. Und jetzt?

Erhard Henkes

breitengrad schrieb:

Um Algorithmen zu machen braucht man gute Container. ...

Das Argument ist nicht von der Hand zu weisen. C bietet das natürlich auch schon, aber in C++ oder C# ist das vlt. bequemer zu handhaben. C, C++, C#, was einem halt am besten für die jeweilige Aufgabe liegt. Wichtig ist, dass man die Sprache beherrscht, damit man Abläufe flink und sicher variieren und debuggen kann.

Um Algorithmen zu lernen braucht man doch keine Container, die sind eher hinderlich. Die Sprache sollte so einfach wie möglich sein, damit man sich ganz auf die Algorithmen konzentrieren kann. Auf keinen Fall braucht man da generalisierte Datentypen wie mit void* in C, Templates in C++ etc.

Später bei einer echten Implementierung sieht das anders aus, obwohl es bei Algos ja eher darum geht den richtigen zu wählen und weniger ob der nun doppelt so schnell in C++ wie in Java läuft, das sind Konstanten im O-Kalkül und die sind eh für die Laufzeit ziemlich irrelevant.

volkard

Erhard Henkes schrieb:

breitengrad schrieb:

Um Algorithmen zu machen braucht man gute Container. ...

Das Argument ist nicht von der Hand zu weisen.

Doch. Selber bauen natürlich. Es ging darum, diese Fähigkeit zu erlernen.
Obs nu Algorithmen
http://www.cplusplus.com/reference/algorithm/make_heap/
oder Datenstrukturen
https://commons.apache.org/proper/commons-collections/javadocs/api-2.1.1/org/apache/commons/collections/BinaryHeap.html
heißt, juckt uns weniger, gell?

AlgoResearch schrieb:

Um Algorithmen zu lernen braucht man doch keine Container, die sind eher hinderlich. Die Sprache sollte so einfach wie möglich sein, damit man sich ganz auf die Algorithmen konzentrieren kann.

Da werd ich ja religiös.
http://www.inf.tu-dresden.de/index.php?node_id=3389&ln=de
http://www.amazon.de/Algorithmen-Datenstrukturen-Thomas-Ottmann/dp/3827410290
Und versuch mal den Dijksta zu implementieren ohne eine PriorityQueue zu benutzen. (Oder ein Primzahlensieb ohne Array.)

Für den Dijkstra kann ich zum Lernen ganz normale Ints nehmen und ein Array würde ich nun nicht gerade einen Container nennen, so wie er hier kommuniziert wurde. Ein Array ist einfach ein zusammenhängender Speicherbereich und kein spezieller Container für mich.

volkard

AlgoResearch schrieb:

Für den Dijkstra kann ich zum Lernen ganz normale Ints nehmen

Ach, findMin in O(n). Das wird lahmer UND umständlicher zum Proggern.

Es geht hier nicht um Geschwindigkeit, es darum einen Algo zu lernen und das geht mit Ints und Arrays wunderbar. Warum willst du hier was anderes verkaufen?

Die Queue hat man bei dem Thema auch schon vorher gecodet gehabt und kann sie einsetzen und auch da brauchte ich keine STL-Container. Int, Zeiger und Speicher mehr brauche ich nicht um einen Algo zu lernen, so einfach ist das. Wenn ich einen andere einfacherer Datenstruktur dafür brauche, dann habe ich die doch eh schon vorher implementiert. Ich starte doch bei dem Thema nicht mit Graphen, sondern mit Stack, Heap, LinkedList etc.

Ist dir dies alles nicht bewusst?