4

我有大约 20,000 个对象的字典键是对象的字符串表示形式，值是对象本身。每个对象都有属性self.length和self.rate。self.rate计算为1.5E-8*self.length。

我需要根据他们的费率从这个字典中选择一个预定数量的项目（在这个例子中我们会说 500 个）。具有较低比率的对象不太可能被选择，而具有较高比率的对象更有可能被选中。

我认为我可以做到这一点的方式非常缓慢。

在一段时间内，虽然所选对象的数量小于所需选择的数量，但我在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

以及完成其余工作的函数（在另一个模块中）：

def select_random(object_dict,maxselect):
    nselect = 0
    object_names = object_dict.keys()
    selected_objects = []
    while(nselect < maxselect):
        x = random.randint(0,len(object_dict))
        if(object_dict[object_names[x]].select()):
            nselect +=1
            selected_objects.append(object_names[x])
    return(selected_objects)

我认为使它真正变慢的原因是每个对象被选择的概率是如此之小，以至于在选择一个对象之前需要进行多次迭代，更不用说 500 个或更多。

长度分布：

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

5 回答 5

2

尝试这个：

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)

（文档）

PS，调用 class 是个坏主意object，因为这也是内置通用基类的名称。

于 2012-08-01T11:20:06.957 回答
1

通过递增地总结项目的权重，您可以通过在 [0, T) 中统一选择一个随机数来根据权重随机选择一个，其中 T 是所有权重的总和，并取第一个较大的项目总比（例如二进制印章）。如果您想要更大的样本，您可以重复此操作，或者像此代码一样对随机数进行排序并执行类似合并排序的步骤。复杂性是一样的，但我认为代码更简单一些，因为二进制印章总是容易出错。

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 时，重要的是第二个对象的出现频率是第一个对象的两倍。这就是这段代码中权重的作用！

于 2012-08-01T12:28:18.000 回答
1

我不知道这种方法是否会更快，但它会更准确：

  1. 做一个 cumsumlength并将其保存到一个名为的列表中cumsum
  2. 假设长度是整数（否则你将不得不标准化并选择一个介于 0 和 1 之间的数字）选择一个介于 0 和最后一个元素之间的随机数cumsum
  3. 遍历 cumsum 并获取小于或等于您选择的数字的第一个元素的索引。
  4. 转到步骤 2。选择另一个号码。

假设lengths现在是：[1,4,2,10,5]现在你随机选择一个介于和之间的数字 - 你会得到对我来说听起来更准确的元素。cumsum[1,5,7,17,22]022ilengeths[i]/cumsum[-1]

于 2012-08-01T11:17:57.880 回答
0

您的费率介于 5.865e-07 和 0.0011845 之间，并且您的统一随机选择介于 0 和 1 之间，我相信如果您能够根据 1311 的中位数选择 500 个对象，您将是幸运的。

你需要改变你的随机选择

x = random.uniform(0,1)

成为

import random
x = random.triangular(51, 103000 , 1311 )
于 2012-08-01T11:48:27.470 回答
-2

如果你需要足够多的对象，你可以这样编写 select 函数：

def select(self):
  x = randint(0,self.length)
  if x > self.legth - c:
   return False
  return True

这样，概率将取决于常数 c 和长度（反映到速率）

于 2012-08-01T11:27:02.297 回答