Hin und wieder stolpert der Entwickler bei seiner Suche nach guten Lösungen über interessante Algorithmen, die er eigentlich gerade nicht braucht. In diesem Fall handelt es sich um Voses Algorithmus zum Generieren von Zufallswerten anhand einer vorgegebenen Verteilung.
Das klingt jetzt erst einmal total uninteressant, aber neben der tatsächlichen Eleganz des Verfahrens, möchte ich noch bekannte Anti-Pattern ins Spiel bringen.
Die simpelste Art eine Zufallszahl x mit 1 \leq x \leq n zu generieren, ist ein Würfel mit n Seiten zu werfen. In diesem Fall hat man eine Gleichverteilung aller möglichen Werte. Häufig benötigt man jedoch eine andere Verteilung. Vielleicht sollen im eigenen Anwendungsfall 50% der eingehenden Daten mit Verfahren A analysiert werden und jeweils 25% der Daten mit den Verfahren B und C. Dann reicht ein einfaches Würfeln nicht mehr aus und wir müssen ein wenig Berechnung hinzusteuern. In diesem Fall könnten wir sagen, die Seiten Eins und Zwei sind für Verfahren A reserviert und die Seite Drei für Verfahren B und Seite Vier für Verfahren C.
Häufig sind die Verteilungen aber komplexer, wie etwa in dem folgenden konstruierten Beispiel mit den Wahrscheinlichkeiten 18,75%, 31,25%, 12,5% und 37,5%. Der triviale und daher im Sourcecode sehr häufig anzutreffende Ansatz ist hier kurz skizziert. Ein Zufallswert wird generiert und dann wird geprüft, in welchem Intervall er landet.
public int findIntervall(double random) {
double[] intervall = { 0.1875, 0.3125, 0.125, 0.375 };
double limit = 0;
for (int i = 0; i < intevall.length; i++) {
limit += intervall[i];
if (random < limit) {
return i;
}
}
}
Wie man unschwer sieht ist die Suche durch eine Liste von Werten recht unelegant und bei vielen Einträgen auch ineffizient.
Der Algorithmus von Vose verwendet eine elegante Veränderung der Problemstellung um eine effizientere Prüfung zu erzielen. Die Zugrunde liegende Idee ist die Alias Methode, aus den einzelnen Verteilungen werden in O(n \log(n)) zwei Listen generiert und mit ihrer Hilfe dann die Zufallswerte in O(1) gewürfelt.
Die obige Grafik zeigt die Grundidee des Algorithmus für unsere didaktisch gewählten Verteilungen. Die einzelnen Säulen im Diagramm werden so gekappt, dass die einzelnen Fragmente auf gleiche Höhen zusammengefügt werden können. Dabei stehen entweder ein oder maximal zwei unterschiedliche Fragmente in einer Spalte aufeinander. Die länglichen mathematischen Beweise, dass dies tatsächlich möglich ist, unterschlage ich an dieser Stelle und konzentriere mich lieber auf die bestechende Schönheit der Lösung.
Mit den Würfen zweier imaginärer Würfel können wir unseren Zufallswert bestimmen. Genaugenommen besitzt einer der beiden imaginären Würfel nur zwei Seiten, ist also eine Münze. Aber wie funktioniert es nun?
Mit dem ersten Würfel entscheiden wir, mit welcher Spalte wir arbeiten werden. Im obigen Beispiel ein Wert zwischen 0 und 3. Dann schauen wir für diese Spalte in unsere erste Liste. Dort ist verzeichnet, mit welcher Wahrscheinlichkeit der ursprüngliche Einträg gewählt werden soll. Hier sind es die Werte 0.75, 1.0, 0.5 und 1.0. Ein entsprechender Münzwurf entscheidet dann, ob tatsächlich der Wert genommen wird oder der andere dort eingezeichnete Wert (Alias genannt). In der zweiten Liste steht für jede Position der mögliche Alias Wert verzeichnet. Hier sind es der Werte 3 in der ersten Spalte und der Wert 1 in der dritten Spalte.
Viele elegante Algorithmen werden deshalb nicht verwendet, weil sie dem Entwickler unbekannt sind und er sich in der Kürze der verfügbaren Zeit mit simplen Ad-Hoc Lösungen begnügt. Hier finden sich die beliebten Anti-Pattern Reinventing the wheel und Reinventing the square wheel. Leider tragen die Entwickler eine große Mitschuld an den Myriaden Zeilen unerquicklichen Quellcodes, weil sie versäumen auf die notwendigen Recherchen und Weiterbildungen hinzuwirken.
Ganz am Ende noch ein effizienter Algorithmus für Softwareentwickler, die nur ganzzahlige Wahrscheinlichkeiten verteilen möchten. Eine Zahl zwischen 1 und 100 würfeln und dann in einer Liste mit 100 Einträgen schauen, welcher Wert dort steht. Für unser erstes Beispiel steht also in den ersten 50 Einträgen eine 1 und in den nächsten 25 Einträgen eine 2 und in den letzen 25 Einträgen eine 3. Dann kann doch beim Würfeln nichts mehr schiefgehen.