6

蟒蛇问题。我正在生成大量对象,我只需要制作一个小的随机样本。实际上生成有问题的对象需要一段时间,所以我想知道是否有可能以某种方式跳过那些不需要生成的对象,而只显式地创建那些已经采样的对象。

换句话说,我现在有

a = createHugeArray()
s = random.sample(a,len(a)*0.001)

这是相当浪费的。我更喜欢更懒惰的东西

a = createArrayGenerator()
s = random.sample(a,len(a)*0.001)

我不知道这是否有效。random.sample 上的文档不太清楚,尽管它提到 xrange 非常快 - 这让我相信它可能会起作用。将数组创建转换为生成器会有点工作(我对生成器的了解非常生疏),所以我想提前知道这是否有效。:)

我可以看到的另一种方法是通过 xrange 制作随机样本,并且只生成那些实际通过索引选择的对象。不过,这不是很干净,因为生成的索引是任意且不必要的,我需要相当老套的逻辑来在我的 generateHugeArray 方法中支持这一点。

对于加分:random.sample 是如何实际工作的?特别是,如果它事先不知道人口的规模,它是如何工作的,比如像 xrange 这样的生成器?

4

4 回答 4

2

似乎没有办法避免弄清楚索引如何映射到您的排列。如果您不知道这一点,您将如何从您的数组中创建一个随机对象?您可以使用xrange()自己建议的技巧,也可以实现一个定义__getitem__()and__len__()方法的类,并将此类的 and 对象作为population参数传递给random.sample().

一些进一步的评论:

  • 将 createHugeArray() 转换为生成器不会给您带来任何好处——random.sample()将不再起作用。它需要一个支持的对象len()

  • 所以它确实需要从一开始就知道总体中的元素数量。

  • 实现具有两种不同的算法,并选择使用较少内存的一种。对于相对较小k的(即在手头的情况下),它将简单地保存已经在 a 中选择的索引,set并在命中其中一个时做出新的随机选择。

编辑:一种完全不同的方法是对所有排列进行一次迭代,并决定是否应该包含每个排列。如果排列的总数是n并且你想从中选择k,你可以写

selected = []
for i in xrange(n):
    perm = nextPermutation()
    if random.random() < float(k-len(selected))/(n-i):
        selected.append(perm)

这将k随机选择精确的排列。

于 2010-11-26T16:50:02.657 回答
0

您可以使用示例创建数组索引列表,然后根据结果生成对象:

def get_object(index):
    return MyClass(index)

或类似的东西。然后使用 sample 生成您需要的索引并使用这些索引调用此函数:

objs = map(get_object, random.sample(range(length), 0.001 * length))

这有点间接,因为它只从可能的数组索引列表中选择。

于 2010-11-26T16:35:20.240 回答
0

解释 random.sample 的工作原理,

random.sample(container, k)将从容器中随机返回 k 个值。因为生成器像列表、元组和字典中的键或值一样是可迭代的,所以它将遍历容器,然后获取这些随机元素。

例如random.sample(xrange(111),4),将返回类似于[33,52,111,1]k = 4xrange 生成器到 111 的 4 个随机数。

于 2010-11-26T16:36:27.840 回答
0

我猜测函数 createHugeArray() 包含一段代码,该代码对创建的每个对象重复一次。我猜这些对象是从某种初始值或种子生成的,在这种情况下 createHugeArray() 看起来像这样:

def createHugeArray( list_of_seeds ):
  huge_array = []                  
  for i in list_of_seeds:
    my_object = makeObject( i )
    huge_array.append( my_object )           
  return huge_array

(我使用的是列表而不是数组,但你明白了。)

要在实际创建对象之前进行随机抽样,只需添加一行生成随机数的行,然后仅当随机数低于某个阈值时才创建对象。假设您只想要千分之一的对象。random.randint(0,999) 给出一个从 0 到 999 的数字 - 所以只有当你得到零时才生成一个对象。上面的代码变成:

import random

def createHugeArray( list_of_seeds ):
  huge_array = [] 

  for i in list_of_seeds:
    die_roll = random.randint(0,999)

    if( die_roll == 0 ):
      my_object = makeObject( i )
      huge_array.append( my_object ) 
  return huge_array

当然,如果我对您的代码如何工作的猜测是错误的,那么这对您来说毫无用处,在这种情况下,对不起,祝您好运:-)

于 2010-11-26T20:00:53.733 回答