Python verwendet gewichtete Zufallszahlen, um Explosionen bei Lotterien und Spielgeräten zu lösen

Über gewichtete Zufallszahlen

Um das zu verstehen, schauen wir uns zunächst den Vergleich von drei Arten von Zufallsproblemen an:
1. Es gibt n Datensätze Von diesen m Datensätzen spielt die Reihenfolge der ausgewählten Datensätze keine Rolle.
Implementierungsidee: Durchlaufen Sie alle Datensätze zeilenweise und nehmen Sie ein Datenelement im Abstand von etwa n/m
2. Bei Typ 1 ist es außerdem erforderlich, dass die ausgewählten m Datensätze zufällig sortiert werden
Implementierungsidee: Fügen Sie jedem der n Datensätze eine Markierungsspalte hinzu, und die Werte sind zufällig ausgewählte, nicht doppelte Daten zwischen 1 und n.
3. Anders als bei Problemen vom Typ 1 und 2: Wenn die Datensätze Gewichtungen haben, wie werden diese anhand der Gewichtungen zufällig ausgewählt? Wenn beispielsweise die Gewichtung von A 10, die Gewichtung von B 5 und die Gewichtung von C 1 beträgt, sollte AABB wahrscheinlich erscheinen, wenn 4 zufällig ausgewählt werden.
Die dritte Art von Fragen steht im Mittelpunkt dieses Artikels.
Umsetzungsidee: Nehmen Sie als Beispiel 4 zufällig ausgewählte Datensätze aus A:10, B:5, C:1 (es spielt keine Rolle, ob sie nach Gewicht sortiert sind)
Für
A 10
B 5
C 1
Zuerst weisen Sie den Wert der n-ten Zeile der n-ten Zeile plus der n-1-ten Zeile zu und führen ihn wie folgt rekursiv aus:
A 10
B 15
C 16
Wählen Sie dann jedes Mal zufällig eine Zahl aus [1,16] aus. Wenn sie zwischen [1,10] liegt, wählen Sie A. Wenn sie zwischen (10,15] liegt, wählen Sie B. Wenn sie liegt zwischen (16) ,16], wählen Sie C. Wie in der Abbildung unten gezeigt, hat jeder, der ein größeres Intervall (höheres Gewicht) einnimmt, eine größere Wahrscheinlichkeit, ausgewählt zu werden 🎜>

Bewerbung in der Lotterie und Spiel-Sprengstoffausrüstung

Vorgang nach Bedarf, um die Wahrscheinlichkeit des Erscheinens jedes Gegenstands zu konfigurieren.
Die Idee von Der gewichtete Zufallsalgorithmus, über den wir heute sprechen werden, ist sehr einfach, das heißt: „Alle Elemente werden entsprechend ihrer Gewichtung zu Intervallen geformt, und die Intervalle mit größeren Gewichten sind größer. Man kann es sich dann als Kreisdiagramm vorstellen.“ , würfeln Sie, um zu sehen, in welchen Bereich es fällt: „

Das vom Veranstalter konfigurierte Gewicht ist [(' iphone', 10), ('ipad', 40), ('itouch', 50)].Die Idee kann mit einer Codezeile erklärt werden, nämlich random.choice(['iphone']* 10 + ['ipad']*40 + ['itouch']*50).
Nachfolgend schreiben wir es als allgemeine Funktion.






Der obige Code ist intuitiv genug. Wenn Sie jedoch vorsichtig sind, werden Sie feststellen, dass die Summe jedes Mal berechnet wird und das Intervall jedes Mal zur Subtraktion linear durchlaufen wird Verwenden Sie zuerst die binäre Suche „akkumulieren + halbieren“. Je mehr Elemente vorhanden sind, desto offensichtlicher ist die Leistungsverbesserung 🎜>

#coding=utf-8 
import random 
def weighted_random(items): 
  total = sum(w for _,w in items) 
  n = random.uniform(0, total)#在饼图扔骰子 
  for x, w in items:#遍历找出骰子所在的区间 
    if n<w: 
      break 
    n -= w 
  return x 
 
print weighted_random([(&#39;iphone&#39;, 10), (&#39;ipad&#39;, 40), (&#39;itouch&#39;, 50)])