möchte­gern­geek

Soeben habe ich mein Blog von Blogger auf einen kleinen Raspberry Pi 2 in meiner Wohnung verschoben. Als Engine benutze ich Pelican, ein statischer Blog Generator in Python, der mir auf den ersten Blick sehr gefällt.

Nicht nur, dass ich alle Einträge jetzt in Markdown schreiben kann, was es ermöglicht das ganze Blog per git zu verwalten (dementsprechend gibt es den Quellcode auf GitHub), sondern es steht mit Pygments ein sehr hübsches Syntax Highlighting zur Verfügung.

float Q_rsqrt( float number )
{
    long i;
    float x2, y;
    const float threehalfs = 1.5F;

    x2 = number * 0.5F;
    y  = number;
    i  = * ( long * ) &y;                       // evil floating point bit level hacking
    i  = 0x5f3759df - ( i >> 1 );               // what the fuck?
    y  = * ( float * ) &i;
    y  = y * ( threehalfs - ( x2 * y * y ) );   // 1st iteration
    // y  = y * ( threehalfs - ( x2 * y * y ) );   // 2nd iteration, this can be removed

    return y;
}

Außerdem Formeln in $\LaTeX$ Notation dank MathJax

$$\mathcal H = \sum_{\left< i, j \right>} s_i s_j$$

Ich werde diese Gelegenheit außerdem nutzen die meisten Einträge meines Blogs zu verwerfen und nur einige ausgewählte zu überarbeiten und hier zu veröffentlichen.

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 $S$ von $N$ Zahlen sortieren wollen, können wir die Summe der Differenzen zwischen benachbarten Zahlen als Energie betrachten, denn die ist minimal in einer sortierten Liste. \begin{equation} \mathcal{H} = \sum_{i=1}^{N-1} \left| S_i - S_{i+1} \right| \end{equation} Um eine Lösung in eine andere zu verwandeln, reicht es zwei Elemente der Sequenz zu tauschen.

Der Kern von Simulated Annealing ist der Metropolis Algorithmus.

1. Starte bei einer hohen Temperatur $T$.
2. Berechne die Energie $\mathcal{H}(S)$ der aktuellen Konfiguration $S$.
3. Erzeuge eine neue Konfiguration $R$ durch eine kleine Änderunge von $S$.
4. Akzeptiere $R$ mit der Wahscheinlichkeit $$p_\mathrm{acc} = \min\left[1 ,\exp(-(\mathcal{H}(R) - \mathcal{H}(S))/T) \right],$$ sodass eine „sortiertere“ Sequenz immer akzeptiert wird und eine „unsortiertere“ vor allem bei hohen Temperaturen. Wenn $R$ akzeptiert wird, gilt $S:=R$, ansonsten wir die alte Konfiguration $S$ weiter benutzt.
5. Reduziere die Temperatur (beispielsweise durch Multiplikation mit einer Zahl etwas kleiner als 1) und breche ab, wenn die Zieltemperatur erreicht ist. Ansonsten beginne wieder bei Punkt 2.

Genug der Theorie: In einem Gist auf GitHub 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 $\mathcal{O}(N \log(N))$ Sortier-Algorithmen?!

Programmiersprachen muss man üben, um sie zu lernen und um sie nicht wieder zu vergessen. 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 (Stichwort: Bitcoin ASIC), ist meiner dennoch sehenswert, da er SHA-256 in 256 Zeilen darstellt.

Der Code ist als Gist auf GitHub, da er in seinen 256 Zeilen ansonsten den Lesefluss stören würde.

In Python ist es übrigens etwas kürzer.

print(hashlib.sha256(b"Hallo Welt!").hexdigest())