gpt4 book ai didi

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

转载 作者:行者123 更新时间:2023-12-04 04:16:04 26 4
gpt4 key购买 nike

给定一个二维矩阵,例如 [[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')

最佳答案

您可以分别在左半部分和右半部分使用该功能。那么你将只有 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)

关于python - 执行笛卡尔积时如何减少内存消耗?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/60684847/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com