Profil | Mitglieder | Registrieren | Start | Suche


PHP-Support.de » Programmierung » PHP & MySQL » Codeschnipsel » Gewichteter Zufall bei diskreten Werten    » Hallo Gast [Login | Registrieren]

Neues Thema | Antworten   

Autor Beitrag
Thoro
Mitglied
Exzellenter User


Dabei seit: 29.09.2008
Herkunft: keine Angabe
Posts: 1126
     Gewichteter Zufall bei diskreten Werten Zitat | Bearbeiten

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 
1:
2:
3:
4:
5:
6:
7:
8:
<?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 
1:
2:
3:
<?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 
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
<?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.


Leidenschaftlicher Rechtschreibfehler-Sammler sucht mehrere Lagerhallen zwecks Erweiterung der Sammlung. Bis zur Vergrößerung der Lagerkapazitäten bitte möglichst keine Rechtschreibfehler mehr posten. Danke.
17.11.2008, 14:21 Profil | PM | Homepage | E-Mail  
Gast


      Zitat | Bearbeiten

da eine auswertung abgebrochen wird wenn ein element in frage kommt und space linear vom anfang zum ende durchlaufen wird müsste die chance für ein in $space am anfang stehendes ereigniss höher sein als die chance für ein hinten im array gelegenes (return bricht ab).
auch besteht die chance, dass keine zahl gewählt wird was mit errval zwar deutlich gemacht wird aber einen wiederholten aufruf der funktion verursachen muss. dadurch kann der zahlenfindungsprozess im zufälligen worst case recht lange dauern. keine vorhersagbare laufzeit-.-


03.03.2011, 12:11  
Thoro
Mitglied
Exzellenter User


Dabei seit: 29.09.2008
Herkunft: keine Angabe
Posts: 1126
      Zitat | Bearbeiten

Zitat:
da eine auswertung abgebrochen wird wenn ein element in frage kommt und space linear vom anfang zum ende durchlaufen wird müsste die chance für ein in $space am anfang stehendes ereigniss höher sein als die chance für ein hinten im array gelegenes (return bricht ab).

Es ist unerheblich, ob ein Element am Anfang oder am Ende von $space steht. Es wird stets nur die Wahrscheinlichkeit berücksichtigt, die in $space für das jeweilige Element angegeben wurde. Die Schleife wird lediglich deshalb vorzeitig abgebrochen, weil es unsinnig wäre, sie fortzuführen, obwohl das gesuchte Element bereits gefunden wurde.

Zitat:
auch besteht die chance, dass keine zahl gewählt wird was mit errval zwar deutlich gemacht wird aber einen wiederholten aufruf der funktion verursachen muss.

Die Rückgabe von $errval erfolgt ausschließlich dann, wenn sich die Wahrscheinlichkeiten, die mit $space übergeben wurden, nicht zu 1 addieren. Hat man dagegen $space wohl definiert, erhält man immer ein Element zurück und es besteht keinerlei Notwendigkeit die Funktion wiederholt aufzurufen.

Zitat:
dadurch kann der zahlenfindungsprozess im zufälligen worst case recht lange dauern. keine vorhersagbare laufzeit-.-

Der Algorithmus garantiert eine lineare Laufzeit (wie du im übrigen selbst zuvor anmerkst), auch im Worst Case.


Leidenschaftlicher Rechtschreibfehler-Sammler sucht mehrere Lagerhallen zwecks Erweiterung der Sammlung. Bis zur Vergrößerung der Lagerkapazitäten bitte möglichst keine Rechtschreibfehler mehr posten. Danke.
02.04.2011, 22:54 Profil | PM | Homepage | E-Mail  
Seiten (1):  1 
PHP-Support.de » Programmierung » PHP & MySQL » Codeschnipsel » Gewichteter Zufall bei diskreten Werten   

Neues Thema | Antworten   


Powered by Command Board 1.0 - Beta 2.0 © 2004-08 PHP-Einfach | Impressum | Datenschutz