Codeschnipsel

Gewichteter Zufall bei diskreten Werten

Zurück zur Übersicht
Mit der PHP-Funktion mt_rand() kann eine Zufallszahl innerhalb bestimmter Grenzen erzeugt werden. Jede der Zahlen innerhalb dieser Grenzen tritt jedoch mit gleicher Wahrscheinlichkeit auf. Manchmal wünscht man sich jedoch, dass bestimmte Werte häufiger vorkommen, als andere. Bspw. wenn Banner, Bilder oder berühmte Zitate dem Benutzer zwar zufällig angezeigt werden sollen, bestimmte aber häufiger als andere.

In der hier vorgestellten Funktion dw_rand() habe ich solch einen gewichteten Zufall für diskrete Werte realisiert. Diskret heißt hier, dass die möglichen Werte konkret angegeben werden können. Neben einer Menge an Zahlen können dies genauso gut Buchstaben oder Wörter sein. Die möglichen Werte müssen zunächst in einem Array nebst ihrer Gewichtung aufgebaut werden.

Ein Beispiel für einen "gezinkten" Würfel:

<?php
 $dice[1] = 0.1;
 $dice[2] = 0.1;
 $dice[3] = 0.1;
 $dice[4] = 0.5;
 $dice[5] = 0.1;
 $dice[6] = 0.1;
?>

Wie man sieht, soll hier mit 50%-iger Wahrscheinlichkeit eine 4 gewürfelt werden, also durchschnittlich mit jedem zweiten Wurf. Es versteht sich von selbst, dass sich alle Wahrscheinlichkeiten zu 1 addieren müssen.

Der Funktion wird nun dieses Array übergeben. Zusätzlich kann optional noch ein Wert für den Fehlerfall (falls bspw. die Summe der Gewichtungen nicht 1 ergeben sollte) angegeben werden. Als Rückgabewert erhalten wir dann einen der Werte aus unserem Array gemäß der zuvor definierten Wahrscheinlichkeiten.

<?php
 echo 'Sie haben eine ' . dw_rand($dice) . ' gewürfelt.';
?>

Kommen wir zur eigentlichen Funktion. In der Variable $res wird zunächst die Auflösung für die Zufallswerte festgelegt. Die hier eingetragene Zahl stellt die größte 10er-Potenz in einem gewöhnlichen 32-bit Integer dar. Damit können die zuvor definierten Wahrscheinlichkeiten bis zur 9. Nachkommastelle genau angegeben werden. Alles darüber hinaus kann von der Funktion nicht mehr korrekt erfasst werden. In unserem obigen Beispiel des gezinkten Würfels haben wir sogar nur eine Nachkommastelle verwendet. Daher könnte die Auflösung auch auf bis zu 10 reduziert werden - der Geschwindigkeitsvorteil sollte allerdings kaum signifikant sein.

Als nächstes wird mit mt_rand() eine ganz gewöhnliche Zufallszahl mit der zuvor definierten Auflösung ermittelt. Dann gehen wir das Array mit den Wahrscheinlichkeitswerten ab. In der Variable $psum rechnen wir dabei schrittweise die einzelnen Wahrscheinlichkeitswerte (relativ zur Auflösung) zusammen. Sobald wir mit $psum unsere Zufallszahl überschreiten, geben wir das Element zurück, was gerade an der Reihe war.

<?php

 function dw_rand ($space, $errval = false) {
  $res = 1000000000;
  $rn = mt_rand(0, $res - 1);

  foreach ($space as $element => $probability) {
   $psum += $probability * $res;
   if ($psum > $rn) return $element;
  }

  return $errval;
 }

?>

Wieso liefert uns dieses Konzept einen gewichteten Zufall? Nun, wenn wir die Wahrscheinlichkeiten aufaddieren, so zählt in unserem Würfelbeispiel die 1 nur 0,1 hinzu, während die 4 direkt 0,5 hinzuaddiert. Da die Zufallszahl gleichgewichtet ist, ist die Wahrscheinlichkeit, dass beim Hinzuaddieren von 0,5 die Zufallszahl überschritten wird, auch 5 mal größer als bei der Addition von 0,1.

Kommentare

Autor Thoro

Zurück zur Übersicht
Autor:
Zurück: URLs im Text identifizieren