高效的笛卡尔积，不包括项 [英] Efficient cartesian product excluding items

问题描述

我正在尝试将11个值的所有可能的组合重复80次，但过滤掉总和大于1的情况.下面的代码实现了我正在尝试执行的工作，但需要花费几天的时间:

I'm am trying to get all possible combinations of 11 values repeated 80 times but filter out cases where the sum is above 1. The code below achieves what I'm trying to do but takes days to run:

import numpy as np
import itertools

unique_values = np.linspace(0.0, 1.0, 11)

lst = []
for p in itertools.product(unique_values , repeat=80):
    if sum(p)<=1:
        lst.append(p)

上面的解决方案可以工作，但是需要太多时间.同样，在这种情况下，我将不得不定期将"lst"保存到磁盘中并释放内存，以避免出现任何内存错误.后一部分很好，但是代码需要几天(或几周)才能完成.

The solution above would work but needs way too much time. Also, in this case I would have to periodically save the 'lst' into the disk and free the memory in order to avoid any memory errors. The latter part is fine, but the code needs days (or maybe weeks) to complete.

还有其他选择吗?

推荐答案

好的，这会更有效率，您可以使用此类生成器，并根据需要获取值:

Okay, this would be a bit more efficient, and you can use generator like this, and take your values as needed:

def get_solution(uniques, length, constraint):
    if length == 1:
        for u in uniques[uniques <= constraint + 1e-8]:
            yield u
    else:
        for u in uniques[uniques <= constraint + 1e-8]:
            for s in get_solution(uniques, length - 1, constraint - u):
                yield np.hstack((u, s))

g = get_solution(unique_values, 4, 1)
for _ in range(5):
    print(next(g))

打印

[0. 0. 0. 0.]
[0.  0.  0.  0.1]
[0.  0.  0.  0.2]
[0.  0.  0.  0.3]
[0.  0.  0.  0.4]

与您的功能比较:

def get_solution_product(uniques, length, constraint):
    return np.array([p for p in product(uniques, repeat=length) if np.sum(p) <= constraint + 1e-8])

%timeit np.vstack(list(get_solution(unique_values, 5, 1)))
346 ms ± 29.1 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

%timeit get_solution_product(unique_values, 5, 1)
2.94 s ± 256 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

这篇关于高效的笛卡尔积，不包括项的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！