计算N重笛卡尔积并筛选和接近1的元组的最快方法是什么

你当前基于itertools.product的暴力生成再过滤的方案，在100个各含100个元素的输入场景下完全不可行：全量笛卡尔积规模为100^100，属于天文数字，无论内存还是算力都不可能支撑，必须用剪枝+动态规划的思路从根源上避免生成无效组合。 #

核心优化思路 #

提前逐层合并数组，每一步仅保留当前和有可能最终凑到目标值的中间结果，直接剪枝所有不可能符合要求的组合，具体剪枝逻辑：

• 提前计算所有剩余未参与合并的数组的最小可能求和值、最大可能求和值
• 遍历当前层的所有中间组合与新数组的元素拼接时，若「当前组合和+新元素值+剩余数组最小和」> 目标值+公差，或「当前组合和+新元素值+剩余数组最大和」< 目标值-公差，直接跳过该组合

可直接使用的Python实现 #

import numpy as np

def filtered_cartesian(p, target=1.0, tol=1e-4):
    # 预处理：每个数组提前排序，方便后续连续剪枝
    p = [sorted(arr) for arr in p]
    # 初始化第一层结果：格式为(当前组合, 当前组合和)
    res = [([num], num) for num in p[0]]
    for idx in range(1, len(p)):
        curr_arr = p[idx]
        # 预计算剩余数组的最小、最大可能和
        remaining_arrs = p[idx+1:]
        remaining_min = sum(arr[0] for arr in remaining_arrs)
        remaining_max = sum(arr[-1] for arr in remaining_arrs)
        new_res = []
        for comb, curr_sum in res:
            for num in curr_arr:
                new_sum = curr_sum + num
                # 剪枝1：当前和加剩余最小和已经超过阈值，后续更大的num也不需要遍历了
                if new_sum + remaining_min > target + tol:
                    break
                # 剪枝2：当前和加剩余最大和还达不到阈值，跳过当前num
                if new_sum + remaining_max < target - tol:
                    continue
                new_res.append( (comb + [num], new_sum) )
        res = new_res
        if not res:
            return np.array([])
    # 最后过滤符合公差要求的结果
    return np.array([comb for comb, s in res if abs(s - target) < tol])

该实现跑你给出的示例输入，输出和原代码完全一致：

输入p = [[0.4,0.389], [0.6,0.611]]
输出：[[0.4 0.6] [0.389 0.611]]

极限性能优化方案 #

如果上述Python实现仍达不到性能要求，可以采用以下方式进一步加速：

• 数值整数化：提前把所有输入值乘以1/tol转为整数，避免浮点数求和的精度误差，同时整数比较速度远高于浮点数
• C++实现：把上述剪枝逻辑用C++实现，编译时开启O2优化，性能可以提升10~100倍，再通过pybind11封装为Python可调用的接口
• 并行优化：可以把第一层的初始组合拆分到多个线程并行处理，进一步提升处理速度

内容的提问来源于stack exchange，提问作者SteRinaldi