从大型组合发电机中随机抽样

Question

在较高的层次上，我尝试从列表中的n个项目的所有组合中抽取n个示例项。对于较小的n值和相对较小的列表长度（n<；=5，len（list）<；75），这是很好的-我只需使用itertools生成组合，转换为列表，然后使用随机抽样. 在

然而，我的用例要求我生成组合，随机抽取几千个元素，然后从列表中删除其中一个组合，然后从较小的列表中重新开始。在

这会在n和len（list）值较高时产生问题—对于120个列表项和n=5，此用例意味着我必须多次执行列表转换，因此对于具有约1.9亿个项的生成器，我会受到generator-->list conversion的时间限制。这需要非常长的时间（对于特别糟糕的例子，超过20分钟）。在

用例不需要统计上一致的样本或任何东西，我纯粹使用抽样，因为对于高n和长列表的处理，每一个可能的组合在计算上都是不实际的，而快速处理是非常重要的。在

我转而使用迭代器.islice方法只从生成器中获取第一个n_样本项并使用它们。这大大提高了速度（这个例子花了20分钟，现在需要34秒），但是性能受到了影响。我认为这是由于itertools生成组合的原因-举个例子

list(itertools.combinations(list(range(4)), 2))

生成以下列表： [（0，1），（0，2），（0，3），（1，2），（1，3），（2，3）]

因此，如果我有一个足够长的列表和一个足够大的n，仅仅从生成器中提取100000多个项目，就会得到100000多个项目，其中第一个元素是相同的，这并不理想。正如我所说的，我不需要完美的随机抽样，但是我认为使用这种方法而不是在整个列表中随机抽样会导致性能崩溃。在

基本上，我需要一个好的方法从长度n的所有可能的组合中有效地抽取n个样本项（其中n个样本介于10k到500k之间）（其中n通常在大约2-8个范围内），从一个长度范围从~20到~200不等的列表中。在

非常感谢您提供的任何建议或资源！在

Answer 1

从你描述的情况来看，我相信如果你随机选取每一个组成部分，独立于其他部分，并继续下去，直到你有了必要的样本，你就会有一个更有效的算法。rng（随机数生成器）速度非常快，足以弥补偶尔需要替换的重复项。将您选择的组合存储为一组元组（散列），您可以在固定时间内查找集合包含，使集合成为线性时间。像这样：

from random import randint

# For illustration, the "lsits" include letters, symbols, 3-letter words, and low primes
list1 = "pythonic"
list2 = "~!@#$%^&*()"
list3 = ["dog", "cat", "ape", "red", "cwm", "pox"]
list4 = [2, 3, 5, 7, 11, 13, 17, 19]

combo = [list1, list2, list3, list4]
my_sample = set()
needed_size = 10

while len(my_sample) < needed_size:
    # Choose one random item from each list; that forms an element
    elem = tuple([comp[randint(0, len(comp)-1)] for comp in combo])
    # Using a set elminates duplicates easily
    my_sample.add(elem)

print(my_sample)

输出：

^{pr2}$

另一种可能性是在长度乘积的范围内生成一个随机数（在本例中为8×10×6×8），然后使用整数除法和mod将其分成四个随机索引。在

另一种可能性是简单地生成第一组随机索引，然后在您认为合适的情况下递增这些索引，依次遍历列表。在本例中，您希望您的列表长度是成对的相对素数；您可以根据需要添加一个None元素来保证这一点。任何带有None的组合都将被丢弃。在

这些想法能让你感动吗？在