Wie generiert man gewichtete Zufallszahlen: Ablehnungsstichprobe vs. iterative Gewichtssummierung?

Gewichtete Zufallszahl generieren

Einführung

In verschiedenen Anwendungen ist dies häufig erforderlich Wählen Sie eine Zufallszahl aus einer Reihe von Optionen aus, wobei jeder Option eine bestimmte Wahrscheinlichkeit zugewiesen wird, dass sie ausgewählt wird. Dieses Konzept wird als Generierung einer gewichteten Zufallszahl bezeichnet.

Rejection-Sampling-Ansatz

Eine Methode zur Generierung gewichteter Zufallszahlen ist die Ablehnungsstichprobe. Bei diesem Ansatz wird eine Nachschlagetabelle erstellt, in der jede Option so oft vorkommt, wie ihr Gewicht zugewiesen ist. Wenn Option A beispielsweise eine Wahrscheinlichkeit von 80 % hat, würde sie 80 Mal in der Nachschlagetabelle erscheinen. Um eine Zufallszahl zu generieren, wird eine zufällige Stelle in der Tabelle ausgewählt und die entsprechende Option zurückgegeben.

Vor- und Nachteile der Ablehnungsstichprobe

Die Ablehnungsstichprobe liefert eine Konstante -Zeitleistung für die Auswahl einer Zufallszahl nach der Erstellung der Nachschlagetabelle. Es erfordert jedoch eine lineare Algorithmusleistung zum Erstellen der Tabelle, was bei großen Optionsmengen oder solchen mit hochpräzisen Gewichtungen problematisch sein kann.

Iterativer Gewichtungssummierungsansatz

Ein alternativer Ansatz ist die iterative Gewichtssummierung. Hier wird eine Zufallszahl im Bereich [0,1) generiert und mit der kumulierten Summe der Gewichte verglichen. Die Option, die dem Gewicht zugeordnet ist, das die Zufallszahl überschreitet, wird als gewichtete Zufallszahl ausgewählt.

Vor- und Nachteile der iterativen Gewichtssummierung

Im Vergleich zur iterativen Ablehnungsstichprobe Die Gewichtungssummierung verursacht keine Vorlaufkosten, weist jedoch eine lineare durchschnittliche algorithmische Leistung im Verhältnis zur Anzahl der Optionen im Satz auf. Es wird außerdem davon ausgegangen, dass sich die Gewichte auf eins summieren.

Überlegungen zur Implementierung

Bei der Implementierung dieser Ansätze wird empfohlen, eine Funktion höherer Ordnung zu erstellen, die eine Spezifikation von Gewichten benötigt und gibt eine Funktion zurück, die gewichtete Zufallszahlen generiert. Dies ermöglicht die Wiederverwendbarkeit und vermeidet den Aufwand, die Nachschlagetabelle zu erstellen oder die Gewichtungen mehrfach zu akkumulieren.

Das obige ist der detaillierte Inhalt vonWie generiert man gewichtete Zufallszahlen: Ablehnungsstichprobe vs. iterative Gewichtssummierung?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!