Lösung für den FizzBuzz Test

Im Internet bin ich auf einen Programmiertest gestoßen, der häufig auch in Einstellungstests verwendet wird, um die Fähigkeiten eines Bewerbers besser einschätzen zu können. Das Problem ist auf https://rosettacode.org/wiki/FizzBuzz beschrieben und es geht darum, Zahlen von 1 bis 100 auszugeben und zusätzlich bei bestimmten Zahlen noch eine Zusatz namens „Fizz“ und „Buzz“. Soweit der Test als solcher. Wie sieht darauf jetzt die korrekte Antwort aus?

Wer sich für ganz besonders schlau hält nutzt die Copy&Paste Funktion um die Lösung von https://rosettacode.org/wiki/FizzBuzz#Python:_Simple unter die Aufgabe anzufügen. Der Sourcecode ist ausführbar und löst exakt das beschriebene Problem. Nur leider ist das nicht die wirkliche Lösung. Weil der Prüfer ja nicht wissen will wie der Python-Code aussieht, sondern der Prüfer will sehen wie man den Code selber schreibt. Insofern ist die obige richtige Antwort leider trotzdem falsch. Aber ein selbst zusammengezimmerte Python Code ist ebenfalls falsch, weil wie gesagt, es beim FuzzBuzz Test ja nicht um Python oder um Informatik geht sondern um Persönlichkeitsdiagnostik. Die richtige Antwort auf den FuzzBuzz zu finden ist nicht ganz so simpel wie es den Anschein hat, bisher ist mir noch keine gute Lösung eingefallen, aber ich glaube dass ein Schulsystem was IQ-Tests durchführt um zwischen guten und schlechten Schülern zu unterscheiden per se der falsche Weg ist, wenn man an Fortschritt interessiert ist. Besser sind Anreizstrukturen die nicht ausgrenzen, nur weil man etwas nicht wusste.

Sourcecode Convolutional Neural Network mit Caffe

# mynet classify 
# Sourcecode from "Trollheaven Magazin September 2015", page 15
import os 
import sys 
import numpy as np 
import matplotlib.pyplot as plt 
caffe_root = '/home/hp/temp/caffe/caffe/' 
sys.path.insert(0, caffe_root + 'python') 
import caffe 

MODEL_FILE = '/home/hp/temp/caffe/mynet/lenet.prototxt' 
PRETRAINED = '/home/hp/temp/caffe/mynet/lenet_iter_1000.caffemodel' 
# IMAGE_FILE = '/home/hp/temp/caffe/mynet/bilder/9b.png' 
IMAGE_FILE = '/tmp/bild.png' 

net = caffe.Classifier(MODEL_FILE, PRETRAINED) 
input_image = caffe.io.load_image(IMAGE_FILE) 

prediction = net.predict([input_image]) 
print 'predicted class:', prediction[0].argmax() 

Ein Lob auf Python

Python darf sich zurecht als die Königin der Programmiersprachen nennen, in extrem kurzer Zeit gelingt es, in dieser Sprache einen kleinen Racetrack zu programmieren bei dem ein Auto seine Runden dreht. Inklusive einer realistischen Physik-Engine und einem grafischen Menü zur Steuerung. Mit keiner anderen Programmiersprache gelangt man nach so wenig Iterationsschritten zu einem ablauffähigen Programm. Zugegeben, das Ergebnis besteht aus einer simplen Klötzchengrafik, und eine Maussteuerung gibt es auch. Nur, man muss das zu investierten Zeit sehen, also wielange man sich durch Edit-Compile-Run Zyklen quält und was man als Gegenwert auf dem Bildschirm sieht. Hätte man die gleiche Simulation in C, Java oder sonstigen Programmiersprache erstellt hätte es Wochen gebraucht für das selbe Ergebnis.

Python mit C interagieren lassen

Dass Python die Sprache der Wahl ist um Prototypen zu erstellen braucht nicht mehr groß erläutert zu werden. Wann immer man es einsetzen kann ist es gegenüber jeder anderen Programmiersprache im Vorteil. Es gibt jedoch innerhalb des Python Universums eine Spielart die als sehr anspruchsvoll gilt und zwar die Verwendung von Code der nicht in Python geschrieben wurde. Der durchschnittliche Python Anwender hat damit weniger zu kämpfen, weil er vorhandene Librarys wie pygame einfach aus dem PyPi Repository installiert und dann benutzt. Aber was ist, wenn solche Librarys noch nicht erstellt sind?

Nach meiner Recherche gibt es aktuell zwei Optionen: ctypes und SWIG. Das wichtigste ist wohl wenn man sich zunächst um eine gute Dokumentation kümmert. Online habe ich nichts brauchbares gefunden, aber dafür findet man bei Google Books mehrere gute Dokumentationen dazu. Ich habe es zwar selbst noch nicht ausprobiert aber wenn ich es richtig verstanden habe, schreibt man eine Python Library und in dieser arbeitet man dann mit SWIG und ctypes, um dort dann C-Funktionen einzubinden wie z.B: SDL oder glibc.

Schaut man sich die existierenden Python Librarys sind (die extrem zahlreich sind) so ist es wohl grundsätzlich möglich, für jede C-Bibliothek ein Interface nach Python zu programmieren. Wie gesagt, der richtige Umgang mit SWIG dürfte innerhalb von Python bereits zu den Advanced Themen gehören, aber offenbar ist es möglich diesen Weg zu bestreiten. Der Vorteil ist, dass mit einem Schlag man darüber Zugriff erhält auf sämtliche Betriebssystemroutinen die noch dazu in der maixmalen Geschwindigkeit ausgeführt werden. Ich glaube, da liegt die eigentliche Stärke von Python. Objektorientierte Scriptsprachen gibt es neben Python noch viele andere wie z.B. Lua, Ruby, Javascript usw. Sie alle haben jedoch das Problem, dass sie nur eine eingeschränkte Funktion verfügen. Für Ruby gibt es beispielsweise keine gute Game-Engine, insofern ist das Interesse der Anwender an Ruby eher gering. Nicht so bei Python. Nach meiner Recherche wurde fast alles was sinnvoll ist, als Import-Library für diese Programmiersprache bereitgestellt und dadurch ist der mögliche Anwendungsrahmen sehr groß.

Man muss unterscheiden zwischen der Python Sprachspezifikation einerseits (also wie man konkret Programme schreibt) und den Tools mit denen man externe C-Biblitoheken anbindet, also ctypes und SWIG. Letzteres ist die eigentliche Stärke von Python und der Hauptgrund dafür warum es sich als Nummer 1 Scripting-Sprache etabliert hat.

Die meisten High-Level-Funktionen von Python wie die Plotting-Funktion, die Grafikausgabe in 3D, Physics-Engine, Abspielen von Mp3 usw. sind realisiert worden, indem externe bereits vorhandene C-Bibliotheken in Python aufrufbar sind. Die wenigsten Bereiche von Python wurden in Python selbst geschrieben, weil dafür die Sprache gar nichts schnell genug wäre.

Vom Ansatz her ist Python und C etwas sehr unterschiedliches. Das heißt, es gibt keinerlei Gemeinsamkeiten. Weder von der Syntax, noch vom Compilieren her und auch nicht was die Zielgruppe angeht. Die eigentliche Herausforderung ist nicht so sehr eine Scriptsprache zu erstellen sondern der Clou ist in SWIG und ctypes zu suchen. Ein derartiges Konzept ist bei anderen Programmiersprachen wie Java und C++ nicht vorhanden. Dort ist man dichter am ursprünglichen C dran und es gibt weniger Notwendigkeit einen Wrapper zu schreiben. Bei Java hat man im Grunde viele C-Bibliotheken nachprogrammiert in Java selber. Das heißt, es gibt einmal OpenGL vom Betriebssystem und dann gibt es dasselbe nochmal von Oracle/SUN. Bei Python hingegen war der Ansatz so, dass man eine möglichst große Distanz zu C aufgebaut hat. Man hat gleich von Anfang gesagt, dass man selber keine Compilersprache sein will und auch keine eigenen Bibliotheken haben möchte. Daraus ergibt sich automatisch die Notwendigkeit einen leistungsfähigen automatischen Wrapper namens SWIG verwenden zu müssen. Ohne diesen wäre Python komplett nutzlos. Ohne das mächtige import Kommando mit dem die meisten Python Programme eingeleitet werden, kann man in der Sprache selber fast gar nichts machen.

Warum erwähne ich das? Der Hauptgrund dürfte sein, dass Python als Programmiersprache sehr faszienierend ist. Mit 300 Lines of Code kann man bereits ein komplettes Computerspiel bauen, das geht mit keiner anderen Programmiersprache. Auf der anderen Seite ist auch C eine sehr faszinierende Sprache. Weil man dort hocheffizienten Code schreiben kann und sehr viele Frames per Second erzeugen kann. Auch das geht mit keiner anderen Programmiersprache. Ich habe einige Alternativen zu C ausprobiert, wie Java, C++, Go und Fortran. Aber keine erreicht die Performance von C.

Ich glaube, das eigentliche Problem besteht darin, dass es da draußen zu Hater von C und zu viele Hater von Python. Also Leute die sich abfällig äußern über C und es als veraltet bezeichnen, genauso wie es Leute gibt, die Python als Anfängersprache verunglimpfen. Ich glaube jedoch, dass jede Sprache für sich extrem mächtig ist in ihrer Nische und dort den Platz #1 innehat. Und das sich viele Probleme innerhalb der Informatik lösen ließen, indem man entweder auf C oder auf Python wechselt.

CTYPES
Eine minimal-Anleitung für ctypes gibt es auf http://stackoverflow.com/questions/5081875/ctypes-beginner Dort muss man zuerst ein C-Programm erstellen, dass dann mit speziellen Parametern (fpic shared) compilieren und kann dann über ctypes aus Python darauf zugreifen. Der Ablauf ist nicht ganz so einfach wie es Python Programmierer gewohnt sind, und manchmal gibt es noch Besonderheiten zu beachten, wenn man jedoch komplexere C-Bibliotheken erstellt ist das ein guter Einstieg. Ich will damit andeuten, dass mit ctypes und SWIG zwei sehr potente Tools zur Verfügung stehen um Python und C miteinander zu kombinieren und genau das wird sehr häufig eingesetzt. Ein wenig zu kritisieren ist jedoch die Dokumentation dazu. Ein Buch was sich speziell dieser Frage annimmt gibt es nicht, und die Online-Hilfe ist mehr als dürftig. Das Konzept als solches ist jedoch zukunftsfähig, man müsste es nur einer breiteren Öffentlichkeit vorstellen. Dann würde man auch vielleicht einige der Java, und C++ Fans zurückgewinnen können.

Nehmen wir mal an, man verfährt nach der obigen Anleitung und schreibt zuerst seinen C-Code und bindet den dann in die Python Anwendung ein. Der Vorteil ist, dass der C-Code mit nativer C-Geschwindigkeit läuft und all das kann was auch C kann. Gleichzeitig hat man mit Python jedoch ein User-Interface was an ein Einfachheit schwer zu überbieten ist. Wie man das ganze objektorientiert gestaltet ist derzeit nicht klar. Aber ich glaube das geht auch auf diese Weise. Weil es ja mehrere Python-Libraries gibt, die objektorientiert funktionieren. Man man mit so einer Pipeline noch weitere Programmiersprachen wie Java oder C++? Eher unwahrscheinlich. Wenn man dann noch im C-Code Threading einsetzt un den -O3 Compilerschalter kann man High-performance-Anwendungen betreiben.

Eim Performance-Vergleich zwischen Python pur und Python plus C-Library hat http://www.maxburstein.com/blog/speeding-up-your-python-code/ angestellt. Danach erreicht man mittels ctypes einen Performancegewinn um den Faktor 30. Anders formuliert, Python ist 30x langsamer als C.

CFFI
Eine weitere Methode Python mit C-Code anzureichern ist CFFI. Die Entwickler von pymunk benutzen es aktiv http://www.pymunk.org/en/latest/advanced.html Um damit ihre C-Library für Python User zugänglich zu machen.

Insgesamt muss man festhalten, dass es im Bereich der Python Schnittstellen relativ viel Chaos gibt. Insgesamt existieren mindestens 5 Wege wie man Python und C zusammenbringt, die noch dazu sehr schlecht dokumentiert sind. Aber, mit Blick in 10 Jahren dürfte sich das Problem entschärft haben weil die Programmierer eher einen Überblick erhalten was geht und was nicht. Wenn man das Angebot etwas strafft und die Dokumentation verbessert hat man eine sehr gute Programmierumgebung. Im Gegensatz dazu sind andere Programmiersprachen wie Java oder C# auf den ersten Blick sehr konsistent aufgebaut. Haben aber den Nachteil, dass sie sich in einer technologischen Sackgasse befinden. Kurz gesagt, ich glaube dass die Mischung Python + C für systemkritische Software gedacht ist, während Java und Co zum rumspielen und Lernen entwickelt wird.

Performance von ctypes ist überragend

Die neu entdeckte ctypes Schnittstelle in Python habe ich einer näheren Untersuchung unterzogen. In C wird zunächst eine Primzahlen Funktion definiert, die eine große Last auf der CPU erzeugt. Diese wird dann in eine Binär-Library kompilert und über Python eingebunden. Dann wird die Ausführungszeit verglichen. Die Laufzeit mit ctypes ist dieselbe als wenn man das C-Programm solo startet. Zur Verdeutlichung hier der Sourcecode:

/*
  Kompilieren:
    gcc -shared -Wl,-soname,prim -o prim.so -fPIC prim.c
  
  Python:
    import ctypes
    prim = ctypes.CDLL('/tmp/1/prim.so')
    prim.main()
  
  Performance: 
    gcc real	0m6.557s
    python real	0m6.578s
*/

#include <stdio.h>
int main() {
  int flag;
  for (int i=0;i<300000;i++) {
    flag=0;
    for (int a=2;a<=i/2;a++) {
      if (i%a==0) { 
        flag=1;
        break;
      }
    }
    if (flag==0) printf("%d\n",i);
  }
  return 0;
}

Natürlich ist das ganze nicht wirklich eine Neuigkeit weil das PyPi Repository wo bereits sehr viele C-Librarys gewrapped wurden ja bereits existiert. Das heißt, dass man C mit Python koppeln kann, haben schon andere Leute herausgefunden. Interessant daran ist jedoch, dass es zukunftsfähig ist. Das heißt man kann davon ausgehen, dass Python eine ausgezeichnete Perspektive besitzt. Weil man auch eigene C-Programme leicht dafür aufbereiten kann. Wenn jedoch Python Programme auf C-Bibliotheken zugreifen, ist die Programmiersprache unschlagbar. C ist zweifellos die performanteste Sprache überhaupt.

Ctypes, SWIG oder CFFI dürfte einer breiten Öffentlichkeit nahezu unbekannt sein. Wir haben es also mit einem sehr leistungsfähigen Konzept zu tun, was gleichzeitig unbekannt ist. Stattdessen denkt der Mainstream, dass Java oder C# die Zukunft wäre.

Spieleentwicklung in Python

Eigentlich wollte ich von pygame auf PySFML umsteigen. Das gestaltet sich jedoch schwieriger als ursprünglich gedacht. Der Grund ist, dass SFML im C/C++ Umfeld zu Hause ist und für diese Sprachen gibt es die Tutorials. Man kann zwar mittels „dir(command)“ auch in Python herausfinden, wie das Python Äquivalent lautet aber das ist mühsam. Erschwerend kommt hinzu, dass nach dem Start der GUI pySFML mindstens genauso viel CPU schluckt wie pygame. Stolze 15% werden von der CPU abgezweigt und das für ein paar Linien und 30 fps.

Offenbar führt im Python Umfeld an pygame nichts vorbei. Unter C würde SFML die bessere Wahl sein, dort ist dier Performance überragend und dort passen auch die Codebeispiele von der Hilfe-Seite. Unter Python jedoch sind Game-Engines immer so eine Sache. Wirklich guten Code kann man mit pygame beispielsweise nicht produzieren. Das ist aber nicht schlimm, weil es letztlich um den Prototypen geht und nicht um die fertige Applikation. Der Vorteil bei Python ist eben, dass man nur sehr wenige Lines of Code benötigt und man schnell fertig ist mit dem Projekt. Das die Anwendung zäh reagiert und manchmal abstürzt kann man da verschmerzen.

Was genau soll die Software einmal können wenn sie fertig ist? Nun, angedacht ist, einen Motion Graph in Python zu implementieren, also eine Animationssequenz die sich interaktiv steuern lässt. Anders als bei Box2D wird die Animation nur auf den Bildschirm ausgegeben, ohne dass im Hintergrund eine Kollisionsüberprüfung durchgeführt wird. Der darauf aufbauende RRT Solver dürfte pfeilschnell sein. Roboter kann man dann zwar nicht mehr damit steuern, aber dafür kann man das Prinzip leichter verdeutlichen bei dem Motion Primitive mit einem RRT Solver kombiniert werden.

Was schon geklärt ist ist die Frage wie die Map im Speicher gehalten wird, nämlich so: http://stackoverflow.com/questions/23318440/2d-array-to-tiled-map-pygame-python Also einfach eine Array-artige Liste als Tiled map. Auf dieser Map werden dann Hindernisse wie Graben eingeblendet und über ein Menü kann eine Animationssequenz aktiviert werden. Das jedenfalls die Idee, wenn das Projekt mal fertig ist.

Einführung in die objektorientierte Programmierung mit Java

Java wird aus unterschiedlichen Gründen von vielen Leuten abgelehnt wobei vermutlich die strikte Orientierung an objektorientierter Programmierung dasjenige Feature sein dürfte, was am meisten Unwillen erzeugt sich näher mit dieser Programmiersprache auseinanderzusetzen. Gleichzeitig gibt es in der Fachliteratur einen Mangel bezüglich darin, diese Programmiermethode einsteigerfreundlich zu erläutern. Deshalb im folgenden eine kleine Übersicht wie OOP mit Java funktioniert.

Zunächst einmal sollte man sich frei machen von der üblichen Vorstellung, objektorientierte Programmierung hätte etwas mit Objekten zu tun (Objekte im Sinne von Klassen zur Beschreibung von Autos, Gebäuden usw) Bei der Programmierung geht es niemals um konkrete Objekte aus dem richtigen Leben, sondern es geht um Computercode, das ist etwas grundlegend verschiedenes. Um das besondere an OOP zu verstehen, zunächst ein kleiner Exkurs zu dessen Gegenteil, der strukturierten Programmierung.

Bei der strukturierten Programmierung werden Sub-Funktionen definiert, an die Variablen übergeben werden:

void function1 (int a, int b, int c) {

}

void function2 (int a) {

}

void function3 (int b, int c) {

}

Zusätzllich dürfen keine globale Variablen verwendet werden, weil dadurch das Unterteilen in Unterprobleme ausgehebelt werden würde. Ein Nachteil der strukturierten Programmierung besteht darin, dass bei größeren Problemen die Liste an zu übergebenden Variablen immer länger wird. Wenn man in einem Computerspiel beispielsweise eine Pfadplanung durchführen möchte, muss man neben einem Array was die Karte enthält auch noch weitere Arrays übergeben welche die aktuelle Punktzahl und den Aufenthaltsort der Gegner enthalten. Gleichzeitig gibt es in Sprachen wie C das Problem, dass man übergebende Variablen nicht abändern darf. Will man dies tun, müssen stattdessen Pointer auf die Variablen übergeben werden, die dann in der Funktion verändert werden. Wie man sieht stößt das Konzept relativ schnell an seine Grenzen.

Die Alternative dazu besteht in der Verwendung von globalen Variablen:

int a; 
int b;
int c;

void function1 () {

}

void function2 () {

}

void function3 () {

}

Man kann jetzt von jeder Funktion aus auf die Variablen zugreifen. Aus Sicht der strukturierten Programmierung wäre das ein Verstoß gegen die Regel „Verwende keine globalen Variablen“. Aber anstatt das ganze als schlechten Stil zu bezeichnen ist es in der Fachlitatur unter einem anderen Namen bekannt geworden: objektorientierte Programmierung. Das ganze kann man weiter vereinfachen, indem man die einzelnen Variablen zu einem Struct zusammenfasst:

class Class1 {
  struct Spielstand {
    int a; 
    int b;
    int c;
  }

  void function1 () {
    Spielstand.b = 5;
  }

  void function2 () {
    Spielstand.a=10;
  }

  void function3 () {

  }
}

Der Sinn des ganzen ist es, dass man die Übergabe von einer oder mehrerer Variablen an die Unterfunktionen einspart und auch nicht mit Zeigern hantieren muss, wenn man die Variablen in der Funktion verändern möchte. Das ist der ganze Sinn der objektorientierten Programmierung.

Man kann das ganze noch weiter ausbauen, hin zu Vererbung, Kommunikation der Objekte untereinander usw. Das würde den Rahmen dieser Einführung jedoch sprengen.