从大型组合生成器中随机采样

Question

在高层次上，我试图从列表中的 n 个项目的所有组合中对 n_samples 个项目进行采样。在 n 值较小且列表长度相对较小时（n <= 5，len(list) < 75），这很好 - 我只是使用 itertools 生成组合，转换为列表，然后使用 random.sample 随机采样正确的数字.

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

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

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

我切换到使用 iterator.islice 方法只从生成器中获取第一个 n_samples 项并使用它们。这显着提高了速度（之前需要 20 分钟的示例现在需要 34 秒），但性能受到了打击。我认为这是由于 itertools 如何生成组合 - 例如，

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

产生这个列表： [(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]

所以看起来如果我有一个足够长的列表和一个足够大的 n，仅仅通过将它们从生成器中拉出来采样甚至 100,000+ 个项目将导致 100,000+ 个项目，其中第一个元素是相同的，这是不理想的。正如我所说，我不需要完美的随机抽样，但我认为使用这种方法而不是在整个列表中随机抽样导致我的性能崩溃是由于这个原因。

基本上，我需要一种好方法来有效地从长度为 n 的所有可能组合（其中 n 通常在 2-8 左右的范围内）中对 n_samples 项（其中 n_samples 介于 10k 到 500k 之间）从长度列表中进行采样从 ~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)

输出：

{('h', '$', 'pox', 7),
 ('y', '(', 'cat', 11),
 ('n', '@', 'cat', 7),
 ('i', '^', 'ape', 13),
 ('y', '#', 'pox', 11),
 ('o', '%', 'dog', 7),
 ('p', '^', 'cwm', 13),
 ('c', '*', 'dog', 19),
 ('o', ')', 'pox', 11),
 ('h', '~', 'cat', 5)}

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

另一种可能性是简单地生成第一组随机索引，然后根据需要增加这些索引，依次逐步浏览列表。在这种情况下，您将希望列表长度成对互质；None您可以通过根据需要添加元素来保证这一点。任何与 a 的组合None都会被丢弃。

这些想法能让你感动吗？