针对十亿种组合的itertools优化

Question

我使用 python 中的 itertools 模块处理十亿个组合的生成。例如，我有

A=[[0.0, 963.07438, 1926.14876], [0.0, 3203.76339, 6407.52678], [0.0, 3231.67715, 6463.3543]]

。

我需要以某种方式生成 A 的很多组合：子嵌套中的每个元素。例如，这里

k=(0.0, 0.0, 0.0), (0.0, 0.0, 3231.67715), (0.0, 0.0, 6463.3543), (0.0, 3203.76339, 0.0), (0.0, 3203.76339, 3231.67715), (0.0, 3203.76339, 6463.3543), (0.0, 6407.52678, 0.0), (0.0, 6407.52678, 3231.67715), (0.0, 6407.52678, 6463.3543), (963.07438, 0.0, 0.0), (963.07438, 0.0, 3231.67715), (963.07438, 0.0, 6463.3543), (963.07438, 3203.76339, 0.0), (963.07438, 3203.76339, 3231.67715), (963.07438, 3203.76339, 6463.3543), (963.07438, 6407.52678, 0.0), (963.07438, 6407.52678, 3231.67715), (963.07438, 6407.52678, 6463.3543), (1926.14876, 0.0, 0.0), (1926.14876, 0.0, 3231.67715), (1926.14876, 0.0, 6463.3543), (1926.14876, 3203.76339, 0.0), (1926.14876, 3203.76339, 3231.67715), (1926.14876, 3203.76339, 6463.3543), (1926.14876, 6407.52678, 0.0), (1926.14876, 6407.52678, 3231.67715), (1926.14876, 6407.52678, 6463.3543)

因此，我有 N^k 个组合，这里 N=3,k=3 ->27。

我可以使用

sums = ((vs,sum(vs)) for vs in itertools.product(*A))

但是，我需要减少这个 k，只保存特定条件的组合：abs(v-12000)<(2000).
例如，我只有 6 种组合：

(0.0, 6407.52678, 6463.3543), (963.07438, 3203.76339, 6463.3543), (963.07438, 6407.52678, 3231.67715), (963.07438, 6407.52678, 6463.3543), (1926.14876, 3203.76339, 6463.3543), (1926.14876, 6407.52678, 3231.67715)

满足这个条件。

最后，我有这个代码：

sums = ((vs,sum(vs)) for vs in itertools.product(*A))

for k,v in sums:
    
    if (abs(v-12000)<(2000)):
        print k

当我有 N=108 和 k=10（十亿种组合）时，这需要很多时间。

如何加速或优化此代码？也许有 itertools 的替代品吗？

谢谢

Answer 1

这是一个动态规划的任务；您可以使用递归公式构建表格：

combs[i, t] = list(itertools.chain.from_iterable(
    ((*c, j) for c in combs[i-1, t-v])
    for j,v in enumerate(A[i-1])
))

建一张桌子；其中

combs[i,t]

是长度为

i

的元组列表，使用

i

的每个

A

第一个子列表中的一个元素，使得这些元素总和为

t

（加上或减去您的容差

tol=2000

） .

您可以初始化表格的边缘：

combs[0, t] = [()] if t <= tol
combs[0, t] = [] if t > tol
combs[i, t] = [] if t + tol < 0
combs[i, t] = [] if t - tol > i * max_element_of_A # this can be refined further using itertools.accumulate on the list of maximums of the lists of A

桌子上会有：

• i

  的每个可能值（0 到 k 之间）占一行；

• t

  的每个可能值占一列（介于 0 到 12000 之间，但您可以将

  A

  中的所有元素四舍五入到个位、数十或数百，以减少可能值的数量）