Wahrscheinlichkeitsverteilung in Python
https://stackoverflow.com/questions/526255
-
22-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Ich habe eine Reihe von Tasten, die jeweils eine Unwahrscheinlichkeit Variable haben. Ich möchte nach dem Zufallsprinzip einen dieser Tasten wählen, aber ich mag es unwahrscheinlicher für unwahrscheinlich (Schlüssel, Werte) gewählt werden, als ein weniger unwahrscheinlich (ein eher) Objekt. Ich frage mich, wenn Sie irgendwelche Vorschläge haben würden, vorzugsweise ein vorhandenes Python-Modul, das ich verwenden könnte, was ich muß es selbst machen.
Ich habe das Zufalls Modul ausgecheckt; es scheint nicht, diese zu liefern.
muss ich solche Entscheidungen viele Millionen Mal für 1000 verschiedene Gruppen von Objekten mit jeweils 2.455 Objekte. Jeder Satz wird Objekte untereinander austauschen, um die Zufallsauswahl dynamisch sein muss. Mit 1000 setzt von 2.433 Objekten ist, dass 2.433 Millionen Objekte; geringer Speicherplatzverbrauch ist entscheidend. Und da diese Entscheidungen nicht der Großteil des Algorithmus sind, muss ich diesen Prozess sehr schnell sein; CPU-Zeit ist begrenzt.
Thx
Update:
Ok, habe ich versucht, Ihre Vorschläge mit Bedacht zu betrachten, aber die Zeit ist so begrenzt ...
Ich schaute auf dem binären Suchbaum Ansatz, und es scheint zu riskant (komplex und kompliziert). Die anderen Vorschläge alle ähneln den Activestate Rezept. Ich nahm es und modifiziert es ein wenig in der Hoffnung auf eine effizientere:
def windex(dict, sum, max):
'''an attempt to make a random.choose() function that makes
weighted choices accepts a dictionary with the item_key and
certainty_value as a pair like:
>>> x = [('one', 20), ('two', 2), ('three', 50)], the
maximum certainty value (max) and the sum of all certainties.'''
n = random.uniform(0, 1)
sum = max*len(list)-sum
for key, certainty in dict.iteritems():
weight = float(max-certainty)/sum
if n < weight:
break
n = n - weight
return key
Ich hoffe, von einem Effizienzgewinn erhalten dynamisch die Summe von Gewissheiten und die maximale Sicherheit aufrechterhalten wird. Weitergehende Vorschläge sind willkommen. Ihr Jungs erspart mir so viel Zeit und Mühe, während meine Wirksamkeit zu erhöhen, es ist verrückt. Vielen Dank! Vielen Dank! Thx!
Update2:
Ich beschloss, es durch effizienter gestalten lässt es sofort eine noch größere Auswahl zur Verfügung. Dies wird in einem akzeptablen Verlust an Präzision in meinem algo Ergebnis für sie dynamisch in der Natur. Wie auch immer, hier ist was ich jetzt habe:
def weightedChoices(dict, sum, max, choices=10):
'''an attempt to make a random.choose() function that makes
weighted choices accepts a dictionary with the item_key and
certainty_value as a pair like:
>>> x = [('one', 20), ('two', 2), ('three', 50)], the
maximum certainty value (max) and the sum of all certainties.'''
list = [random.uniform(0, 1) for i in range(choices)]
(n, list) = relavate(list.sort())
keys = []
sum = max*len(list)-sum
for key, certainty in dict.iteritems():
weight = float(max-certainty)/sum
if n < weight:
keys.append(key)
if list: (n, list) = relavate(list)
else: break
n = n - weight
return keys
def relavate(list):
min = list[0]
new = [l - min for l in list[1:]]
return (min, new)
Ich habe es noch nicht ausprobiert. Wenn Sie Kommentare / Anregungen haben, zögern Sie bitte nicht. Thx!
Update3:
Ich arbeite den ganzen Tag auf eine Aufgabe zugeschnittene Version von Rex Logan Antwort. Statt einen 2-Arrays von Objekten und Gewichten, ist es eigentlich eine spezielle Wörterbuch-Klasse; das macht die Sache ziemlich komplex, da Rex Code ein Zufallsindex erzeugt ... Ich habe auch einen Testfall codiert, die Art ähnelt dem, was in meinem algo passieren wird (aber ich kann nicht wirklich wissen, bis ich versuchen!). Das Grundprinzip ist: Je mehr ein Schlüssel zufällig häufig erzeugt wird, desto unwahrscheinlicher wird es wieder erzeugt werden:
import random, time
import psyco
psyco.full()
class ProbDict():
"""
Modified version of Rex Logans RandomObject class. The more a key is randomly
chosen, the more unlikely it will further be randomly chosen.
"""
def __init__(self,keys_weights_values={}):
self._kw=keys_weights_values
self._keys=self._kw.keys()
self._len=len(self._keys)
self._findSeniors()
self._effort = 0.15
self._fails = 0
def __iter__(self):
return self.next()
def __getitem__(self, key):
return self._kw[key]
def __setitem__(self, key, value):
self.append(key, value)
def __len__(self):
return self._len
def next(self):
key=self._key()
while key:
yield key
key = self._key()
def __contains__(self, key):
return key in self._kw
def items(self):
return self._kw.items()
def pop(self, key):
try:
(w, value) = self._kw.pop(key)
self._len -=1
if w == self._seniorW:
self._seniors -= 1
if not self._seniors:
#costly but unlikely:
self._findSeniors()
return [w, value]
except KeyError:
return None
def popitem(self):
return self.pop(self._key())
def values(self):
values = []
for key in self._keys:
try:
values.append(self._kw[key][1])
except KeyError:
pass
return values
def weights(self):
weights = []
for key in self._keys:
try:
weights.append(self._kw[key][0])
except KeyError:
pass
return weights
def keys(self, imperfect=False):
if imperfect: return self._keys
return self._kw.keys()
def append(self, key, value=None):
if key not in self._kw:
self._len +=1
self._kw[key] = [0, value]
self._keys.append(key)
else:
self._kw[key][1]=value
def _key(self):
for i in range(int(self._effort*self._len)):
ri=random.randint(0,self._len-1) #choose a random object
rx=random.uniform(0,self._seniorW)
rkey = self._keys[ri]
try:
w = self._kw[rkey][0]
if rx >= w: # test to see if that is the value we want
w += 1
self._warnSeniors(w)
self._kw[rkey][0] = w
return rkey
except KeyError:
self._keys.pop(ri)
# if you do not find one after 100 tries then just get a random one
self._fails += 1 #for confirming effectiveness only
for key in self._keys:
if key in self._kw:
w = self._kw[key][0] + 1
self._warnSeniors(w)
self._kw[key][0] = w
return key
return None
def _findSeniors(self):
'''this function finds the seniors, counts them and assess their age. It
is costly but unlikely.'''
seniorW = 0
seniors = 0
for w in self._kw.itervalues():
if w >= seniorW:
if w == seniorW:
seniors += 1
else:
seniorsW = w
seniors = 1
self._seniors = seniors
self._seniorW = seniorW
def _warnSeniors(self, w):
#a weight can only be incremented...good
if w >= self._seniorW:
if w == self._seniorW:
self._seniors+=1
else:
self._seniors = 1
self._seniorW = w
def test():
#test code
iterations = 200000
size = 2500
nextkey = size
pd = ProbDict(dict([(i,[0,i]) for i in xrange(size)]))
start = time.clock()
for i in xrange(iterations):
key=pd._key()
w=pd[key][0]
if random.randint(0,1+pd._seniorW-w):
#the heavier the object, the more unlikely it will be removed
pd.pop(key)
probAppend = float(500+(size-len(pd)))/1000
if random.uniform(0,1) < probAppend:
nextkey+=1
pd.append(nextkey)
print (time.clock()-start)*1000/iterations, "msecs / iteration with", pd._fails, "failures /", iterations, "iterations"
weights = pd.weights()
weights.sort()
print "avg weight:", float(sum(weights))/pd._len, max(weights), pd._seniorW, pd._seniors, len(pd), len(weights)
print weights
test()
Jede Kommentare sind immer noch willkommen. @Darius: Ihre Binärbäumen sind zu komplex und zu kompliziert für mich; und ich glaube nicht, seine Blätter effizient entfernt werden können ... Thx alle
Lösung
Dieses Active Rezept einen einfach befolgende Ansatz gibt, und zwar die Version in dem Kommentare, die Sie nicht, vor der Normalisierung Ihre Gewichte benötigt:
import random
def weighted_choice(items):
"""items is a list of tuples in the form (item, weight)"""
weight_total = sum((item[1] for item in items))
n = random.uniform(0, weight_total)
for item, weight in items:
if n < weight:
return item
n = n - weight
return item
Dies wird langsam, wenn Sie eine große Liste von Elementen haben. Eine binäre Suche wäre wahrscheinlich besser, in diesem Fall ... aber auch komplizierter zu schreiben, für wenig Gewinn, wenn Sie eine kleine Stichprobengröße haben wäre. Hier ist ein Beispiel für den binären Suchansatz in Python wenn Sie diesem Weg folgen wollen.
(Ich würde empfehlen, ein paar schnellen Performance-Tests beiden Methoden auf dem Daten-Set zu tun. Die Leistung der verschiedenen Ansätze für diese Art von Algorithmus ist oft ein bisschen unintuitive.)
Edit:. ich meinen eigenen Rat nahm, da war ich neugierig und habe ein paar Tests
Ich vergleichen vier Ansätze:
Die weighted_choice Funktion oben.
Eine binäre-Suche Auswahlfunktion wie folgt:
def weighted_choice_bisect(items):
added_weights = []
last_sum = 0
for item, weight in items:
last_sum += weight
added_weights.append(last_sum)
return items[bisect.bisect(added_weights, random.random() * last_sum)][0]
Eine Zusammenstellung Version von 1:
def weighted_choice_compile(items):
"""returns a function that fetches a random item from items
items is a list of tuples in the form (item, weight)"""
weight_total = sum((item[1] for item in items))
def choice(uniform = random.uniform):
n = uniform(0, weight_total)
for item, weight in items:
if n < weight:
return item
n = n - weight
return item
return choice
Eine Zusammenstellung Version 2:
def weighted_choice_bisect_compile(items):
"""Returns a function that makes a weighted random choice from items."""
added_weights = []
last_sum = 0
for item, weight in items:
last_sum += weight
added_weights.append(last_sum)
def choice(rnd=random.random, bis=bisect.bisect):
return items[bis(added_weights, rnd() * last_sum)][0]
return choice
Ich baute dann eine große Liste von Auswahlmöglichkeiten wie folgt:
choices = [(random.choice("abcdefg"), random.uniform(0,50)) for i in xrange(2500)]
Und eine zu einfache Profilierung Funktion:
def profiler(f, n, *args, **kwargs):
start = time.time()
for i in xrange(n):
f(*args, **kwargs)
return time.time() - start
Die Ergebnisse:
(Sekunden für 1.000 Anrufe an die Funktion entnommen.)
- Einfache unkompilierten: ,918624162674
- Binary unkompilierten: 1,01497793198
- Einfache zusammengestellt: ,287325024605
- Binary kompiliert: 0,00327413797379
Die „kompiliert“ Ergebnisse enthalten die durchschnittliche Zeit, die Wahl Funktion einmal zu kompilieren genommen. (I timed 1000 compiliert, unterteilt dann die Zeit von 1000 und fügte hinzu, das Ergebnis der Wahl Funktion der Zeit.)
Also:., Wenn Sie eine Liste der Elemente + Gewichte haben, die sehr selten ändern, die binäre kompilierte Methode ist mit Abstand die schnellsten
Andere Tipps
In den Kommentaren auf der ursprünglichen Nachricht, schlägt Nicholas Leonard, dass sowohl der Austausch und die Probenahme muß schnell sein. Hier ist eine Idee für diesen Fall; Ich habe es nicht versucht.
Wenn nur Probenahme schnell sein mussten, konnten wir eine Reihe der Werte zusammen mit der laufenden Summe ihrer Wahrscheinlichkeiten, verwenden und eine binäre Suche auf dem laufenden Summe tun (mit Schlüssel eine einheitliche Zufallszahl ist) - ein O (log (n)) Betrieb. Aber ein Austausch erfordern würde nach den Angaben erscheinen alle des laufenden Summenwertes Aktualisierung ausgetauscht - eine O (n) -Operation. (Können Sie wählen nur Produkte am Ende ihrer Listen tauschen? Ich nehme an, nicht.)
Lassen Sie uns also für O Ziel (log (n)) in beiden Operationen. Anstelle einer Anordnung, halten einen binären Baum für jeden aus eingestellt abzutasten. Ein Blatt hält den Abtastwert und dessen (nicht normalisierten) Wahrscheinlichkeit. Ein Zweigknoten hält die Gesamtwahrscheinlichkeit ihrer Kinder.
abzutasten eine einheitliche Zufallszahl zwischen 0 und x die Gesamtwahrscheinlichkeit der Wurzel zu erzeugen, und den Baum hinab. An jedem Zweig, wählen Sie das linke Kind, wenn das linke Kind Gesamtwahrscheinlichkeit <= x hat. Else subtrahiert das linke Kind Wahrscheinlichkeit von x und gehen Sie nach rechts. Bringen Sie den Blatt Wert, den Sie erreichen.
Zum Austausch, entfernen Sie das Blatt von seinem Baum und stellen Sie die Zweige, die zu ihm führen hinunter (ihre Gesamtwahrscheinlichkeit abnimmt und Ausschneiden keine Ein-Kind-Zweigknoten). Legen Sie das Blatt in den Zielbaum: Sie haben eine Wahl, wo es zu setzen, so halten Sie es ausgeglichen. ein zufälliges Kind auf jeder Ebene Picking ist wahrscheinlich gut genug - das ist, wo ich anfangen würde. Erhöhen Sie jede Wahrscheinlichkeit des übergeordneten Knoten, zurück bis zur Wurzel.
Nun sind beide Probenahme und Austausch sind O (log (n)) im Durchschnitt. (Wenn Sie garantieren Balance benötigen, eine einfache Möglichkeit, ein anderes Feld mit dem Zweig Knoten hinzuzufügen, ist die Anzahl der Blätter in dem gesamten Unterbaum zu halten. Wenn ein Blatt hinzufügen, auf jeder Ebene mit weniger Blättern das Kind holen. Dies läßt die Möglichkeit eines allein durch Streichungen Baum unausgeglichen bekommen;. dies kein Problem sein kann, wenn es angemessen ist, auch den Verkehr zwischen den Sätzen, aber wenn ja, dann Drehungen beim Löschen wählt mit der Blattzählung Informationen zu jedem Knoten in Ihrem Traversal)
Update: Auf Wunsch ist hier eine grundlegende Implementierung. Haben sie überhaupt nicht gestimmt. Verbrauch:
>>> t1 = build_tree([('one', 20), ('two', 2), ('three', 50)])
>>> t1
Branch(Leaf(20, 'one'), Branch(Leaf(2, 'two'), Leaf(50, 'three')))
>>> t1.sample()
Leaf(50, 'three')
>>> t1.sample()
Leaf(20, 'one')
>>> t2 = build_tree([('four', 10), ('five', 30)])
>>> t1a, t2a = transfer(t1, t2)
>>> t1a
Branch(Leaf(20, 'one'), Leaf(2, 'two'))
>>> t2a
Branch(Leaf(10, 'four'), Branch(Leaf(30, 'five'), Leaf(50, 'three')))
Code:
import random
def build_tree(pairs):
tree = Empty()
for value, weight in pairs:
tree = tree.add(Leaf(weight, value))
return tree
def transfer(from_tree, to_tree):
"""Given a nonempty tree and a target, move a leaf from the former to
the latter. Return the two updated trees."""
leaf, from_tree1 = from_tree.extract()
return from_tree1, to_tree.add(leaf)
class Tree:
def add(self, leaf):
"Return a new tree holding my leaves plus the given leaf."
abstract
def sample(self):
"Pick one of my leaves at random in proportion to its weight."
return self.sampling(random.uniform(0, self.weight))
def extract(self):
"""Pick one of my leaves and return it along with a new tree
holding my leaves minus that one leaf."""
return self.extracting(random.uniform(0, self.weight))
class Empty(Tree):
weight = 0
def __repr__(self):
return 'Empty()'
def add(self, leaf):
return leaf
def sampling(self, weight):
raise Exception("You can't sample an empty tree")
def extracting(self, weight):
raise Exception("You can't extract from an empty tree")
class Leaf(Tree):
def __init__(self, weight, value):
self.weight = weight
self.value = value
def __repr__(self):
return 'Leaf(%r, %r)' % (self.weight, self.value)
def add(self, leaf):
return Branch(self, leaf)
def sampling(self, weight):
return self
def extracting(self, weight):
return self, Empty()
def combine(left, right):
if isinstance(left, Empty): return right
if isinstance(right, Empty): return left
return Branch(left, right)
class Branch(Tree):
def __init__(self, left, right):
self.weight = left.weight + right.weight
self.left = left
self.right = right
def __repr__(self):
return 'Branch(%r, %r)' % (self.left, self.right)
def add(self, leaf):
# Adding to a random branch as a clumsy way to keep an
# approximately balanced tree.
if random.random() < 0.5:
return combine(self.left.add(leaf), self.right)
return combine(self.left, self.right.add(leaf))
def sampling(self, weight):
if weight < self.left.weight:
return self.left.sampling(weight)
return self.right.sampling(weight - self.left.weight)
def extracting(self, weight):
if weight < self.left.weight:
leaf, left1 = self.left.extracting(weight)
return leaf, combine(left1, self.right)
leaf, right1 = self.right.extracting(weight - self.left.weight)
return leaf, combine(self.left, right1)
Update 2: In ein weiteres Problem beantworten, Jason Orendorff weist darauf hin, dass die binären Bäume durch perfekt ausbalanciert gehalten werden kann sie in einem Array darstellt. (Dies spart den Platz auf Zeiger ausgegeben, auch.) Sehen Sie meine Kommentare zu dieser Antwort, wie seinen Code für dieses Problem anzupassen.
Ich schlage vor, Sie Port diese PHP-Implementierung von gewichteten Zufall Python. Insbesondere hilft die binary-Suche-basierten zweiten Algorithmus Ihre Geschwindigkeit Bedenken auszuräumen.
würde ich dieses Rezept rel="nofollow. Sie müssen ein Gewicht, um Ihre Objekte hinzuzufügen, aber das ist nur ein einfaches Verhältnis und steckte sie in einer Liste von Tupeln (Objekt, Überzeugung / (Summe der Verurteilungen)). Dies sollte einfach eine Liste Verständnis zu tun, verwendet wird.
Hier ist ein klassischer Weg, es zu tun, in Pseudo-Code, wo random.random () Ihnen einen zufälligen float von 0 bis 1 gibt.
let z = sum of all the convictions
let choice = random.random() * z
iterate through your objects:
choice = choice - the current object's conviction
if choice <= 0, return this object
return the last object
Ein Beispiel: Stellen Sie zwei Objekte haben, eine mit Gewicht 2, ein weiteres mit Gewicht 4. Sie erzeugen eine Zahl von 0 bis 6. Wenn choice zwischen 0 und 2 ist, die mit 2/6 = passieren wird 1 / 3 Wahrscheinlichkeit, dann wird es mit 2 und das erste Objekt subtrahiert erhalten ist, ausgewählt. Wenn die Wahl zwischen 2 und 6 ist, die mit 4/6 = 2/3 Wahrscheinlichkeit passieren werden, dann wird die erste Subtraktion noch hat die Wahl zu sein> 0, und die zweite Subtraktion wird das zweite Objekt macht gewählt erhalten.
Sie möchten jede geben ein Gewicht widersprechen. Je größer das Gewicht desto wahrscheinlicher ist es passieren wird. Genauer gesagt probx = Gewicht / sum_all_weights.
Dann eine Zufallszahl im Bereich von 0 bis sum_all_weights erzeugen und wo es zu jedem Objekt.
Dieser Code ermöglicht es Ihnen, einen zufälligen Index zu generieren und abgebildet wird, wenn das Objekt für die Geschwindigkeit erzeugt wird. Wenn alle Ihre Gruppen von Objekten die gleiche Verteilung haben, dann können Sie mit nur einem RandomIndex Objekt erhalten durch.
import random
class RandomIndex:
def __init__(self, wlist):
self._wi=[]
self._rsize=sum(wlist)-1
self._m={}
i=0
s=wlist[i]
for n in range(self._rsize+1):
if n == s:
i+=1
s+=wlist[i]
self._m[n]=i
def i(self):
rn=random.randint(0,self._rsize)
return self._m[rn]
sx=[1,2,3,4]
wx=[1,10,100,1000] #weight list
ri=RandomIndex(wx)
cnt=[0,0,0,0]
for i in range(1000):
cnt[ri.i()] +=1 #keep track of number of times each index was generated
print(cnt)
über 3 Jahre später ...
Wenn Sie numpy verwenden, vielleicht die einfachste Option ist np.random.choice , die eine Liste der möglichen Werte annimmt, und eine optionale Folge von Wahrscheinlichkeiten mit jedem Wert zugeordnet:
import numpy as np
values = ('A', 'B', 'C', 'D')
weights = (0.5, 0.1, 0.2, 0.2)
print ''.join(np.random.choice(values, size=60, replace=True, p=weights))
# ACCADAACCDACDBACCADCAAAAAAADACCDCAADDDADAAACCAAACBAAADCADABA
Das einfachste, was zu tun ist random.choice zu verwenden (die eine gleichmäßige Verteilung verwendet) und variiert die Häufigkeit des Auftretens auf dem Objekt in der Quellauflistung.
>>> random.choice([1, 2, 3, 4])
4
... vs:
>>> random.choice([1, 1, 1, 1, 2, 2, 2, 3, 3, 4])
2
So Ihre Objekte könnten eine Basis Auftrittsrate (n) haben und zwischen 1 und n Objekte werden auf die Quellensammlung in Abhängigkeit von der Verurteilungsrate hinzugefügt. Diese Methode ist sehr einfach; kann es jedoch erheblichen Aufwand, wenn die Anzahl der verschiedenen Objekte groß ist oder die Verurteilungsrate sein muss sehr feinkörnig.
Alternativ, wenn Sie erzeugen mehr als eine Zufallszahl eine gleichmäßige Verteilung mit und summieren sie Zahlen in der Nähe des mittleren auftretenden wahrscheinlicher sind, dass diejenigen in der Nähe von den Extremen auftritt (man denke an zwei Würfel rollen und die Wahrscheinlichkeit von 7 gegenüber 12 bekommen oder 2). Anschließend können Sie die Objekte durch Verurteilungsrate bestellen und eine Reihe mit mehreren Düsenrollen erzeugen, die Sie zu berechnen, und der Index in die Objekte verwenden. Verwenden Sie Zahlen in der Nähe des mittleren indizieren geringe Überzeugung Objekte und Zahlen in der Nähe von den Extremen zu indizieren hohe Überzeugung Gegenstände. Sie können die genaue Wahrscheinlichkeit variieren, dass ein bestimmtes Objekt wird durch Ändern der „Anzahl der Seiten“ und die Nummer Ihres „Würfels“ ausgewählt werden (es kann einfacher sein, die Objekte in Eimer zu setzen und verwendet Würfel mit einer kleinen Anzahl von Seiten statt versuchen, jedes Objekt mit einem bestimmten Ergebnis zu assoziieren):
>>> die = lambda sides : random.randint(1, sides)
>>> die(6)
3
>>> die(6) + die(6) + die(6)
10
Eine sehr einfache und einfache Möglichkeit, dies zu tun, ist für jeden der Werte Gewichte zu setzen, und es würde nicht viel Speicher benötigen.
Sie könnten wahrscheinlich einen Hash / Wörterbuch verwenden, um dies zu tun.
Was Sie tun möchten, ist die Zufallszahl haben, x , multipliziert und über den gesamten Satz von Dingen, die Sie ausgewählt werden sollen summierte und teilt dieses Ergebnis über die Anzahl der Objekte in Ihrem Satz.
Pseudo-Code:
objectSet = [(object1, weight1), ..., (objectN, weightN)]
sum = 0
rand = random()
for obj, weight in objectSet
sum = sum+weight*rand
choice = objectSet[floor(sum/objectSet.size())]
EDIT : Ich dachte nur, wie langsam mein Code mit sehr großen Mengen würde (es ist O (n)). Der folgende Pseudo-Code ist O (log (n)), und ist im Grunde eine binäre Suche verwendet wird.
objectSet = [(object1, weight1), ..., (objectN, weightN)]
sort objectSet from less to greater according to weights
choice = random() * N # where N is the number of objects in objectSet
do a binary search until you have just one answer
Es gibt Implementierungen von binärer Suche in Python ganzer ‚net, so dass hier keine Notwendigkeit zu wiederholen.
Hier ist eine bessere Antwort für eine spezielle Wahrscheinlichkeitsverteilung, die ein Rex Logan Antwort scheint ausgerichtet zu sein. Die Verteilung ist wie folgt: Jedes Objekt hat ein ganzzahligen Gewicht zwischen 0 und 100, und seine Wahrscheinlichkeit ist, im Verhältnis zu seinem Gewicht. Da, dass die derzeit akzeptierte Antwort ist, ich denke, dies über wert ist zu denken.
So ein Array von 101 Behältern halten. Jeder Behälter enthält eine Liste aller Objekte mit ihrem besonderen Gewicht. Jeder Behälter auch kennt das total Gewicht aller Objekte.
Zur Probe: ein sind zufällig im Verhältnis zu seinem Gesamtgewicht holen. (Verwenden Sie eine der Standardrezepte für diese -. Lineare oder binäre Suche). Dann aus dem Behälter ein Objekt auswählen gleichmäßig zufällig
Um ein Objekt zu übertragen: entfernen Sie es aus seinem ist, steckt es in seinem sind im Ziel und aktualisiert beiden Gewichte Bins. (Wenn Sie für die Probenahme binäre Suche verwenden, müssen Sie auch die laufenden Summen aktualisieren, die verwendet wird. Dies ist immer noch ziemlich schnell, da es nicht viele Bins).
(Ein Jahr später) alias Methode für zufällige Objekte mit unterschiedlichen probablities Walker sehr schnell und sehr einfach
Ich war in schnellen Funktionen benötigt werden, für nicht sehr große Zahlen. Also hier ist es, in Visual C ++:
#undef _DEBUG // disable linking with python25_d.dll
#include <Python.h>
#include <malloc.h>
#include <stdlib.h>
static PyObject* dieroll(PyObject *, PyObject *args)
{
PyObject *list;
if (!PyArg_ParseTuple(args, "O:decompress", &list))
return NULL;
if (!PyList_Check(list))
return PyErr_Format(PyExc_TypeError, "list of numbers expected ('%s' given)", list->ob_type->tp_name), NULL;
int size = PyList_Size(list);
if (size < 1)
return PyErr_Format(PyExc_TypeError, "got empty list"), NULL;
long *array = (long*)alloca(size*sizeof(long));
long sum = 0;
for (int i = 0; i < size; i++) {
PyObject *o = PyList_GetItem(list, i);
if (!PyInt_Check(o))
return PyErr_Format(PyExc_TypeError, "list of ints expected ('%s' found)", o->ob_type->tp_name), NULL;
long n = PyInt_AsLong(o);
if (n == -1 && PyErr_Occurred())
return NULL;
if (n < 0)
return PyErr_Format(PyExc_TypeError, "list of positive ints expected (negative found)"), NULL;
sum += n; //NOTE: integer overflow
array[i] = sum;
}
if (sum <= 0)
return PyErr_Format(PyExc_TypeError, "sum of numbers is not positive"), NULL;
int r = rand() * (sum-1) / RAND_MAX; //NOTE: rand() may be too small (0x7fff). rand() * sum may result in integer overlow.
assert(array[size-1] == sum);
assert(r < sum && r < array[size-1]);
for (int i = 0; i < size; ++i)
{
if (r < array[i])
return PyInt_FromLong(i);
}
return PyErr_Format(PyExc_TypeError, "internal error."), NULL;
}
static PyMethodDef module_methods[] =
{
{"dieroll", (PyCFunction)dieroll, METH_VARARGS, "random index, beased on weights" },
{NULL} /* Sentinel */
};
PyMODINIT_FUNC initdieroll(void)
{
PyObject *module = Py_InitModule3("dieroll", module_methods, "dieroll");
if (module == NULL)
return;
}
