在高层次上，我试图从列表中的 n 个项目的所有组合中对 n_samples 个项目进行采样。在 n 值较小且列表长度相对较小时(n
但是，我的用例要求我生成组合，随机采样几千个元素，然后从列表中删除其中一个组合，然后从较小的列表重新开始。
这会在 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 不等。
非常感谢您提供的任何建议或资源!
最佳答案
根据您的描述，我相信如果您随机选择每个组件，独立于其他组件，并继续直到您拥有所需的样本，您将拥有一个更有效的算法。 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)}
另一种可能性是在长度的乘积范围内生成一个随机数(在本例中为 8 * 10 * 6 * 8)，然后使用整数除法和
mod 将其分解为四个随机索引。另一种可能性是简单地生成您的第一组随机索引，然后在您认为合适的情况下增加这些索引，依次遍历列表。在这种情况下，您将希望列表长度为成对相对素数；您可以通过根据需要添加
None 元素来保证这一点。与 None 的任何组合都将被丢弃。这些想法让你动起来了吗？
关于python - 从大型组合生成器中随机采样，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/55926244/