Wie können wir eine gewichtete Zufallsauswahl mit und ohne Ersatz implementieren?

Gewichtete Zufallsauswahl mit und ohne Ersetzung: Ein umfassender Leitfaden

Das Auswählen von Elementen aus einer Liste mit bestimmten Gewichtungen kann in verschiedenen Bereichen eine wertvolle Technik sein Anwendungen. Während die gewichtete Auswahl ohne Ersetzung über gut etablierte Algorithmen verfügt, stellt die Auswahl von Elementen mit Ersetzung eine andere Herausforderung dar.

Eine effiziente Methode zur gewichteten Auswahl mit Ersetzung ist die Alias-Methode. Durch die Normalisierung der Gewichtungen auf eine Summe von 1,0 und das Ermitteln der kleinsten Potenz von 2, die größer als die Anzahl der Auswahlmöglichkeiten ist, können Partitionen für jede Variable erstellt werden. Die Methode füllt Partitionen iterativ mit den am wenigsten und am stärksten gewichteten Variablen und weist bei Bedarf die verbleibende Gewichtung der ursprünglichen Partition zu.

Zur Laufzeit wird eine einheitliche Zufallszahl generiert und deren binäre Darstellung um den Logarithmus von verschoben die Anzahl der Partitionen. Der Index der ausgewählten Partition wird durch die verschobene Nummer bestimmt. Wenn die Partition geteilt ist, bestimmt der Dezimalteil der verschobenen Zufallszahl die Auswahl zwischen den beiden Variablen, die dieser Partition zugewiesen sind.

Die Alias-Methode ist für ihre Effizienz bekannt und basiert auf einfachen algebraischen Operationen und konstanter Zeit Indizierung. Es ermöglicht eine effiziente Auswahl, selbst wenn ein erheblicher Teil der Liste ausgewählt werden muss, was es zu einer geeigneten Wahl für verschiedene Szenarien macht, in denen eine gewichtete Zufallsauswahl mit Ersetzung erforderlich ist.

Das obige ist der detaillierte Inhalt vonWie können wir eine gewichtete Zufallsauswahl mit und ohne Ersatz implementieren?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!