التوزيع الاحتمالي في بايثون
https://stackoverflow.com/questions/526255
-
22-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russianسؤال
لدي مجموعة من المفاتيح التي تحتوي على unlikeliness متغير.أريد أن تختار عشوائيا واحد من هذه المفاتيح ، ولكن أريد أن يكون أكثر غير المرجح (مفتاح القيم) يتم اختياره من أقل من غير المحتمل (على الأرجح) الكائن.وأنا أتساءل عما إذا كان لديك أي اقتراحات ، ويفضل أن يكون موجود بيثون وحدة التي يمكن أن تستخدم وإلا سوف تحتاج إلى جعل ذلك بنفسي.
يجب فحص عشوائي وحدة ؛ لا يبدو أن تقديم هذا.
يجب أن تجعل هذه الخيارات الملايين من الأوقات 1000 مجموعات مختلفة من الكائنات تحتوي كل منها على 2,455 الكائنات.كل مجموعة سوف تبادل أجسام بين بعضها البعض بحيث عشوائية مختار يحتاج إلى ديناميكية.مع 1000 مجموعات من 2,433 الكائنات التي 2,433 مليون الكائنات ؛ انخفاض استهلاك الذاكرة أمر بالغ الأهمية.وبما أن هذه الخيارات ليست هي الأكبر من الخوارزمية ، أنا بحاجة إلى هذه العملية أن تكون سريعة جدا;وحدة المعالجة المركزية-الوقت محدود.
Thx
تحديث:
حسنا, لقد حاولت للنظر في الاقتراحات الخاصة بك بحكمة ، ولكن الوقت محدود جدا...
بحثت في شجرة البحث الثنائية النهج يبدو مخاطرة كبيرة جدا (معقد).غيرها من الاقتراحات جميع تشبه ActiveState وصفة.أخذته و تعديله قليلا على أمل صنع أكثر كفاءة:
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
أنا على أمل الحصول على زيادة الكفاءة من حيوي للحفاظ على مبلغ اليقين و أقصى قدر من اليقين.أي اقتراحات هي موضع ترحيب.أنتم يوفر لي الكثير من الوقت والجهد ، في حين أن زيادة فعالية بلدي هو مجنون.Thx!Thx!Thx!
Update2:
قررت لجعله أكثر كفاءة من خلال السماح لها اختيار المزيد من الخيارات في وقت واحد.وهذا سوف يؤدي إلى خسارة مقبولة في الدقة في algo هو ديناميكية في الطبيعة.على أي حال, هنا هو ما لدي الآن:
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)
أنا لم أجربها بعد.إذا كان لديك أي تعليقات/اقتراحات لا تترددوا.Thx!
Update3:
لقد تم العمل على المهمة-نسخة معدلة من ريكس لوغان الإجابة.بدلا من 2 المصفوفات الأجسام والأوزان ، هو في الواقع خاصة القاموس الفئة ، الأمر الذي يجعل الأمور معقدة جدا منذ ريكس رمز يولد العشوائية مؤشر...أنا أيضا مشفرة حالة اختبار هذا النوع يشبه ما يحدث في بلدي algo (ولكن أنا لا أعرف حقا حتى محاولة!).المبدأ الأساسي هو:أكثر مفتاح بشكل عشوائي في كثير من الأحيان ، أكثر من غير المرجح أنها سوف تكون ولدت مرة أخرى:
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()
أي تعليقات لا تزال موضع ترحيب.@داريوس:الثنائية الأشجار معقدة جدا ومعقدة بالنسبة لي ؛ وأنا لا أعتقد أن يورق يمكن إزالتها بكفاءة...Thx all
المحلول
هذا activestate وصفة يعطي سهلة اتبع النهج ، وتحديدا الإصدار في التعليقات التي لا تتطلب منك قبل تطبيع الأوزان الخاصة بك:
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
هذا سوف يكون بطيئا إذا كان لديك قائمة كبيرة من العناصر.البحث الثنائي ربما يكون من الأفضل في هذه الحالة...ولكن من شأنه أيضا أن يكون أكثر تعقيدا في الكتابة ، من أجل مكسب قليلا إذا كان لديك عينة صغيرة الحجم. هنا مثال من البحث الثنائية النهج في بايثون إذا كنت تريد أن تتبع هذا الطريق.
(أنصح به بعض سريعة اختبار الأداء من كلا الأسلوبين على مجموعة البيانات الخاصة بك.أداء أساليب مختلفة إلى هذا النوع من الخوارزمية هو في كثير من الأحيان قليلا unintuitive.)
تحرير: أخذت بلدي المشورة ، حيث كان من الغريب ، وقام عدد قليل من الاختبارات.
قارنت أربعة مناهج:
على weighted_choice وظيفة أعلاه.
ثنائي-البحث عن وظيفة اختيار مثل ذلك:
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]
تجميع الإصدار: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
تجميع نسخة من 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
ثم بناء قائمة كبيرة من الخيارات مثل:
choices = [(random.choice("abcdefg"), random.uniform(0,50)) for i in xrange(2500)]
و بشكل مفرط بسيطة التنميط وظيفة:
def profiler(f, n, *args, **kwargs):
start = time.time()
for i in xrange(n):
f(*args, **kwargs)
return time.time() - start
النتائج:
(ثانية تؤخذ مقابل 1000 يدعو إلى وظيفة.)
- بسيطة غير المجمعة:0.918624162674
- ثنائي غير المجمعة:1.01497793198
- بسيطة جمعت:0.287325024605
- ثنائية جمعت:0.00327413797379
إن "جمعت" وتشمل النتائج متوسط الوقت المستغرق في جمع واختيار وظيفة واحدة.(ط توقيت 1,000 تجمع ثم تقسم ذلك الوقت من 1 ، 000 ، إضافة النتيجة إلى وظيفة اختيار الوقت.)
لذلك:إذا كان لديك قائمة من العناصر+الأوزان التي تغير نادرا جدا ، ثنائي جمعت الطريقة حتى الآن أسرع.
نصائح أخرى
في تعليقات على هذه الوظيفة الأصلية، يشير نيكولاس ليونارد أن كلا من تبادل وأخذ العينات تحتاج إلى أن تكون سريعة. وفيما يلي فكرة عن هذه الحالة. لم أحاول ذلك.
إذا كان أخذ العينات الوحيدة ليكون سريع، ونحن يمكن أن تستخدم مجموعة من القيم جنبا إلى جنب مع مجموع تراكمي من احتمالات حصولها، والقيام بالبحث ثنائي على مجموع تراكمي (مع مفتاح كونه رقم عشوائي موحد) - وهو O (سجل (ن)) العملية. ولكن تبادل يتطلب تحديث كافة القيم تشغيل محصلتها تظهر بعد الإدخالات تبادل - وهو O (ن) عملية. (هل يمكن أن تختار لتبادل المنتجات الوحيدة قرب نهاية قوائمها؟ سوف أفترض لا.)
لذلك دعونا تهدف لO (سجل (ن)) في كل من العمليات. بدلا من مجموعة، والحفاظ على شجرة ثنائية لتعيين كل لعينة من. ورقة للنبات يحمل قيمة عينة ولها (unnormalized) احتمال. عقدة فرع تحمل الاحتمال الكلي لأبنائها.
لعينة، وتوليد زي x عدد عشوائي بين 0 و الاحتمال الكلي من الجذر، وتنحدر الشجرة. في كل فرع، اختيار الطفل اليسار إذا ترك الطفل لديه مجموعه <= x الاحتمالات. آخر طرح احتمال ترك الطفل من x ويسير في الاتجاه الصحيح. إرجاع قيمة ورقة تصل.
لتبادل، وإزالة ورقة من شجرة وضبط الفروع التي تؤدي الى ذلك (تناقص إجمالي احتمال حدوثها، والاستغناء عن أي عقد فرع طفل واحد). إدراج ورقة في شجرة المقصد: لديك خيار من حيث وضعه، والحفاظ على ذلك التوازن. اختيار طفل عشوائي في كل مستوى هو على الارجح جيدة بما فيه الكفاية - وهذا حيث كنت أبدأ. زيادة احتمال كل عقدة الأم، والعودة إلى جذورها.
والآن كل من أخذ العينات والصرف O (سجل (ن)) في المتوسط. (إذا كنت بحاجة إلى توازن مضمون، طريقة بسيطة لإضافة حقل آخر إلى العقد فرع عقد عدد من الأوراق في الشجرة الفرعية بأكملها. عند إضافة ورقة، في كل مستوى اختيار الطفل مع عدد أقل من الأوراق. وهذا يترك احتمال وجود شجرة الحصول على غير متوازن فقط من قبل الحذف؛ وهذا لا يمكن أن يكون مشكلة إذا كان هناك حد معقول من الحركة بين مجموعات، ولكن إذا كان كذلك، ثم اختيار تناوب خلال الحذف باستخدام المعلومات أوراق العد على كل عقدة في اجتياز الخاص بك)
<القوي> تحديث: على الطلب، وهنا تنفيذ الأساسي. لم ضبطها على الإطلاق. الاستعمال:
>>> 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')))
والرمز:
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)
على تحديث 2: في <لأ href = "https://stackoverflow.com/questions/2140787/select-random-k-elements-from-a-list-whose-elements-have -weights / 2149533 # 2149533 "> الإجابة مشكلة أخرى ، تشير جيسون Orendorff إلى أن شجرة ثنائية يمكن أن تبقى متوازنة تماما من خلال تمثيل لهم في مجموعة تماما مثل هيكل كومة الكلاسيكية. (وهذا يوفر مساحة قضى على مؤشرات أيضا.) انظر تعليقاتي على أن الجواب عن كيفية التكيف كود له لهذه المشكلة.
وأقترح عليك أن ميناء هذا التطبيق PHP من عشوائي الوزني لبيثون. على وجه الخصوص، الخوارزمية الثانية على أساس ثنائي بحث يساعد على معالجة الشواغل سرعة.
وأود أن استخدام هذه صفة . وسوف تحتاج إلى إضافة الوزن إلى الأشياء الخاصة بك، ولكن هذا هو مجرد نسبة بسيطة ووضعها في قائمة الصفوف (كائن، القناعة / (مجموع القناعات)). هذا ينبغي أن يكون من السهل القيام به باستخدام الفهم القائمة.
وهنا هو الطريقة الكلاسيكية للقيام بذلك، في شبة الكود، حيث random.random () يعطيك تعويم عشوائية 0-1.
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
لمثالا على ذلك: تخيل لديك كائنين، واحدة مع الوزن 2، وآخر مع الوزن 4. أنت توليد رقم من 0 إلى 6. إذا choice ما بين 0 و 2، والذي سيحدث مع 2/6 = 1 / 3 الاحتمالات، وبعد ذلك سوف تحصل على طرح من قبل (2) ويتم اختيار الكائن الأول. إذا كان اختيارك هو ما بين 2 و 6، والذي سيحدث مع 4/6 = 2/3 احتمالية، ثم الطرح الأول لا تزال لديها خيار يجري> 0، وسوف الطرح الثاني جعل الكائن 2ND الحصول على اختيار.
وأنت تريد أن تعطي كل كائن الوزن. كلما كان الوزن أكثر احتمالا أن ذلك سيحدث. بتعبير أدق probx = الوزن / sum_all_weights.
وثم توليد رقم عشوائي في النطاق من 0 إلى sum_all_weights وتعيين ذلك إلى كل كائن.
وهذا الرمز يسمح لك لتوليد مؤشر عشوائي ويتم تعيين عندما يتم إنشاء الكائن للسرعة. وإذا كان كل من مجموعات بك من الأشياء لديهم نفس التوزيع ثم يمكنك الحصول عليه مع الكائن RandomIndex واحد فقط.
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)
عن 3 سنوات...
إذا كنت تستخدم numpy, ولعل أبسط خيار هو استخدام np.random.choice, الذي يأخذ قائمة من القيم الممكنة اختياري سلسلة من الاحتمالات المرتبطة مع بعضها القيمة:
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
أبسط شيء نفعله هو استخدام عشوائي.الاختيار (الذي يستخدم توزيع موحد) و تختلف تواتر على الكائن في جمع المصدر.
>>> random.choice([1, 2, 3, 4])
4
...vs:
>>> random.choice([1, 1, 1, 1, 2, 2, 2, 3, 3, 4])
2
حتى الأشياء الخاصة بك يمكن أن يكون قاعدة حدوث معدل (ن) بين 1 و n الكائنات وأضاف المصدر أن المجموعة بوصفها وظيفة من معدل الإدانة.هذا الأسلوب هو بسيط حقا.ومع ذلك ، يمكن أن يكون حمل كبير إذا كان عدد متميزة الأجسام الكبيرة أو معدل الإدانة يجب أن تكون جدا غرامة الحبيبات.
بدلا من ذلك, إذا كنت توليد أكثر من واحد رقم عشوائي باستخدام توزيع موحد و مبلغ لهم والأرقام التي تحدث قرب يعني أكثر من المحتمل أن تلك التي تقع بالقرب من التطرف (اعتقد المتداول اثنين من الزهر و احتمال الحصول على 7 مقابل 12 أو 2).ثم يمكنك ترتيب الأشياء حسب معدل الإدانة وتوليد عدد استخدام عدة يموت القوائم التي يمكنك استخدامها لحساب مؤشر إلى الكائنات.استخدام الأرقام بالقرب أقصد أن مؤشر انخفاض إدانة الأشياء والأرقام بالقرب من التطرف إلى مؤشر عالية إدانة البنود.يمكنك تغيير دقة احتمال أن كائن معين سيتم اختيار طريق تغيير "عدد من الجانبين" وعدد من "الزهر" (قد يكون أبسط إلى وضعت الأشياء في الدلاء استخدام النرد مع عدد صغير من الجانبين بدلا من محاولة ربط كل كائن مع نتيجة محددة):
>>> die = lambda sides : random.randint(1, sides)
>>> die(6)
3
>>> die(6) + die(6) + die(6)
10
وهناك طريقة سهلة جدا وبسيطة للقيام بذلك هي لتحديد أوزان لكل من القيم، وأنها لن تتطلب الكثير من الذاكرة.
وربما يمكن أن تستخدم تجزئة / القاموس للقيام بذلك.
ما عليك تريد القيام به هو الحصول على رقم عشوائي، <م> س مضروبة ولخص على مجموعة كاملة من الأشياء التي تريد المحدد، وتقسيم تلك النتيجة على عدد من الأشياء في حياتك مجموعة.
والزائفة رمز:
objectSet = [(object1, weight1), ..., (objectN, weightN)]
sum = 0
rand = random()
for obj, weight in objectSet
sum = sum+weight*rand
choice = objectSet[floor(sum/objectSet.size())]
تحرير : أنا بس كيف بطيئة قانون بلدي سيكون مع مجموعات كبيرة جدا (انها O (ن)). في رمز الزائفة التالية هي O (سجل (ن))، وأساسا يستخدم بحث ثنائي.
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
وهناك تطبيقات البحث الثنائي في بيثون في جميع أنحاء صافي، لذلك لا حاجة يعيد هنا.
وهنا إجابة أفضل لتوزيع احتمال خاص، الجواب واحد ريكس لوغان يبدو أن توجه في. توزيع مثل هذا: كل كائن له وزن صحيح بين 0 و 100، واحتمال منه هو بما يتناسب مع وزنه. لأن هذا هو الجواب المقبولة حاليا، أعتقد أن هذا هو يستحق التفكير.
وحتى تبقي مجموعة من 101 صناديق. يحمل كل بن قائمة بجميع الكائنات بكل ثقلها معين. كل بن يعرف أيضا <م> مجموعه وزن كل أهدافه.
لعينة: اختيار بن عشوائيا منسوبة الى مجموع وزنها. (استخدم واحدة من صفات القياسية لهذا - البحث الخطي أو ثنائي). ثم اختيار كائن من بن موحد عشوائيا
لنقل كائن: إزالته من بن على، ووضعها في بن في الهدف، وتحديث الأوزان كل من صناديق ". (إذا كنت تستخدم البحث الثنائي لأخذ العينات، يجب عليك أيضا تحديث مبالغ تشغيل يستخدم هذا لا يزال بسرعة معقولة حيث لا توجد العديد من صناديق).
(وبعد ذلك بعام) طريقة الملقب وكر للكائنات عشوائية مع probablities مختلفة هو سريع جدا وبسيط جدا
وهناك حاجة أنا في وظائف أسرع، لعدم بأعداد كبيرة جدا. حتى هنا هو، في 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;
}
