高效地迭代嵌套列表以查找和

Question

我有一个数组，想检查和是否等于40。问题是这个数组大约有270000000个元素，按顺序进行是不可能的。我遇到的问题是在合理的时间内找到总数。我已经运行了这个程序一夜，它仍然在运行在上午。我怎样才能使这个程序更高效、运行速度更快

以下是我目前的代码：

import numpy as np


def cartesianProduct(arrays):
    la = arrays.shape[0]
    arr = np.empty([la] + [a.shape[0] for a in arrays], dtype="int32")
    for i, a in enumerate(np.ix_(*arrays)):
        arr[i, ...] = a
    return arr.reshape(la, -1).T


rows = np.array(
    [
        [2, 15, 23, 19, 3, 2, 3, 27, 20, 11, 27, 10, 19, 10, 13, 10],
        [22, 9, 5, 10, 5, 1, 24, 2, 10, 9, 7, 3, 12, 24, 10, 9],
        [16, 0, 17, 0, 2, 0, 2, 0, 10, 0, 15, 0, 6, 0, 9, 0],
        [11, 27, 14, 5, 5, 7, 8, 24, 8, 3, 6, 15, 22, 6, 1, 1],
        [10, 0, 2, 0, 22, 0, 2, 0, 17, 0, 15, 0, 14, 0, 5, 0],
        [1, 6, 10, 6, 10, 2, 6, 10, 4, 1, 5, 5, 4, 8, 6, 3],
        [6, 0, 13, 0, 3, 0, 3, 0, 6, 0, 10, 0, 10, 0, 10, 0],
    ],
    dtype="int32",
)

product = cartesianProduct(rows)
combos = []

for row in product:
    if sum(row) == 40:
        combos.append(row)

print(combos)

Answer 1

正如评论中所建议的那样，优化此功能的一种方法是检查子数组的总和是否已超过阈值（在本例中为40）。作为对此的另一个优化，您甚至可以从最大到最小递增地对数组进行排序

检查heapq.nlargest()以获取增量部分排序

Answer 2

我相信你想做的就是所谓的NP难。研究“动态规划”和“子集和”

示例：

• https://www.geeksforgeeks.org/subset-sum-problem-dp-25/
• https://www.techiedelight.com/subset-sum-problem/