möchte­gern­geek

Ein Algorithmus, von dem jeder schoneinmal gehört haben sollte, ist die Tiefensuche (Depth First Search). Wenn man Zusammenhangskomponenten in einem Graphen finden will oder nach einem bestimmten Knoten in einem Graphen sucht, ist die Tiefensuche meist der einfachste und oft ein geeigneter Algorithmus mit einer Zeitkomplexität $\mathcal{O}(N+M)$, die linear in der Anzahl der Knoten und der Kanten ist. Da man gefühlt alle Graphalgorithmen am besten rekursiv beschreiben kann, folgt hier eine (nichtrigorose) Beschreibung.

1. Man startet die Tiefensuche an einem beliebigen Knoten.
2. Bei jedem noch nicht besuchten Nachbarn startet man wieder eine Tiefensuche.

Aber was macht man im Alltag mit einer Tiefensuche? Meine Antwort darauf ist: Labyrinthe bauen.

Bei dieser Gelegenheit muss NetworkX erwähnt werden. Ein Python Modul, das sehr schöne Klassen für Graphen bereitstellt und perfekt geeignet ist, um schnell Prototypen von Graphalgorithmen zu testen.

Der Code ist als Gist auf GitHub verfügbar.

Wer kennt das nicht: Man hat sich ein Python Skript geschrieben, um seine Daten per Bootstrap Resampling auszuwerten und stellt fest, dass das Konstrukt zur Bildung des „Samples mit Ersetzungen“

    import random
    x = [1,2,3]

    bootstrapSample = [random.choice(x) for _ in x]

einfach nicht schnell genug ist.
Aber glücklicherweise gibt es numpy!

    import numpy
    x = [1,2,3]

    bootstrapSample = list(numpy.random.choice(x, len(x)))

Das ist — zumindest in meinem Anwendungsfall — spürbar schneller. Ich werde in Zukunft also immer optimale Fehlerbalken erzeugen.

Differentialgleichungen numerisch zu lösen macht mehr Spaß, als man erwarten würde, wenn man es hört. Und sobald man den ersten Runge-Kutta-Algorithmus in einer kommerziellen Interpretersprache geschrieben hat, bemerkt man, dass dieses Skript doch recht lange braucht.

Für dieses Problem gibt es zwei Lösungen: Entweder wird man zum Guru und wendet irgendeine okkulte Matlab-Magie an, um das Programm schneller laufen zu lassen, oder man schreibt das Programm in einer schönen Sprache neu. In C zum Beispiel.

Ich habe mich für den einfachen Weg entschieden und wenig überraschend eine Tempoverbesserung von Faktor $\sim 140$ festgestellt. Jedenfalls für diesen Lorenzattraktor. \begin{align} \dot{X} &= a(Y - X) \ \dot{Y} &= X(b - Z) - Y \ \dot{Z} &= XY - cZ \ \end{align} Geplottet habe ich die Werte dann mit Python und matplotlib.

Warum ich den Titel „Schmetterlingseffekt“ gewählt habe? Naja, das Bild hier sieht ein wenig nach einem Schmetterling aus. Und tatsächlich wurde der Schmetterlingseffekt nach diesem Differentialgleichungssystem benannt — und nicht nach der Geschichte aus Jurassic Park.

Er bewegt in Peking die Flügel, und im Central Park gibt’s Regen statt Sonne.

— Dr. Ian Malcolm (1993)

Wie genau der Lorenzattraktor mit Chaos zusammenhängt, habe ich in diesem Post dargestellt.

Der Quellcode ist als Gist auf GitHub.