python - 执行笛卡尔积时如何减少内存消耗？

Question

给定一个二维矩阵，例如 [[a,b,c],[d,e,f]...]] ，我想执行矩阵的笛卡尔积，以便我可以确定所有可能的组合。

对于这个特殊的限制，当我使用一个包含 12 个不同子集的二维矩阵时，它使用的内存超过了我拥有的 16 兆字节。每个子集中有三个值，所以我会有 312 种不同的组合。

我使用的笛卡尔积函数是:

def cartesian_iterative(pools):
    result = [[]]
    for pool in pools:
        result = [x+[y] for x in result for y in pool]
    return result

我想知道如何在不使用任何外部库的情况下减少内存消耗。我将使用的一个示例二维数组是 [['G', 'H', 'I'], ['M', 'N', 'O'], ['D', 'E', 'F'], ['D', 'E', 'F'], ['P', 'R', 'S'], ['D', 'E', 'F'], ['M', 'N', 'O'], ['D', 'E', 'F'], ['D', 'E', 'F'], ['M', 'N', 'O'], ['A', 'B', 'C'], ['D', 'E', 'F']]
编辑:
作为引用，可以在此处找到问题陈述的链接 Problem Statement .这是指向可能名称文件的链接 Acceptable Names .

最终代码:

with open('namenum.in','r') as fin:
    num = str(fin.readline().strip()) #the number being used to determine all combinations

numCount = []
for i in range(len(num)):
    numCount.append(dicti[num[i]]) #creates a 2d array where each number in the initial 'num' has a group of three letters


def cartesian_iterative(pools): #returns the product of a 2d array
    result = [[]]
    for pool in pools:
        result = [x+[y] for x in result for y in pool]
    return result

pos = set() #set of possible names
if len(num) == 12: #only uses more than the allocated memory when the num is 12 digits long.
    '''
    This optimization allows the product to only calculate 2 * 3^6 values, instead of 3**12. This saves a lot of memory
    '''
    rights = cartesian_iterative(numCount[6:])
    for left in cartesian_iterative(numCount[:6]):
        for right in rights:
            a = ''.join(left+right)
            if a in names:
                pos.add(a) #adding name to set
else: #if len(num) < 12, you do not need any other optimizations and can just return normal product 
    for i in cartesian_iterative(numCount):
        a = ''.join(i)
        if a in names:
            pos.add(a)
pos = sorted(pos)


with open('namenum.out','w') as fout: #outputting all possible names
    if len(pos) > 0:
        for i in pos:
            fout.write(i)
            fout.write('\n')
    else:
        fout.write('NONE\n')

Answer 1

您可以分别在左半部分和右半部分使用该功能。那么你将只有 2×36 种组合而不是 312 种组合。而且它们的长度只有原来的一半，甚至抵消了因子 2。

for left in cartesian_iterative(pools[:6]):
    for right in cartesian_iterative(pools[6:]):
        print(left + right)

输出:

['G', 'M', 'D', 'D', 'P', 'D', 'M', 'D', 'D', 'M', 'A', 'D']
['G', 'M', 'D', 'D', 'P', 'D', 'M', 'D', 'D', 'M', 'A', 'E']
['G', 'M', 'D', 'D', 'P', 'D', 'M', 'D', 'D', 'M', 'A', 'F']
['G', 'M', 'D', 'D', 'P', 'D', 'M', 'D', 'D', 'M', 'B', 'D']
...

为了更快，只需计算一次正确的组合:

rights = cartesian_iterative(pools[6:])
for left in cartesian_iterative(pools[:6]):
    for right in rights:
        print(left + right)