Erzeugen Einer Gewichteten Zufallszahl
Ich versuche zu kommen mit einem (guten) Weg zu wählen, eine zufällige Zahl aus einer Reihe von zahlen, wobei jede Zahl in der Reihe ist, da ein Gewicht. Um es einfach zu sagen: angesichts der Vielfalt der zahlen (0,1,2) wählen Sie eine Zahl 0 hat eine 80% Wahrscheinlichkeit hat, ausgewählt zu werden, 1 hat eine 10% chance und 2 hat eine 10% chance.
Es ist schon über 8 Jahre her, seit meinen college-stats-Klasse, so können Sie sich vorstellen, die richtige Formel für diese entgeht mir im moment.
Hier ist die "billige und schmutzige" Methode, die ich kam mit. Diese Lösung verwendet ColdFusion. Möglicherweise ist deine verwenden, was auch immer Sprache, die Sie möchten. Ich bin Programmierer, ich denke, ich kann damit umgehen Portierung. Letztlich ist meine Lösung muss in Groovy - ich schrieb ein, die in ColdFusion, weil es einfach schnell schreiben/test im VGL.
public function weightedRandom( Struct options ) {
var tempArr = [];
for( var o in arguments.options )
{
var weight = arguments.options[ o ] * 10;
for ( var i = 1; i<= weight; i++ )
{
arrayAppend( tempArr, o );
}
}
return tempArr[ randRange( 1, arrayLen( tempArr ) ) ];
}
//test it
opts = { 0=.8, 1=.1, 2=.1 };
for( x = 1; x<=10; x++ )
{
writeDump( weightedRandom( opts ) );
}
Ich bin auf der Suche nach besseren Lösungen, bitte Verbesserungsvorschläge oder alternativen.
InformationsquelleAutor Todd Sharp | 2011-12-08
Du musst angemeldet sein, um einen Kommentar abzugeben.
Rejection sampling (wie in deiner Lösung), ist die erste Sache, die kommt sich zu kümmern, wobei Sie bauen eine lookup-Tabelle mit Elementen aufgefüllt, die durch Ihre Gewichtsverteilung, dann wähle eine zufällige Position in der Tabelle und gibt es zurück. Als eine Implementierung Wahl, würde ich einen höheren Ordnung, die Funktion, die ein spec und gibt eine Funktion, die Werte zurückgibt, basierend auf der Verteilung in der spec, auf diese Weise vermeiden Sie, dass zum erstellen der Tabelle für jeden Anruf. Die Nachteile sind, dass die Algorithmische Leistung der Aufbau der Tabelle ist linear von der Anzahl der Elemente und könnte es möglicherweise sein, viel Speicher für große specs (oder die mit-Mitglieder mit sehr kleinen oder genaue GEWICHTE, z.B. {0:0.99999, 1:0.00001}). Der Vorteil ist, dass die Kommissionierung einen Wert hat die Konstante Zeit, die vielleicht wünschenswert sein, wenn die Leistung entscheidend ist. In JavaScript:
Andere Strategie ist, um eine zufällige Zahl in
[0,1)
und Iteration über die Gewicht-Spezifikation, Summierung der GEWICHTE, wenn die Zufallszahl kleiner ist als die Summe dann wieder den zugehörigen Wert. Natürlich, dies setzt Voraus, dass die GEWICHTE summieren sich zu eins. Diese Lösung hat keine up-front Kosten, aber hat eine Durchschnittliche Algorithmische performance linear mit der Anzahl der Einträge in der spec. Zum Beispiel in JavaScript:Beachten Sie, dass Sie können speichern ein array mit Angabe der kumulativen Summen, dh es einmal tun, und verwenden Sie dann eine
log n
binäre Suche jedes mal, wenn Sie das erzeugen einer Zahl. Aber das macht nur Sinn für große n.Wenn ich die Funktion mit diesen Parametern arr = {0:0.1, 1:0.7, 2:0.9} 10000 mal, es gibt mir folgende Ausgabe : 0 : 983 , 1 : 7011 und 2 : 2006 was ist alles falsch, denn 2 hat mehr Wahrscheinlichkeit als 1 beim Ausgang suggerieren etwas anderes.
Hey nur ein kurzer check mit Euch, nicht die Summe der GEWICHTE muss genau 1? Ich habe versucht, diese weightedRand({0:0.350, 1:0.200, 2:0.010, 3:0.150 , 4:0.010, 5:0.200, 6:0.150 }); aber ich habe gemerkt, dass Nummer 4 kommt oft eine sehr große Anzahl
ja, die Summe der GEWICHTE muss eins sein und für diejenigen, die GEWICHTE, die Sie brauchen, um verwenden Sie die Konstante mit dem Wert 1000 statt 10.
InformationsquelleAutor maerics
Erzeugen einer Zufallszahl R zwischen 0 und 1.
Wenn f in [0, 0.1) -> 1
Wenn R in [0.1, 0.2) -> 2
Wenn R in [0.2, 1] -> 3
Wenn Sie nicht direkt eine Zahl zwischen 0 und 1, zu erzeugen, eine Zahl in einem Bereich zu erzeugen, so viel Genauigkeit, wie Sie wollen. Zum Beispiel, wenn Sie die GEWICHTE für
(1, 83.7%) und (2, 16.3%), roll eine Zahl von 1 bis 1000. 1-837 ist eine 1. 838-1000 ist 2.
Ein Freund von mir kam mit dieser Variante dieses Ansatzes: return Math.random() < 0.8 ? 0 : ( Math.random() < 0.9 ? 1 : 2 );
Ich würde nicht empfehlen, es sei denn, Sie sind den Umgang mit bedingten probablities, welche Modelle am besten.
Ich weiß, es ist uralt, aber ... würden Sie wirklich wollen, verwenden Sie die gleichen Zufallszahlen, oder Sie bekommen einen bias: r = Math.random(); return (r < 0.8) ? 0 : (r<.9) ? 1 : 2. In Ihrem code, '2' würde nur zurückgegeben werden, wenn r1>=.8 UND r2>=.9, 10%, 20% oder 2% der Fälle.
InformationsquelleAutor Thomas Eding
Dies ist mehr oder weniger ein generic-ized version von dem, was @trinithis schrieb, in Java: ich habe es mit ints statt floats zu vermeiden, chaotisch Rundungsfehler.
InformationsquelleAutor Greg Case
Hier sind 3 Lösungen in javascript, da ich nicht sicher bin, welche Sprache Sie wollen es in. Je nach Ihren Bedürfnissen, eines der ersten beiden funktionieren könnte, aber der Dritte ist wahrscheinlich am einfachsten zu implementieren, die mit großen Mengen von zahlen.
InformationsquelleAutor qw3n
Wie etwa
int [ ] zahlen = { 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 2 } ;
dann Sie können nach dem Zufallsprinzip wählen Sie aus zahlen und 0 haben eine 80% - chance, 1 von 10%, und 2 10%
InformationsquelleAutor emory
Verwende ich die folgenden
Dies ist mein gehe-zu "gewichtet" zufällig, wo ich eine inverse Funktion von "x" (wobei x für eine random zwischen min und max) zur Erzeugung eines gewichteten Ergebnisses, wo das minimum ist die meisten schweren element, und das maximum, das die leichteste (am wenigsten Chancen das Ergebnis)
Also im Grunde, mit
weightedRandom(1, 5)
bedeutet, dass die Chancen, eine 1 höher als 2, die höher sind als 3, die höher sind als 4, die höher sind als 5.Möglicherweise nicht nützlich sein, für deinen Anwendungsfall aber wohl sinnvoll für Leute googeln das gleiche Frage stellen.
Nach 100 Iterationen versuchen, es mir gab:
weightedRandom(50, 100)
aber noch erhalten 1s und solche, offensichtlich habe ich den Punkt verpasst.ein paar Dinge: (1) dieser Ansatz ist sehr spezifisch, da gibt es ein enormes Gewicht (Priorität) , die niedrigsten zahlen, die in der Nähe
f(x)=1/x
... (2) gegeben, verwendet es zufällig, es gibt keine Garantie, es wird mindestens einmal jede Zahl... und (3) last but not least, sollten Sie49 + weightedRandom(1, 51)
wenn Sie möchten, zu bekommen, zahlen zwischen 50 und 100Duh
49 + weightedRandom(1, 51)
ist eine so offensichtliche Lösung. Danke.InformationsquelleAutor Tom Roggero
Diese ist in Mathematica, aber es ist leicht zu kopieren auf eine andere Sprache, ich benutze es in meine Spiele und es kann mit dezimal-GEWICHTE:
(Jetzt Rede ich mit einem Listen erste element ist index gleich 0) Die Idee dahinter ist, dass eine normierte Liste GEWICHTE es ist eine chance GEWICHTE[n] Rückkehr der index n, so die Abstände zwischen den min-und max bei Schritt n sollte GEWICHTE[n]. Die gesamte Entfernung vom minimum min (was setzen wir es auf 0 sein) und die maximale max ist die Summe der Liste GEWICHTE.
Die gute Sache dahinter ist, dass Sie nicht Anhängen, um ein array oder nest für loops, und das erhöht stark die Ausführungszeit.
Hier ist der code in C#, ohne zu normalisieren, die GEWICHTE Liste, und löschen Sie einige code:
InformationsquelleAutor Garmekain
hier ist der Eingang und die Verhältnisse : 0 (80%), 1(10%) , 2 (10%)
können zeichnen Sie aus, so dass seine leicht zu visualisieren.
können hinzufügen, bis das Gesamtgewicht und nennen es TR für die gesamtkennziffer. also in diesem Fall 100.
können nach dem Zufallsprinzip Holen Sie sich eine Zahl aus (0-TR) oder (0 bis 100 in diesem Fall) . 100 wird Ihre Summe GEWICHTE. Rufen Sie RN für Zufallszahl.
so, jetzt haben wir TR als Summe Gewicht und RN als die Zufallszahl, die zwischen 0 und TR.
so können sich vorstellen, wählten wir eine random # von 0 bis 100. Sagen 21. so das Wars eigentlich 21%.
MÜSSEN WIR KONVERTIEREN/PASSEN DIESE ZU UNSEREM EINGANG ZU ZAHLEN, ABER WIE ?
können Schleife über jedes Gewicht (80, 10, 10) und halten Sie die Summe der GEWICHTE, die wir bereits besuchen.
der moment, die Summe der GEWICHTE, die wir Durchlaufen, ist größer als die Zufallszahl RN (21 in diesem Fall), wir beenden die Schleife & return, element position.
können sagen, dass die zufällige Zahl (zwischen 0 und 100), 83. Können tun Sie es wieder:
InformationsquelleAutor j2emanue
Habe ich ein Automat, und ich verwendete den folgenden code um Zufallszahlen zu generieren. In probabilitiesSlotMachine die Tasten sind, wird die Ausgabe in den Automat, und die Werte repräsentieren das Gewicht.
Nun zum generieren einer zufälligen Ausgang, ich benutze diesen code:
InformationsquelleAutor J. Doe