在Python中懒惰地抽样随机结果

Question

这是一个关于Python的问题。我正在生成一个很大的对象数组，但实际上我只需要从中随机抽取一小部分。生成这些对象需要一些时间，所以我在想，是否可以跳过那些不需要生成的对象，只创建那些被抽样的对象。

换句话说，我现在有

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这样的生成器，它是怎么工作的？

Answer 1

来解释一下random.sample是怎么工作的。

random.sample(container, k)这个函数会从一个容器里随机选出k个值。这里的“容器”可以是像列表、元组这样的可迭代对象，也可以是字典里的键或值。它会遍历这个容器，然后随机挑选出这些元素。

比如说，random.sample(xrange(111), 4)会返回类似于[33, 52, 111, 1]这样的结果，因为k = 4，也就是说从0到111的范围里随机选出4个数字。

Answer 2

我猜想这个函数 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

当然，如果我对你代码的理解是错的，那这些内容对你就没什么用，抱歉了，祝你好运 :-)

Answer 3

看起来没有办法可以避免弄清楚索引是如何映射到你的排列上的。如果你不知道这一点，怎么能从你的数组中创建一个随机对象呢？你可以使用你自己提到的那个用 xrange() 的技巧，或者实现一个类，定义 __getitem__() 和 __len__() 方法，然后把这个类的对象作为 population 参数传给 random.sample()。

一些进一步的评论：

• 把 createHugeArray() 转换成生成器并不会有什么好处——random.sample() 就无法再工作了。它需要一个支持 len() 的对象。

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

• 这个 实现 有两个不同的算法，并选择一个占用更少内存的。对于相对较小的 k（也就是在这个情况下），它会把已经选择的索引保存在一个 set 中，如果再随机选择时碰到其中一个，就会重新选择。

编辑：一种完全不同的方法是遍历所有的排列一次，然后决定每个排列是否应该被包含。如果总的排列数是 n，而你想选择 k 个，你可以写

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

这样就会随机选择出正好 k 个排列。