我有许多钥匙，每个都有一个不太可能的变量。我想随机选择其中一个钥匙，但是我希望对于不太可能（键、值）被选择而言，它比较不太可能被选中，而对于较可能（更可能）的对象来说，则更容易被选中。我想知道你是否有任何建议，最好是我可以使用的现有Python模块，否则我将需要自己制作。
我已经查看了随机模块；它似乎没有提供这个功能。
我需要为包含2,455个对象的1000个不同集合做出这样的选择数百万次。每个集合将在彼此之间交换物品，因此随机选择器需要具有动态性。对于包含2,433个对象的1000个集合，总共有2,433亿个对象；低内存消耗至关重要。由于这些选择不是算法的主要部分，我需要这个过程非常快速；CPU时间有限。
谢谢。
更新：
好的，我尽力考虑了您的建议，但时间太紧了...
我查看了二叉搜索树方法，似乎太冒险了（复杂和复杂）。其他建议都类似于ActiveState配方。我获取了它并稍作修改，希望能够更有效。
我已经查看了随机模块；它似乎没有提供这个功能。
我需要为包含2,455个对象的1000个不同集合做出这样的选择数百万次。每个集合将在彼此之间交换物品，因此随机选择器需要具有动态性。对于包含2,433个对象的1000个集合，总共有2,433亿个对象；低内存消耗至关重要。由于这些选择不是算法的主要部分，我需要这个过程非常快速；CPU时间有限。
谢谢。
更新：
好的，我尽力考虑了您的建议，但时间太紧了...
我查看了二叉搜索树方法，似乎太冒险了（复杂和复杂）。其他建议都类似于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
我希望通过动态维护置信度的和以及最大置信度来提高效率。欢迎提出其他建议。你们为我节省了很多时间和精力，同时提高了我的效率，这太不可思议了。谢谢！谢谢！谢谢！
更新2：
我决定通过让它一次选择更多的选项来使其更加高效。虽然这会导致算法精度有所损失，但由于其具有动态性质，因此这是可以接受的。无论如何，这就是我现在拥有的：
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)
我还没有试过它。如果您有任何意见/建议，请不要犹豫。谢谢！
更新3：
我整天都在为Rex Logan的答案定制任务版本而努力工作。这个版本不像是2个对象和权重的数组，而是一个特殊的字典类；由于Rex的代码生成随机索引，所以事情变得相当复杂... 我还编写了一个测试用例，它有点类似于我的算法将发生的情况（但在尝试之前我不太确定！）基本原则是：随机生成的键越多，再次生成的可能性就越小：
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()
仍然欢迎任何评论。@Darius：你的二叉树对我来说太复杂了，我不认为它的叶子节点可以有效地被移除... 谢谢大家
bisect模块）。 - Darius Bacon