Wie führt man eine effiziente gewichtete Zufallsauswahl mit und ohne Ersatz durch?

Gewichtete Zufallsauswahl mit und ohne Ersatz

Als Reaktion auf eine Programmierherausforderung suchen wir nach effizienten Algorithmen für die gewichtete Zufallsauswahl aus einer Liste. sowohl mit als auch ohne Ersetzung.

Gewichtete Auswahl mit Ersetzung

Eine effektive Methode zur gewichteten Auswahl mit Ersetzung ist die Alias-Methode. Diese Technik erstellt für jedes gewichtete Element einen Satz gleich großer Bins. Durch die Verwendung von Bitoperationen können wir diese Bins effizient indizieren, ohne auf die binäre Suche zurückgreifen zu müssen. In jedem Bin wird ein einzelner Prozentsatz gespeichert, der die Grenze zwischen den ursprünglich gewichteten Elementen darstellt.

Betrachten Sie das Beispiel von fünf Elementen mit gleichen Gewichten: (a, b, c, d, e).

Implementierung der Alias-Methode

1. Gewichte normalisieren: Teilen Sie jedes Gewicht durch die Summe, um 1,0 zu ergeben.
2. Bestimmen Sie die kleinste Potenz von 2, die größer oder gleich der Zahl ist Anzahl der Elemente (hier 8).
3. Weisen Sie jedem Element eine leere Partition zu.

4. Wiederholen Sie die folgenden Schritte, bis alle Gewichte verteilt sind:

   • Platzieren Sie so viel des Elements mit dem geringsten verbleibenden Gewicht in einer leeren Trennwand.
   • Wenn eine Trennwand nicht gefüllt ist, fügen Sie das schwerste verbleibende Element hinzu.

Für unser Beispiel haben wir nach mehreren Iterationen die folgende Partition:

• p1: {a, 1.0}
• p2: {a, b, 0.6}

Laufzeitauswahl

1. Generieren Sie eine Zufallszahl zwischen 0 und 1.
2. Bitshiften Sie die Zufallszahl, um den Partitionsindex zu finden.
3. Wenn die Partition geteilt ist, verwenden Sie den Dezimalteil der bitverschobenen Zahl, um zu entscheiden, welches Element zurückgegeben werden soll.

Gewichtete Auswahl ohne Ersatz

While-Algorithmen So wie es die Methode des gewichteten Reservoirs für eine ungewichtete Auswahl ohne Ersatz gibt, bleibt dieses Problem ungelöst.

Das obige ist der detaillierte Inhalt vonWie führt man eine effiziente gewichtete Zufallsauswahl mit und ohne Ersatz durch?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!