Как уменьшить потребление памяти при выполнении декартового произведения? - PullRequest
Новая
       41

Как уменьшить потребление памяти при выполнении декартового произведения?

2 голосов
/ 14 марта 2020

Учитывая 2-мерную матрицу, такую ​​как [[a,b,c],[d,e,f]...]], я хочу выполнить декартово произведение матрицы, чтобы я мог определить все возможные комбинации.

Для этого конкретного ограничения, когда я использую 2-мерную матрицу с 12 различными подмножествами он использует более 16 мегабайт выделенной памяти, которую я имею. В каждом подмножестве есть три значения, поэтому у меня было бы 3 12 различных комбинаций.

Используемая мной функция декартового произведения: 

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

Я бы хотелось бы узнать, как я могу уменьшить потребление памяти без использования каких-либо внешних библиотек. Пример 2d массива, с которым я бы работал: [['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']]

РЕДАКТИРОВАТЬ: Для справки, ссылка на формулировку проблемы можно найти здесь Постановка проблемы . Вот ссылка на файл возможных имен Допустимые имена .

Финальный код: 

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')

1 Ответ

1 голос
/ 14 марта 2020

Вы можете использовать эту функцию в левой и правой половине отдельно. Тогда у вас будет только 2 × 3 6 комбинаций вместо 3 12 . И они вдвое длиннее, что несколько отменяет этот коэффициент 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)
...