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 回答