Adventskalender 20. Dezember 2024 - NQueens

[mn77de]

Einleitung
Heute kommt das Türchen mit der vmtl. längsten Vorbereitungszeit
Und gleich vorweg ... mich faszinieren Programmiersprachen und Algorithmen.

Eigentlich ging es am 19.7.2009 los, als auf Heise folgender Artikel erschien: 26-Damen-Problem gelöst
Und nein, das Damenproblem hat nichts mit Frauen zu tun

Es geht hier um eine schachmathematische Problemstellung:

Wie viele Möglichkeiten gibt es, um 'n' Damen auf einem Schachfeld der Größe 'n x n' so zu positionieren, dass sie einander weder diagonal, noch senkrecht, noch waagrecht schlagen können.

Weitere Infos kann man auf Wikipedia nachlesen: Wikipedia - Damenproblem

Damals fand ich die Problemstellung eine gute Fingerübung, weshalb ich spontan einen möglichst effizienten Algorithmus entwickelte.
Als weiteren Schritt fing ich an, diesen Quellcode in verschiedene Sprachen zu übersetzen. Welche Sprache ist wohl die schnellste?

Es ist einem meist nicht bewusst, aber man hat mit Debian heutzutage wirklich viele, qualitative und teils sehr mächtige Programmiersprachen sofort zur Hand!

Mein Projekt ist nun quasi ein Benchmark für diese Programmiersprachen. Einerseits lässt sich die Geschwindigkeit testen, andererseits kann auch die Übersichtlichkeit und Einfachheit verglichen werden.

Klarstellung
Es mag sicherlich noch einen effizienteren Lösungsansatz geben, als den von mir gewählten. Gerade mit nebenläufigen Prozessen und der Verteilung auf mehrere CPU's, sollte da heutzutage noch einiges möglich sein.
Teils lässt sich auch der Quellcode noch optimieren, ich bin natürlich nicht in allen Sprachen so richtig fit.
Ebenso sind meine Geschwindigkeitstests nur relativ zu werten und wurden nicht unter "Laborbedingungen" durchgeführt.
Auch fehlen noch einige Sprachen, wie z.B. Lisp.

Es gibt noch bissl zu tun

Trotzdem bietet mein Projekt die Möglichkeit für ein paar Vergleiche.

Geschwindigkeit
Hier nun die bei mir und mit einem i7-11700 ermittelten Ergebnisse:

Alle Werte sind in Sekunden. Eine Sprache schied aus dem Test aus, sobald sie für die Aufgabe mehr als 20 Sekunden benötigte.

EDIT: Aufgrund von Eurem Feedback wurden mittlerweile Optimierungen vorgenommen. Die Grafik wird noch aktualisiert.

And the winner is: Go, C, Vala !!!
Dicht gefolgt von: Ocaml, Kotlin, Groovy, C++ und Java.

Da Groovy hier interpretiert verwendet wird, ist dies definitiv eine ordentliche Leistung. Auch Julia ist als interpretierte Sprache richtig flott. Wobei z.B. Lua eine ultrakurze Startgeschwindigkeit hat.
Faszinierend finde ich, dass die Java-VM echt flott ist!

Das Schlusslicht bildet die Bash, welche für solche Aufgaben aber auch nicht wirklich gemacht ist.

Übersichtlichkeit / Einfachheit
Eine gute Lesbarkeit ist bei einer Programmiersprache generell sehr sinnvoll. Ebenso ist ein kompakter Quellcode von Vorteil, da er Schreibarbeit erspart.


Natürlich lassen sich die einzelnen Programme kompakter schreiben, aber hier geht es um die übliche und gut lesbare Schreibweise.
Interessant ist auch, ob eine Programmiersprache sehr viele Sonderzeichen und Klammern benötigt. So etwas kann die Lesbarkeit erschweren, wie z.B. bei Perl.
Leerzeichen, Zeilenumbrüche und Tabs werden bei der Prozentzahl übrigens ignoriert.

Die einzelnen Programme können hier betrachtet werden: nqueens.mn77.de
Das gesamte Projekt liegt auf GitLab und ist relativ übersichtlich strukturiert: https://gitlab.com/MN77/nqueens

Mit folgendem Befehl kann es übrigens auf den Rechner geladen werden:

Code: Alles auswählen

git clone https://gitlab.com/MN77/nqueens

Schlusswort
Das Ziel des heutigen Türchens ist es, auf die vielen Programmiersprachen in Debian hinzuweisen.
Jede der heute genannten Sprachen hat ihre Berechtigung und es gibt ganz spezifische Anwendungsfälle dafür.
Das Damenproblem ist natürlich nicht für alle der optimale Anwendungsfall.

Was sind Eure Lieblings-Programmiersprachen?
Ist eine Sprache dabei, die ihr noch nicht kennt?
Welche Sprachen sollten noch unbedingt aufgenommen werden?
Gibt es Optimierungen, die ihr vornehmen würdet?

Und ja, meine eigene Programmiersprache "JayMo" hat sich hier rein gemogelt, obwohl sie nicht im Debian-Repo verfügbar ist.

Ich wünsche Euch viel Spaß beim Stöbern, entdecken, ausprobieren und programmieren.

[Liffi]

Sehr witziges Projekt muss ich sagen. Mich überrascht vermutlich das Ergebnis von C am meisten. Da würde mich interessieren, ob da jemand mit ein bisschen C-Wissen das noch verbessern kann.
Auch bei Rust und C++ würde ich noch Potential erwarten.

[uname]

Auch von mir Danke für das Thema. Ich habe mir mal die JavaScript-Version angeschaut und einen Zähler für die rekursive Funktion solve eingebaut. Benutzt du überall Rekursion? Ist die Anzahl der Funktionsaufrufe der rekursiven Funktion bei allen Programmiersprachen gleich?

Code: Alles auswählen

N=1: Anzahl der Lösungen: 1, Anzahl der Funktionsaufrufe: 2
N=2: Anzahl der Lösungen: 0, Anzahl der Funktionsaufrufe: 3
N=3: Anzahl der Lösungen: 0, Anzahl der Funktionsaufrufe: 6
N=4: Anzahl der Lösungen: 2, Anzahl der Funktionsaufrufe: 17
N=5: Anzahl der Lösungen: 10, Anzahl der Funktionsaufrufe: 54
N=6: Anzahl der Lösungen: 4, Anzahl der Funktionsaufrufe: 153
N=7: Anzahl der Lösungen: 40, Anzahl der Funktionsaufrufe: 552
N=8: Anzahl der Lösungen: 92, Anzahl der Funktionsaufrufe: 2057
N=9: Anzahl der Lösungen: 352, Anzahl der Funktionsaufrufe: 8394
N=10: Anzahl der Lösungen: 724, Anzahl der Funktionsaufrufe: 35539
N=11: Anzahl der Lösungen: 2680, Anzahl der Funktionsaufrufe: 166926
N=12: Anzahl der Lösungen: 14200, Anzahl der Funktionsaufrufe: 856189

[mn77de]

Benutzt du überall Rekursion? Ist die Anzahl der Funktionsaufrufe der rekursiven Funktion bei allen Programmiersprachen gleich?

Zum besseren Vergleich habe ich versucht, den Code für alle Sprachen möglichst ähnlich zu halten. Somit sollte die Anzahl der Funktionsaufrufe überall gleich sein, ja.
Lass mich gerne wissen, wenn du eine schnellere Möglichkeit findest.

[uname]

Ich habe mal mit Hilfe einer KI versucht beim Damenproblem die genannte Koroutine von Niklaus Wirth zu verwenden. Bein meinem Test mit JavaScript von 1 bis 13 jedoch ohne Berechnung der zusätzlichen Schleifenzähler war die Version mit der Koroutine 10 Mal langsamer (extra Zeitausgabe vorher und nachher eingebaut). Aber das lag vielleicht auch nur an JavaScript oder der KI. Vielleicht hat die alternative Lösung aber weniger Speicher benötigt. Das habe ich nicht geprüft.

[wanne]

Ein wenig verwundert bin ich von C, aber sicherlich gibt es hier noch Optimierungsmöglichkeiten.

Naja, das gcc ohne optimierung zu verwenden finde ich schon massiv unfair. Das speichert da literally jede Variable nach jeder Zeile in den RAM um sie dann wieder da auszulesen. Der Cache fängt da einiges ab aber im Zweifelsfall sind das halt zig CPU-Zyklen pro Zeile warteizeit auf den RAM. Für ein Benchmark gehört da IMHO mindestens ein -O3 hin. Zumal go über doppelt so lange braucht, wenn man Optimierung abschaltet, die da halt per default an und nicht aus ist.
-O3 -funroll-all-loops ist bei mir für die 15 Damen 3s schneller als die go Variante 7.469s vs. 10.129s mit Optimierung. clang ist nur mit -O3 schneller als die go Variante 7.629s.
Daneben ist bools zu verwenden halt extrem ineffizient. Auf der anderen Seite ist Bitbangig halt ein viel komplexeres unterfangen und dann kein vergleichbarer Algorithmus mehr. Das ist leider halt immer das Problem bei Programmierspracheinvergleichen.
Die was Programmiersprachen unterschiedlich schnell macht ist ja die übliche Nutzung und ein bisschen Compilerunterschiede. Wenn man einem gleich funktionierenden Compiler den gleichen Algorithmus in unterschiedlichen Sprachen übergibt sollte ja der selbe assembler raus kommen. Aber die übliche Nutzung ist halt sehr geschmacksspezifisch. Daneben ist die Idee der bash halt, dass man andere tools aufruft und niemals selber rechnet. Kann ja nicht mal floats. In sofern ist ja jede deiner Lösungen eine Bash-Lösung.

[mn77de]

Für ein Benchmark gehört da IMHO mindestens ein -O3 hin.

Danke für den Hinweis. Entsprechend habe ich nun für C, C++ und Vala jeweils ein "-Ofast" verwendet, was die Ausführungsgeschwindigkeit doch extrem beschleunigt. Ein "-Ofast" war auch schneller als "-O3 -funroll-all-loops", auch wenn die Kompilierung nun angeblich nicht mehr Standard-Konform ist.

Entsprechend sind nun Go, C und Vala führend!
Wobei Go bei mir immer noch am schnellsten ist, wenn auch nur ganz minimal.

Vielleicht gibt es bei anderen Sprachen auch noch solche Optimierungen ... ?

[hikaru]

Auch Fortran sollte mit Optimierung wieder auf C-Level sein.

[mn77de]

Auch Fortran sollte mit Optimierung wieder auf C-Level sein.

Wuhuuu!
Fortran hat mit "-Ofast" gerade deutlich alle anderen, inkl. Go und C, überholt.

Okay, weiter so ... wo gibt es noch Optimierungsmöglichkeiten?