Beste Sprache um Algorithmen zu lernen

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.

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.