不是从Python对象列表中随机抽取的

2024-03-28 10:42:56 发布

您现在位置:Python中文网/ 问答频道 /正文

我有大约20000个对象的字典,键是对象的字符串表示,值是对象本身。每个对象都有属性self.lengthself.rateself.rate计算为1.5E-8*self.length。在

我需要从这个dict中选择一个预先确定的数量(在这个例子中我们将为500个)基于它们的速率来选择项目。比率较低的对象不太可能被选中,比率较高的对象则更有可能被选中。在

我以为我能做到这一点的方式很慢。在

在while循环中,当选定对象的数量小于所需选择的数量时,我生成一个介于0和dict长度之间的随机数,然后选择该元素。然后我生成另一个随机数,如果这个随机数小于列表中所选对象的rate,则将其添加到所选对象中。起初这看起来不错,但现在我意识到它太慢了。有人对如何更快地做到这一点有什么建议吗?在

一些代码: 对象的类定义

from numpy import random
class object():
    def __init__(self, length):
        self.length  = length
        self.rate = (1.15E-8*self.length)

    def select(self):
        x = random.uniform(0,1)
        if(x<self.rate):
            return True
        else:
            return False

以及完成其余工作的函数(在另一个模块中):

^{pr2}$

我认为使它变得非常慢的原因是每个对象被选中的概率非常小,以至于在选择一个对象之前需要多次迭代,更不用说500次甚至更多。在

长度分布:

Min. 1st Qu.  Median    Mean 3rd Qu.    Max. 
     51     822    1311    1770    2112  103000 

Tags: 对象字符串self数量return字典属性rate
3条回答

试试这个:

import numpy as np    # requires NumPy 1.7 (!)

def select_random(object_dict, n):
    keys = object_dict.keys()
    rate = np.array([x.rate for x in keys])
    prob = rate / rate.sum()
    return np.random.choice(keys, size=n, replace=True, p=prob)

Documentation

另外,调用一个类object是个坏主意,因为这也是内置通用基类的名称。在

通过递增地合计项目的权重,您可以根据权重随机选择一个随机数,在[0,T)中均匀地选择一个随机数,其中T是所有权重的总和,并取第一个总权重大于该值的项目(例如二进制chop)。如果你想要一个更大的样本,你可以重复这个,或者像这样的代码对随机数进行排序,然后做一个类似于合并排序的步骤。复杂度是一样的,但是代码要简单一点,因为二进制切分总是容易出错。在

import random

def accumulate_weights(weighted_items):
    T = 0.0
    for w, i in weighted_items:
        T += w
        yield (T, i)

def sample_weighted(weighted_items, n):
    cumulative = list(accumulate_weights(weighted_items))
    T = cumulative[-1][0]
    i = 0
    for sample in sorted(random.uniform(0, T) for _ in xrange(n)):
        while sample > cumulative[i][0]:
            i += 1
        yield cumulative[i][1]

r = list(sample_weighted([(1.0, 'a'), (2.0, 'b'), (5.0, 'c'), (1.0, 'd')], 10000))
print [(x, r.count(x)) for x in 'abcd']

如果不明显,你可以用你的“比率”作为权重。当一个对象的速率为0.15,另一个对象的速率为0.3时,重要的是第二个对象的出现频率是第一个对象的两倍。这就是重量在代码中的作用!在

我不知道这种方法是否会更快,但会更准确:

  1. length上做一个求和运算,并将其保存到名为cumsum的列表中
  2. 假设长度是整数(否则必须规范化并选择一个介于0和1之间的数字),请在0和cumsum的最后一个元素之间选择一个随机数
  3. 检查cumsum并取第一个元素的索引,它小于或等于您选择的数字。在
  4. 转到第2步。选择另一个号码。在

假设lengths[1,4,2,10,5],那么cumsum将是:[1,5,7,17,22]现在你在022之间随机选择一个数-i元素的概率是lengeths[i]/cumsum[-1],这听起来更准确。在

相关问题 更多 >