在高层次上,我试图对列表中 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 不等。
非常感谢您提供的任何建议或资源!
请您参考如下方法:
根据您的描述,我相信如果您随机选择每个组件,独立于其他组件,并继续直到获得必要的样本,您将拥有一个多更有效的算法。 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 的组合都会被丢弃。
这些想法会让您感动吗?
