懒惰地在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生成随机样本,并仅生成通过索引实际选择的那些对象.虽然这不是很干净,因为生成的索引是任意的和不必要的,我需要相当hacky逻辑来支持我的generateHugeArray方法.

奖励积分:random.sample实际上如何运作？特别是,如果它不像提前像xrange那样知道人口的大小,它是如何工作的？

Answer 1

似乎没有一种方法可以避免弄清楚索引如何映射到您的排列。如果您不知道这一点，您将如何从数组中创建一个随机对象？您可以使用您自己建议的技巧xrange()，或者实现一个定义__getitem__()和__len__()方法的类，并将该类的 和 对象作为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随机选择精确的排列。