linux|n00b Linux für Ein- und Umsteiger

25Mai/110

Gewichtete Zufallsauswahl eines Arrayelements

Weil ich das schon Ewigkeiten mal "zu Papier" bringen wollte, habe ich heute mal eine Angelegenheit in Sachen Webprogrammierung mit PHP.

array_rand

Aus einem Array ein Element zufällig auszuwählen, ist mit PHP-Bord-Mitteln denkbar einfach.

$randomKey = array_rand($anyArray);
$randomElement = $anyArray[$randomKey];

dw_rand

Jedoch hat dabei jedes Element die gleiche Ziehungswahrscheinlichkeit. Schon vor einiger Zeit fand ich diese Lösung, um die Auswahl gewichten zu können.

Was diese Lösung nicht kann

Die dort vorgestelle PHP-Funktion dw_rand ist schon mal ein guter Anfang. Mein einziges Problem, welches ich damit nun noch habe, ist, dass ich im Vorhinein nicht weiß, wie die Wahrscheinlichkeiten bestimmt sind. Diese sollen sich aus den Arrayelementen selbst ergeben und nicht explizit vorgegeben sein, so wie es die Funktion dw_rand erfordert.

Wie ich das meine? Vielleicht kann folgendes Beispiel das ein wenig verdeutlichen.

Anwendungsbeispiel

Angenommen wir betreiben einen Internet-Shop, bei dem es auch mal einen Artikel zu gewinnen gibt. Nun soll aus einem Teil der Produktpalette zufällig ein Produkt gelost und als Gewinn verschenkt werden. Aber teure Produkte sollen eine geringere Wahrscheinlichkeit erhalten als die preisgünstigeren Produkte, so dass letztere häufiger ausgelost werden.
(Zugegebenermaßen ist mein eigener Anwendungsbereich ein etwas anderer, aber als Beispiel kann dies trotzdem dienen, hoffe ich.)

Veranschaulichen wir das mal mit ein wenig Quellcode. Wir nehmen an, wir haben zur Laufzeit folgendes Array:

$products = array(
    array(                //  im echten Programmierumfeld wäre dies dann eher ein Objekt der Klasse Product und kein Array
        'id' => 123,      //  ID des Produkts
        'cost' => 500     //  Kosten des Produkts
    ),
    array(
        'id' => 456,
        'cost' => 100
    ),
    array(
        'id' => 789,
        'cost' => 200
    )
);

Aus diesen drei Produkten soll nun je nach Preis eines zufällig ausgewählt werden. Das Produkt mit der ID 456 soll dabei am häufigsten gewählt werden, da es am günstigsten ist.

Da müssen wir noch was machen...

Die Funktion dw_rand benötigt für die Häufigkeitsverteilung aber keine ganzzahligen Preise, sondern Fließkommazahlen zwischen 0.0 und 1.0 (für Prozentwerte von 0% bis 100%).

Ansatz

Was wir brauchen, ist eine Art Umkehrwert der Kostenangaben für die Produkte. Hier reicht es allerdings nicht, einfach nur 1/x zu rechnen, denn die resultierenden Wahrscheinlichkeiten sollen ja in Summe genau 1.0 (für 100%) ergeben. Ich möchte die Erläuterungen an dieser Stelle einfach abkürzen und sogleich die Lösung präsentieren (nicht zuletzt, weil ich den Quellcode bereits recht ausführlich dokumentiert habe).

Lösung

<?php

class RandomUtil {

	/**
	 * Gibt ein zufällig gewähltes Element aus einem Array zurück.
	 *
	 * Wird ausschließlich das Array übergeben, gibt es keine bevorzugten Elemente im Array.
	 * Es wird einfach ein Element nach Gleichverteilung aller Elemente ausgewählt.
	 *
	 * Wird neben dem Array zusätzlich der optionale Parameter $fieldWithRarity übergeben,
	 * so wird gewichtet ausgewählt. Je höher die Rarität, desto geringer die Gewichtung bei
	 * der zufälligen Auswahl und umgekehrt. Elemente im Array mit niedriger Rarität, also
	 * mit höherer Gewichtung, werden statistisch häufiger ausgewählt.
	 *
	 * @param $array Array mit Elementen, von denen eins zufällig gewählt werden soll
	 * @param $fieldWithRarity Feld mit Rarität/Seltenheitswert in den Elementen des Arrays
	 * @return zufälliges Element des übergebenen Arrays oder NULL, wenn das Array leer ist
	 */
	public static function getRandomArrayElement($anyArray, $fieldWithRarity = null) {
		if (empty($anyArray)) {
			return null;
		}

		if (empty($fieldWithRarity)) {
			$randKey = array_rand($anyArray);
		} else {
			$probArray = self::getProbabilitiesArray($anyArray, $fieldWithRarity);
			$randKey = self::dw_rand($probArray);
		}

		return $anyArray[$randKey];
	}

	/**
	 * Gibt ein Array mit Wahrscheinlichkeitswerten zurück. Diese werden von dw_rand benötigt.
	 */
	private static function getProbabilitiesArray(array $anyArray, $fieldWithRarity) {
		if (empty($fieldWithRarity)) {
			throw new Exception('Es muss das Feld mit dem Raritätswert angegeben werden');
		}

		//	Array mit Wahrscheinlichkeiten (wird gleich befüllt, zunächst Erläuterung an Beispiel)
		$probabilities = array();

		/*
			BEISPIEL:
			 Produkt-Objekte mit Gewichtung auf das Feld 'cost', das ist der Raritätswert

			Situation:
			 Wir haben Produkte, die Geld kosten. Von allen Produkten soll eines zufällig
			 ausgewählt werden. Allerdings sollen die günstigen Produkte wahrscheinlicher
			 und die teuren Produkte unwahrscheinlicher sein (bzw. häufiger und seltener).
			 Mit den Kosten der Produkte als Grundlage zum Ermitteln von Wahrscheinlich-
			 keiten ergibt sich folgender Rechenweg.

			(1) - Kosten
			 K_Prod1 = 30.000
			 K_Prod2 = 50.000
			 K_Prod3 = 40.000
			 SUMME = 120.000

			(2) - Kostenverhältnisse
			 R_Prod1 = 120k / 30k = 4
			 R_Prod2 = 120k / 50k = 2,4
			 R_Prod3 = 120k / 40k = 3

			(3) - Faktor
			 SUMME_VERHAELTNISSE = 4 + 2,4 + 3 = 9,4
			 FAKTOR = 1 / 9,4 = 0,106382979

			(4) - Wahrscheinlichkeiten
			 P_Prod1 = 0,106382979 * 4 = 0,425531916
			 P_Prod2 = 0,106382979 * 2,4 = 0,25531915
			 P_Prod3 = 0,106382979 * 3 = 0,319148937

			(-->) folgendes Array käme dabei heraus
			 array(
				'1' => 0.425531916,
				'2' => 0.25531915,
				'3' => 0.319148937
			 );
		*/

		//	(1) - Einzel- und Gesamtkosten ermitteln und in das Wahrscheinlichkeits-Array stecken
		$costSum = 0;
		foreach ($anyArray as $key => $element) {
			$rarity = $element[$fieldWithRarity];

			if ($rarity >= 0)  {
				$costSum += $rarity;
				$probabilities[$key] = $rarity;
			}
		}

		//	(2) - Verhältnis von Gesamtkosten zu Einzelkosten bilden und ins Wahrsch.-Array stecken
		foreach ($probabilities as $key => $cost) {
			$probabilities[$key] = $costSum / $cost;
		}

		//	(3) - Faktor ermitteln, mit dem wir die Kostenverhältnisse in Summe auf 1 bekommen (Dreisatz)
		$ratioSum = 0;
		foreach ($probabilities as $ratio) {
			$ratioSum += $ratio;
		}
		$factor = 1 / $ratioSum;

		//	(4) - die endgültigen Wahrscheinlichkeiten errechnen (Dreisatz Fortsetzung)
		foreach ($probabilities as $key => $ratio) {
			$probabilities[$key] = $factor * $ratio;
		}

		//	Wahrscheinlichkeiten zurück geben
		return $probabilities;
	}

	/**
	 * @see http://rotering-net.de/tut/php-dwrand.html
	 */
	private static function dw_rand($space, $errval = false) {
		$res = 1000000000;
		$rn = mt_rand(0, $res - 1);
		$psum = 0;

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

		return $errval;
	}
}

Verwendung

Aus unserem Produkte-Array bestehend aus Product-Instanzen (bzw. aus Sub-Arrays zur Veranschaulichung) lässt sich nun wie folgt ein Element zufällig, gewichtet nach Kosten auswählen:

$randomProduct = RandomUtil::getRandomArrayElement($products, 'cost');

Einfach, oder? Ich hoffe, diese (für mich schon seit Längerem hilfreiche) Klasse kann auch euch da draußen dienlich sein. Mir war und ist sie es - in diesem Sinne auch meinen Dank an Thorsten Rotering für seine dw_rand-Funktion!