Blogumzug

Dieser Blog ist umgezogen nach: blog.schawe.me

Details zu dem Umzug gibt es auf der neuen Seite: blog.schawe.me/blogumzug.html

SimulatedSort

Simulated Annealing ist eine Optimierungsmethode, die von natürlichen Kristallisationsprozessen inspiriert ist. Man startet in der Schmelze bei hohen Temperaturen und lässt es dann abkühlen, sodass die Atome sich in einem Zustand minimaler Energie anordnen, dem Kristallgitter. Wenn man also für ein Optimierungsproblem die zu optimierende Größe als Energie ansieht, und man eine Lösung durch eine kleine Änderung in eine andere Lösung verwandeln kann, kann man mit dieser Methode eine Näherung für das Optimum finden.

Wenn wir also eine Sequenz von Zahlen sortieren wollen, können wir die Summe der Differenzen zwischen benachbarten Zahlen als Energie betrachten, denn die ist minimal in einer sortierten Liste. Um eine Lösung in eine andere zu verwandeln, reicht eine Permutation.

Genug der Theorie: Hier präsentiere ich ein schnell terminierendes Sortierprogramm, das zwar nicht immer eine sortierte Liste findet, aber zumindest eine Näherung! Es ist also Bogosort in mehr als nur einer Hinsicht überlegen!
Wer braucht da noch O(n log(n)) Sortier-Algorithmen?!

Munin

Weil bunte Diagramme das beste auf der Welt sind, ist Munin mein neuer lieblings-Daemon: man konfiguriert ihn einmal kurz und er zeichnet alle 5 Minuten hunderte Diagramme über alle Vitalfunktionen seines Hosts.

Hier besonders schön: ein Kopiervorgang. Die Festplatte wird von außen nach innen beschrieben; weil sie sich außen schneller dreht, ist die Schreibgeschwindigkeit anfangs höher.

Oder auch immer hübsch: "Fieberkurven" der Festplatten. Die externe wird offenbar schlecht gekühlt. Die Lücken entstehen übrigens sobald eine Festplatte in den Standby wechselt.

Zum Schluss noch was klassisches: CPU Benutzung. Das Kopieren ist natürlich nicht durch die CPU begrenzt.

Compiler Benchmark

Ich habe eine kleine Sammlung selbst implementierter Kryptographie, wie ich im letzten Post schon angedeutet habe. Was kann man nun mit kaum/gar nicht optimierten krypto-Funktionen anfangen? Man kann sie natürlich benutzen, um die Daten, die man mit eigenen Programmen verwaltet, zu verschlüsseln. Aber noch viel besser kann man optimierende Compiler darauf los lassen und sehen, welcher am besten optimiert.
Hier sind also meine Messdaten. Grün ist Linux, Blau ist Windows.
Als Compiler Option habe ich jeweils nur -O3 (oder vergleichbar) übergeben. Das schlechte Abschneiden des Microsoft Compilers liegt übrigens daran, dass er Sonderwünsche betreffend der AES-NI Befehle hatte, weshalb dort der reine-Software-Zweig gemessen wurde. Messwerte für den Linux 32 Bit Intel Compiler fehlen, da die Installation scheinbar schief gegangen ist und 32 Bit auf Linux meiner Meinung nach nur eine sehr untergeordnete Rolle spielt.

Besonderes Augenmerk sollte übrigens auf die Unterschiede zwischen 32 und 64 Bit gelegt werden. Nehmt das ihr Leute die glauben, dass 64 Bit nur wegen des RAM gut sei ;) Zugegebenermaßen arbeiten Threefish sowie SHA512 mit 64 Bit breiten Worten, die auf einem 64 Bit Betriebssystem mindestens doppelt so schnell verarbeitet werden können.

Es ist auf jeden Fall interessant zu sehen, dass verschiedene Compiler verschiedene Warnungen ausgeben -- und dass der Microsoft Compiler bis 2012 scheinbar noch nichts vom c99 Standard wusste.
Außerdem sind die farbigen Ausgaben von clang und seine statische Code Analyse sehenswert.
Den höchsten Komfort bietet meiner Meinung nach gcc, der dank MinGW-w64 auch unter Linux für Windows kompiliert -- und dabei Code erzeugt, der in diesem Test sehr konkurrenzfähig ist.

SHA-256 in 256 Zeilen

Programmiersprachen muss man üben, um sie zu lernen und um sie nicht wieder zu verlernen. Ich habe also meine Zeit damit vertrieben einen SHA-256 zu schreiben -- eine kryptographische Hash Funktion. Die Spezifikation ist Glücklicherweise sehr sehr verständlich.
Und auch wenn es tausende andere Implementationen gibt, die schneller sind, alle Grenzfälle beachten (ich befürchte, dass mein Programm Probleme auf Big Endian Systemen bekommt), und sogar Schaltkreise, die hochoptimiert nur diese Operation beherrschen (vgl. Bitcoin ASIC), ist meiner dennoch sehenswert, da er SHA-256 in 256 Zeilen darstellt.

Natürlich fehlt die main() Funktion, was daran liegt, dass es als Bibliothek entworfen ist.
In Python ist es übrigens etwas kürzer ;)

DGLshow

Das ist ein Doppelpendel. Soetwas möchte man eigentlich auf seinem Schreibtisch stehen haben. Aber dann stellt man fest, dass ein Doppelpendel viel zu teuer ist, und entschließt sich, dass ein virtuelles auf dem virtuellen Schreibtisch ausreicht.

Also erinnert man sich an eine alte Vorlesung, schreibt ein kleines C++ Programm mit einen adaptiven Runge-Kutta-4 Löser, das mit den Qt Zeichenprimitiven Lösungen visualisiert.

Da die Differentialgleichung zum Doppelpendel etwas abschreckt, habe ich zuerst einige DGLn lösen lassen, mit denen ich schon vertraut war. Den Lorenz Attraktor. Ein Dreikörper Problem. Und ein Sonnensystem/Bohrsches Atommodell.

Auch wenn der Code nicht sehr aufgeräumt ist -- und er wird vermutlich auch nie besser aussehen -- sind die Quellen auf GitHub: github.com/surt91/DGLshow.

Dieses Programm ist übrigens ein Paradebeispiel für ein schlechtes GUI und Anfangswerte ändert man direkt im Code -- aber mir zumindest macht es Spaß :)

Wie man einen Borg Kubus baut

Wie man am neuen Logo dieser Seite sieht, gefällt mir die Ästhetik, der Depth First Search (DFS) Labyrinthe und ihrer Entstehung. Und was könnte besser sein, als so eine 2D Animation? Richtig eine in 3D! Streng genommen, ist es zwar nur eine zweidimensionale Projektion mittels POV-Ray. Aber dennoch löst es ein Gefühl der Seekrankheit aus, was ich als Indiz für gelungene 3D Darstellung werte.

Sobald ich eine Möglichkeit finde zur 4D Darstellung, werde ich nicht zögern, das entstehende Video hier zu zeigen. Ich fürchte allerdings, dass das noch eine Weile dauern könnte. Bis dahin könnt ihr einer Borg Sphäre bei der Entstehung zusehen.

Making of: Das neue Logo

Tschüss altes Logo!

Hallo neues Logo!

Und weil das alleine etwas knapp wäre, habe ich noch ein Video gemacht, wo gezeigt wird, wie ich es zeichne -- mit zehn Stiften in zehn Händen.

Als besonderes Feature kann man im neuen Logo rn nicht mehr von m unterscheiden. Zum nachbasteln, sind nur einige Änderungen an diesem code nötig. Man schränkt die Tiefensuche auf Knoten mit der Eigenschaft "schwarzer Pixel" ein und liest ein Bild aus, um den Knoten diese Eigenschaft zuzuweisen (vgl. diesen Post).

Ising Modell zur Bildentrauschung

Eines der bekanntesten Modelle der statistischen Physik ist das Ising Modell. Es besteht aus (klassischen) Spins auf einem Gitter im Wärmebad und soll magnetische Eigenschaften von Festkörpern modellieren. Es zeigt nämlich in 2D und 3D (und 4D ... ) einen Phasenübergang zweiter Ordnung von "magnetisch" zu "nicht magnetisch", so wie ferromagnetische Materialien, die oberhalb der Curie Temperatur nicht mehr magnetisch sind.

In einfachen Worten: Die Spins des Ising Modells richten sich so aus, wie ihre Nachbarn und die Temperatur bringt sie wieder durcheinander.

Aber es wäre natürlich langweilig das Modell so zu benutzen, wie alle anderen auch. Deshalb stelle ich hier eine Anwendung aus in diesem Buch vor, die nichts mehr mit Magneten zu tun hat: Rauschunterdrückung in Bildern.

Andererseits bin ich Physiker und darf deshalb nichts machen, was direkt nützlich wäre, also beschränke ich mich auf schwarz-weiße Bilder, die man direkt auf das "spin up"-"spin down" des Ising Modells abbilden kann.

Die Idee ist, das jeder Spin einem Pixel entspricht. Dann koppelt man das Gitter des Ising Modells über einen zusätzlichen Energie-Term an das Bild, das man entrauschen will und equilibriert bei T=0.

Das Schema dazu wurde bereits in diesem Post gezeigt. Graue Knoten entsprechen den Pixeln des verrauschten Bilds und weiße Knoten den Ising Spins, die am Ende als Pixel des entrauschten Bilds interpretiert werden.

Genug der Theorie. Es wird Zeit für pixelige Bilder. Leider hatte ich kein verrauschtes Bild, also habe ich ein beliebiges Bild gemalt und 10% aller Pixel invertiert.

Links das verrauschte Bild und rechts das entrauschte. Ja, nicht perfekt. Und in dem zitierten Buch wird auf der gleichen Seite noch eine sehr viel bessere Methode angesprochen. Aber die hatte nichts mit dem Ising Modell zu tun. Und man sieht ja auch eine Verbesserung. Oder?

Nebenbei bemerkt, kann man das Ising Modell auch als zellulären Automaten mit zufälligem Element betrachten, denn jeder Spin ist eine Zelle, die nur lokal von seinen Nachbarn und zufällig durch die Temperatur beeinflusst wird.

Und weil so ein Post ohne Code nicht vollständig wäre und damit ich mit mit meinen Python Fähigkeiten blamieren kann, ist hier der Code.

Depth First Search und Labyrinthe

Wenn man alle Knoten eines Graphen besuchen möchte, benutzt meist entweder eine Breitensuche oder eine Tiefensuche. (Übrigens auch, wenn man ein bestimmtes Element sucht. Aber die Knoten einfach nur mal so zu besuchen, ist nett und zeigt, dass man sich um seinen Graphen sorgt.)

1. Man starte an einem Knoten.
2. Man schiebe die noch nicht besuchten Nachbarn auf einen Stack (für die Tiefensuche) oder eine Queue (für die Breitensuche). 
3. Man entnehme einen Knoten vom Stack/Queue und fahre bei 2. fort, bis der Stack/Queue leer ist.

Und weil ich gerade dabei bin, den Wikipedia-Artikel zu wiederholen, mache ich auch weiter damit.

Der beste Anwendungsfall ist nämlich, ein bisschen Zufall in den Algorithmus zu mischen, ein Labyrinth zu bauen und ein Video davon in HD zu posten!

Und weil man dafür weniger als 100 Zeilen Python braucht, spendiere ich auch den Code, falls irgendjemandem das Video nicht reicht. (Oder etwas gegen Youtube hat und sich das Video deshalb lieber selbst bauen würde.)
Außerdem gibt es mir Gelegenheit networkx zu erwähnen. Ein Python Modul, das sehr schöne Klassen für Graphen bereitstellt.

Wer bis hier hin durchgehalten hat, hat es sich verdient, zwei weitere Videos anzusehen.
Hier ist eine Breitensuche, erwartet langweilig:

Und hier bin ich mir nicht sicher, was schief gegangen ist. Aber es ist genial!

Oberflächenkachelung mit TikZ

Man arbeitet an einem Seminarvortrag und will ein Modell auf einem periodischen Gitter erklären. Natürlich kann man sich nicht entscheiden, wie viele Elementarzellen man darstellen möchte, außerdem ist es einem zuwider mehrere Elementarzellen per Hand zu schreiben.

Wer kennt das nicht?

Glücklicherweise gibt es eine Lösung. Weil man alle seine Aufzeichnungen sowieso in LaTeX setzt, benutzt man TikZ, bastelt eine Elementarzelle und kachelt sie über die Ebene, bis man das Gefühl hat, dass es genau passend für die Präsentation ist.
Als Bonus kann man noch mit den Parametern spielen, um einen möglichst überzeugenden pseudo 3D Effekt zu erzielen.

Ungefähr so:
Und danach kann man es in ein .svg wandeln und auf seinem Blog zeigen.

Und damit wäre wiedereinmal die Vorliebe dieses Blogs für schwarz-weiße Bilder, die entweder Linien und Kreise oder zu große Pixel enthalten, bestätigt.

Lektion #17509

Besuche niemals mit einem Browser, der weiß was Tabs sind, tvtropes.org, es sei denn, du willst wissen, wie das Symbol für "mehr Tabs als ich darstellen kann" aussieht. (Vgl. Wiki Walk und dieses XKCD Comic)

... *tab* Anime Catholicism *tab* Crystal Dragon Jesus  *tab* crystals do everything *tab* Sufficiently Advanced Alien *tab*  Abusing the Kardashev Scale for Fun and Profit *tab* ... 

 Auflösung: Auf Chrome für Android sieht es nach 99 Tabs so aus:

Rule 90

Vor kurzem habe ich angefangen "Think Complexity" zu lesen -- ein leicht verständliches, interessantes Buch, in dem unter anderem Zelluläre Automaten angesprochen werden. Und zwar die von Stephen Wolfram -- ja der Stephen Wolfram, der Mathematica und Wolfram|Alpha entwickelt hat (vermutlich jedoch nicht allein).
Zelluläre Automaten eignen sich natürlich sehr gut, pixelige Bilder zu erstellen, wie der Conways-Game-of-Life-Post beweist. Daher, lasse ich erstmal ein Bild sprechen.

Rule 90

Die Idee ist, dass man mit einem eindimensionalen Zustand startet, und einen neuen Zustand daraus mit lokalen Regeln, die je einen rechten und linken Nachbarn berücksichtigen, erzeugt. Stellt man diese Zustände untereinander da, entstehen Strukturen, wie die, die an ein Sierpinski-Dreieck erinnert.
Die Erklärung, wie genau diese Regeln lauten, und wie sie definiert sind, überlasse ich passenderweise Wolfram|Alpha.

Und damit ich auch etwas sage, das tiefsinnig erscheint: Die Dreieckige Form entspricht übrigens dem Vorwärtslichtkegel des Startwertes in der ersten Zeile. Die y-Achse entspricht hier schließlich einer Zeit und die "Lichtgeschwindigkeit", mit der Beeinflussungen propagieren können ist 1 Pixel pro Iteration.

Meinen Quellcode gibt es natürlich bei Github. Wenn auch nur in einem "kleine Fingerübungen in C"-Repo.

Für Liebhaber, hier noch eins im original 1982 Retro Look.

Rule 150

Passend zur Jahreszeit, wie ich finde.