Itertools 组合，如何让它更快？

Question

我正在编写这个程序，它需要 54 (num1) 个数字并将它们放在一个列表中。然后它取这些数字中的 16 (num2) 个并形成一个列表，其中包含从“num1”c“num2”的所有可能组合中选择的 16 个数字的列表。然后它获取这些列表并生成 4x4 数组。

我的代码可以工作，但是运行宁 54 个数字来获得我想要的所有数组需要很长时间。我知道这一点是因为我已经使用 20 到 40 个数字测试了代码并对其进行了计时。

20 numbers =  0.000055 minutes
30 numbers =  0.045088 minutes
40 numbers =  17.46944 minutes

使用我得到的所有 20 点测试数据，我建立了一个数学模型来预测运行 54 个数字需要多长时间，我得到 1740 分钟 = 29 小时。这已经是预测 38 小时的代码 v1 和实际上使我的机器崩溃的 v0 的改进。

我正在与您联系，尝试让这个运行更快。该程序甚至不是 RAM 密集型的。我有 8GB RAM 和核心 i7 处理器，它根本不会减慢我的机器。它实际上运行与我以前的版本相比非常流畅，我的计算机甚至崩溃了几次。

大家觉得有办法吗？我目前正在抽样以减少处理时间，但如果可能的话，我宁愿根本不抽样。我什至没有打印数组也是为了减少处理时间，我只是打印一个计数器来查看我生成了多少组合。

这是代码：

import numpy as np
import itertools
from itertools import combinations
from itertools import islice
from random import sample

num1 = 30 #ideally this is 54, just using 30 now so you can test it.
num2 = 16
steps = 1454226 #represents 1% of "num1"c"num2" just to reduce processing time for testing.

nums=list()
for i in range(1,num1+1):
    nums.append(i)
#print ("nums: ", nums) #Just to ensure that I am indeed using numbers from 1 to num1

vun=list()
tabl=list()
counter = 0
combin = islice(itertools.combinations(nums, num2),0,None,steps)
for i in set(combin):
    vun.append(sample(i,num2)) 
    counter = counter + 1
    p1=i[0];p2=i[1];p3=i[2];p4=i[3];p5=i[4];p6=i[5];p7=i[6];p8=i[7];p9=i[8]
    p10=i[9];p11=i[10];p12=i[11];p13=i[12];p14=i[13];p15=i[14];p16=i[15]
    tun = np.array ([(p1,p2,p3,p4),(p5,p6,p7,p8),(p9,p10,p11,p12),(p13,p14,p15,p16)])
    tabl.append(tun)
    # print ("TABL:" ,tabl)
# print ("vun: ", vun)
print ("combinations:",counter)

我用这段代码得到的输出是：

combinations: 101

理想情况下，这个数字应该是 2.109492366(10)¹³ 或至少 1%。只要运行是 54x16 并且不需要 29 小时。

Answer 1

仅仅计算组合的数量是微不足道的，因为它是 just a formula:

import math

math.comb(30, 16)
# 145422675

math.comb(54, 16)
# 21094923659355

麻烦的是，存储 30 个案例中的 16 个案例的结果需要大约 64 GB RAM 在我的机器上。您可能但可能没有像我一样闲置的那么多 RAM。 54 个案例中的 16 个案例需要大约 9.3 PB 的 RAM，这是现代架构不支持的。

您将需要采取以下两种方法之一：

限制为 16 in 30 的情况，并且不将任何结果存储到 vun 或 tabl.

优点：在我的测试中可以在 < 5 分钟内完成。

缺点：根本不适用于 16 in 54 的情况，没有额外的处理是可行的
改为 Monte Carlo simulation：生成随机组合，直到达到一些大但可达到的样本数，然后对这些进行数学计算。

优点：速度快，同时支持 16 of 30 和 16 of 54 可能具有相同的时间性能

缺点：根据随机种子，结果会有一些随机变化，应进行统计处理以获得有效性的置信区间。

注意：用于置信区间的公式取决于您打算对这些数字进行哪些实际数学运算，如果您只是寻找估计值，则平均值是一个很好的起点。

我强烈建议选项（2），Monte Carlo模拟。

Answer 2

主要的低效率来自于生成所有组合 (itertools.combinations(nums, num2))，只是为了丢弃其中的大部分组合。

另一种方法是随机生成组合，确保没有重复。

import itertools
import random

def random_combination(iterable, r):
    "Random selection from itertools.combinations(iterable, r)"
    pool = tuple(iterable)
    n = len(pool)
    indices = sorted(random.sample(range(n), r))
    return tuple(pool[i] for i in indices)
    
items = list(range(1, 55))

samples = set()

while len(samples) < 100_000:
    sample = random_combination(items, 16)
    samples.add(sample)

for sample in samples:
    board = list(sample)
    random.shuffle(board)
    board = [board[0:4], board[4: 8], board[8: 12], board[12: 16]]

print("done")

这使用了 this question 答案中的 random_combination 函数，后者又来自 itertools 文档。

代码在大约 10 秒内生成 100,000 个独特的 4x4 样本，至少在我的机器上是这样。

一些注意事项：

每个样本都是一个元组，条目是排序的；这意味着我们可以将它们存储在一个集合中并避免重复。
由于第一点，我们在创建 4x4 棋盘之前对每个样本进行洗牌；后面的代码对这些板没有任何作用，但我想包括它们以了解时间。
如果您要对 space 的大部分进行采样，则可能会出现大量哈希冲突，但无论如何这都不可行，因为涉及的数据量很大（见下文）。

我认为您对此处要实现的目标有些困惑。

54C16 = 2.1 x 10^13 ... 为 all 这些点存储 16 个 8 位整数需要 2.7 x 10^15 位，即 337.5 TB .这超出了本地磁盘上可以存储的内容。

因此，即使覆盖 space 的 1% 也将占用 3TB 的空间……也许可以一键存储在磁盘上。你在问题中暗示你想涵盖 space 的这个比例。显然，这不会发生在 8GB RAM 中。

Itertools 组合，如何让它更快？

Itertools combinations, ¿How to make it faster?

python

performance

combinations

itertools