Wann sollte bei der gewichteten Zufallsauswahl Ersetzung oder Nicht-Ersetzung verwendet werden?

Gewichtete Zufallsauswahl: Ersatz vs. Nicht-Ersatz

Gewichtete Zufallsauswahl ist eine grundlegende Technik, die in verschiedenen Anwendungen verwendet wird. Dabei werden Elemente aus einer gegebenen Liste mit Wahrscheinlichkeitsverteilungen ausgewählt, die durch bestimmte Gewichtungen bestimmt werden. Bei der Auswahl von Elementen mit Ersetzung kann jedes Element mehrfach ausgewählt werden, was zu einer höheren Wahrscheinlichkeit führt, dass Elemente mit höherem Gewicht ausgewählt werden. Im Gegensatz dazu schränkt die Auswahl ohne Ersetzung die Auswahl eines Elements ein, sobald es ausgewählt wurde.

Es kann eine Herausforderung sein, effiziente Algorithmen für die gewichtete Zufallsauswahl zu finden, insbesondere mit Ersetzung. Bestehende Methoden, einschließlich modifizierter Reservoir-Algorithmen, erweisen sich für die Auswahl signifikanter Fraktionen aus kleinen Listengrößen als ungeeignet.

Ein effizienter Ansatz: Alias-Methode

Ein Ansatz, der in diesem Szenario hervorragend ist ist die Alias-Methode. Diese Technik erstellt einen strukturierten Satz von Bins, die jeweils einen Teil der gewichteten Liste darstellen. Durch die Verwendung von Bitoperationen können die Bins effizient indiziert werden, wodurch binäre Suchen vermieden werden. Jeder Behälter enthält zwei Elemente aus der ursprünglichen Liste, was eine effiziente Darstellung der Verteilung ermöglicht.

Betrachten Sie beispielsweise eine Liste mit fünf gleichgewichteten Auswahlmöglichkeiten: (a:1, b:1, c:1, d: 1, e:1). Die Alias-Methode erstellt einen Satz von acht Bins mit jeweils einer Wahrscheinlichkeitsmasse von 0,125.

1. Normalisierung: Passen Sie die Gewichte so an, dass sie eine Summe von 1,0 ergeben. In diesem Fall (a:0,2 b:0,2 c:0,2 d:0,2 e:0,2).
2. Partition: Ordnen Sie beginnend Behälter mit Gewichten zu, die niedriger als die Partitionswahrscheinlichkeit (0,125) sind mit dem geringsten Gewicht. Hier (p1{a|null,1.0},p2,p3,p4,p5,p6,p7,p8).
3. Füllen: Füllen Sie den verbleibenden Platz in der Partition mit dem höchsten Wert Gewichtsvariable. Zum Beispiel (p1{a|null,1.0},p2{a|b,0.6},p3,p4,p5,p6,p7,p8).

Laufzeitauswahl:

Zur Laufzeit generieren wir eine Zufallszahl und verwenden Bitoperationen, um den der Wahrscheinlichkeitsverteilung entsprechenden Bin effizient zu bestimmen. Wenn die Bin geteilt ist, verwenden wir den Dezimalteil der Zufallszahl, um zwischen den beiden Elementen in der Bin auszuwählen.

Zusammenfassend bietet die Alias-Methode eine effiziente Technik für die gewichtete Zufallsauswahl mit Ersetzung. Es nutzt Bitoperationen für eine schnelle Bin-Indizierung und erreicht genaue Wahrscheinlichkeitsverteilungen durch sorgfältige Aufteilung der Gewichte in überschaubare Bins.

Das obige ist der detaillierte Inhalt vonWann sollte bei der gewichteten Zufallsauswahl Ersetzung oder Nicht-Ersetzung verwendet werden?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!