それぞれがありそうもない変数を持つキーがたくさんあります。これらのキーのいずれかをランダムに選択したいのですが、可能性が低い (可能性が高い) オブジェクトよりも、可能性が低い (キー、値) が選択される可能性が低いことを望んでいます。何か提案があれば、できれば私が使用できる既存の python モジュールがあるかどうか疑問に思っています。それ以外の場合は、自分で作成する必要があります。
random モジュールをチェックアウトしました。これを提供していないようです。
それぞれが 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)
まだ試していません。ご意見/ご提案がございましたら、お気軽にお寄せください。どうも！
Update3:
私は一日中、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: あなたの二分木は複雑すぎて私には複雑です。そして、その葉を効率的に取り除くことができるとは思いません... Thx all