Monte Carlo Methodik

Im Rahmen einer Vorlesung zu Game-Engines beschäftige ich mich derzeit mit “Reinforcement Learning”. Ein Verfahren, was damit in Zusammenhang steht, nennt sich “Monte Carlo Methods” oder eingedeutscht eben Monte-Carlo Methode.
Dieses simple Verfahren hat mich so beeindruckt, dass mir das einen kleinen Blogartikel wert war. Benutzt wird dieser Ansatz nämlich immer dann, wenn für ein gegebenes Problem der numerische Ansatz zu komplex oder schlicht nicht vorhanden ist.
Um die Arbeitsweise nun zu verdeutlichen, erwähnt der dazugehörige Wikipedia-Artikel, aus dem auch das Bild zu diesem Beitrag stammt, als Beispiel die (witzige) Annäherung an die Kreiszahl Pi.
Hierbei wird nämlich schlicht ein Quadrat auf dem Einheitskreis zufällig mit Punkten überzogen. Gemäß dem Gesetz der großen Zahl liegen nun Pi/4 aller Punkte innerhalb des Einheitskreises.
Und ob das nun auch tatsächlich so ist, lässt sich (wie auch sonst) wunderbar mit Python zeigen:

import sys, random

if __name__ == "__main__":
    durchgaenge = int (sys.argv[1])
    anzImKreis = 0
    for i in range(durchgaenge):
        x, y = random.random(), random.random()
        if x**2+y**2 <= 1:
            anzImKreis += 1;

    print "Pi = ", (4.0*anzImKreis)/durchgaenge

Und die dazugehörige Ausgabe mit Parametern:

$ python pibest.py 100
Pi =  3.0
$ python pibest.py 1000
Pi =  3.148
$ python pibest.py 10000
Pi =  3.1508
$ python pibest.py 100000
Pi =  3.14156
$ python pibest.py 1000000
Pi =  3.144532
$ python pibest.py 10000000
Pi =  3.1420184

Wäre ich Mathematiker, könnte ich nun zeigen, dass bei unendlich vielen Durchläufen die Kreiszahl Pi beliebig genau berechnet werden kann. Ich belasse es besser dabei und beende diesen Artikel mit einem passenden Zitat:

Wer sich nicht mehr wundern kann, ist seelisch bereits tot.

Albert Einstein

Eleganz vs. Verständlichkeit

Fremden Code zu lesen ist grausam. Man muss sich nicht nur in eine völlig andere Denkweise hinein versetzen, sondern versuchen einzelne Stückchen zu einem großen Ganzen zusammenzusetzen.
Eigenen Code zu lesen ist aber mindestens genauso grausam, wenn der vorliegende Quelltext sagen wir älter als zwei Monate ist. Man vergisst schnell, was man sich beim entwickeln gedacht hat und warum man das entstehende Programm in eine bestimmte Richtung und nicht anders programmiert hat.

Wenn ich nun also zum Beispiel ein geschriebenes Programm aus dem ersten Semester um eine bestimmte Funktionalität erweitern müsste, dann wäre ich wahrscheinlich schneller, wenn ich das komplette Programm “from-scratch” noch einmal komplett neu schreiben würde.
Diese Erkenntnis ist natürlich schon lange bekannt und es gibt daher auch viele Konzepte, wie man diesem Problem entgegnen kann. Auf diese möchte ich hier aber gar nicht weitergehen, sondern versuchsweise aufzeigen, wie man im Kleinen schon darauf achten kann, lesbaren Code zu produzieren.
Als Beispielsprache verwende ich Python, weil mir erstens die Sprache sehr gut liegt und weil sie den Benutzer schon konzeptuell zwingt “saubereren” Code zu schreiben.

Kommentare sind dazu da, den eigenen Code zu erläutern bzw. zu erklären und verwendete Parameter auf ihre Bedeutung hin zu verdeutlichen. Im Prinzip wohl eine gute Sache. Ich finde den Einsatz von Kommentaren dennoch nicht gut, weil sie meiner Meinung nach das Problem nicht an der Wurzel packen: Wenn ich Code erst erklären muss, bevor sie einem dritten verständlich erscheinen, ist die Wahrscheinlichkeit hoch, dass entweder das zu lösende (Teil-)problem noch nicht ganz geknackt ist, oder meine Bezeichnungen für Funktionen und Variablen Mumpitz sind. Selbst Bezeichnungen für Hilfsvariablen sollten eindeutig bestimmen, wofür diese gebraucht werden.

Als Beispiel soll folgendes Szenario dienen:
Hier soll die Eingabe des Benutzer verarbeitet und an eine Funktion weitergegeben werden. Im ersten Beispiel ohne genauere Variablenbezeichnung und mit Kommentar, im zweiten Beispiel mit treffenden Bezeichnungen.
Obwohl die Lebensdauer der Variablen mindestgebot, auktionsdauer, dateipfad gerade mal zwei Zeilen beträgt, tragen diese doch erheblich zur Lesbarkeit bei:

# Eingabe: versteigere 50,60,/tmp/bild.jpg
eingabe = raw_input()
if eingabe.split()[0] == 'versteigere':
    data = eingabe.split()[1].split(',')
    if len(data) != 3:
        print "error: wrong input"
    else:
        # Startet neue Auktion mit Mindestgebot,
        # Dauer der Auktion und Pfad zum Bild
        auktion.versteigere(data[0],data[1],data[2])

Und jetzt nochmal mit eindeutigen Bezeichnungen

eingabe = raw_input()
userBefehl = eingabe.split()[0]
if userBefehl == 'versteigere':
    befehlsParameter = eingabe.split()[1].split(',')
    if len(befehlsParameter) != 3:
        print "error: wrong input"
    else:
        mindestgebot, auktionsdauer, dateipfad = befehlsParameter[:]
        auktion.versteigere(mindestgebot, auktionsdauer, dateipfad)

Wie man sieht, hat man also nur durch eine bessere Bezeichnung der übergebenen Variablen ein Kommentar gespart und (hoffentlich) erheblich zur Lesbarkeit beigetragen.

Meines Erachtens darf hier auch ruhig redundante Information im Code vorkommen, wenn sie der Lesbarkeit dient. Im obigen Code ist das zum Beispiel das unnötige Slicing (befehlsParameter[:]), weil Python schlau genug ist, auch ohne das Slicing zu erkennen, dass die Liste mit drei Parameter auf die drei vorstehenden Variablen übergeben werden soll. Dennoch wird man durch das ‘[:]‘ beim Lesen noch einmal explizit darauf hingewiesen.

Onlinetest Python

Heute war es wieder mal soweit: Onlinetest. Dieses mal in Python. Nachdem ich erfolgreich meine Maschine (iMac mit Debian, Windowmanager war glaub ich FVWM) zweimal abgeschossen hatte, bin ich in der vorgegebenen Zeit von 90 Minuten knapp fertig geworden. Eigentlich sind die gestellten Aufgaben in den bisherigen Onlinetests, die ich so mitgeschrieben habe, nicht extrem schwer, trotzdem finde ich es aber schwierig auf Kommando kreativen (und möglichst cleveren) Code zu schreiben.

Es sind eben diese typischen Prüfungssituationen bei denen man unter erschwerten Bedingungen klaren Kopf behalten muss
Das waren die Aufgaben:

Aufgabe 1:

Man soll von der Standardeingabe eine Zeile einlesen und unnötige Leerzeichen entfernen. Außerdem soll jedes Wort mit einem großen Anfangsbuchstaben in Großbuchstaben umgewandelt wieder ausgegeben werden.

# a1.py
while True:
    line = raw_input()
    line = line.split()
    for word in line:
        if(str.isupper(word[0])):
            print str.upper(word),
        else:
            print word,
    print # Zeilenumbruch für schönere Ausgabe

Aufgabe 2:

Die zweite Aufgabe bestand darin, eine Datei belegung.dat einzulesen, die folgendes Format hatte: <VL-Nr>; <matrikelNr>; <VL-Name>; <VL-Typ>.
Danach sollte die so eingelesene Datei in folgendem Format in eine Datei ausgabe.dat geschrieben werden:
<VL-Nr>,<AnzahlBelegungen>, <VL-Name> <VL-Typ>
Momentan sind in der Ausgabe noch doppelte Einträge drin, das müsste noch geändert werden.

# a2.py
dict = {}
belegung = []

input = open('belegung.dat','r')
for line in input:
    line = line.split(';')
    belegung.append(line)

input.close()

for line in belegung:
    if dict.has_key(line[0]):
        dict[line[0]] += 1
    else:
        dict[line[0]] = 1

ausgabe = file('ausgabe.dat','w')

for nummer, anzahl in dict.iteritems():
    for line in belegung:
        tmp = ""
        if nummer==line[0]:
            try:
                tmp = str(nummer) + ',' + str(anzahl) + ',' + line[2] + '\n'
                ausgabe.write(tmp)
            except:
                pass

ausgabe.close()

Aufgabe 3:

Die dritte Aufgabe bestand darin, einen “sprach-begabten” Taschenrechner zu programmieren, der beim Aufruf des Programms Argumente wie “17 plus 4 minus 3 gleich” übernimmt und korrekt auswertet. Es soll bewusst auf Punkt-vor-Strich Rechnung verzichtet werden (also fällt eval() flach). Außerdem kann man der Einfachheit davon ausgehen, dass nur korrekte Argumente übergeben werden.
Ich hab ungefähr so etwas hingeschrieben:

# a3.py
import sys

i = 0
result = 0
input = sys.argv[1:]
while i < len(input):
    if input[1]=="gleich":
        result = int(input[0])
        break
    elif input[i]=="plus":
        result = int(input[i-1]) + int(input[i+1])
        input[i+1] = result
    elif input[i]=="minus":
        result = int(input[i-1]) - int(input[i+1])
        input[i+1] = result
    elif input[i]=="mal":
        result = int(input[i-1]) * int(input[i+1])
        input[i+1] = result
    elif input[i]=="durch":
        result = int(input[i-1]) / int(input[i+1])
        input[i+1] = result
    i += 1

print "Ergebnis:",str(result)