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 für die gewichtete 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 eine 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).

Alias-Methodenimplementierung

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 von Elementen (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 Partition.
   • Wenn eine Partition 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.