Есть ли лучший способ рассчитать продукт из нескольких списков?

Question

Мне нужно получить все возможные комбинации, основанные на n-количестве входных списков, и сделать что-то с ними.

текущий пример кода:

import itertools

# example inputs
list_small = [1, 2, 3]
list_medium = [444, 666, 242]
list_huge = [1680, 7559, 5573, 43658, 530, 11772, 284, 50078, 783, 37809, 6740, 37765, 74492, 50078, 783, 37809, 6740, 37765, 74492]

# out of the input list, I need to generate all numbers from 0 to the current list element
# e.g. if I have 6, I need to get [0, 1, 2, 3, 4, 5, 6]
# if I get a list [1, 2, 3], the output will be [[0, 1], [0, 1, 2], [0, 1, 2, 3]]
# I achieved this by doing it with xrange: [x for x in xrange(0, current_list_element + 1)]
# after that, I need to generate all possible combinations using the generated lists
# I managed to do this by using itertools.product()

# print this to get all possible combinations
# print list(itertools.product(*[[x for x in xrange(0, current_list_element + 1)] for current_list_element in list_medium]))

cumulative_sum = 0
for current_combination in itertools.product(*[[x for x in xrange(0, current_list_element + 1)] for current_list_element in list_medium]):
    # now I need to do some calculations to the current combination
    # e.g. get sum of all combinations, this is just an example
    cumulative_sum += sum(current_combination)

    # another example
    # get XOR sum of current combination, more at https://en.wikipedia.org/wiki/Exclusive_or
    print reduce(operator.xor, current_combination, 0)

# runs fast for list_small, then takes some time for list_medium and then takes ages for list_huge
print cumulative_sum

Это прекрасно работает для небольших списков, но занимает бесконечность для больших списков / или выдает ошибку времени выполнения. Есть ли лучший способ сделать это? Лучший способ получить все комбинации? Или я неправильно использую xrange?

Я попробовал это с Python 2.7 и Pypy 2.

РЕДАКТИРОВАТЬ: благодаря @famagusta я избавился от xrange, но проблема все еще остается

import itertools

# example inputs
list_small = [1, 2, 3]
list_medium = [444, 666, 242]
list_huge = [1680, 7559, 5573, 43658, 530, 11772, 284, 50078, 783, 37809, 6740, 37765, 74492, 50078, 783, 37809, 6740, 37765, 74492]

max_element = max(get_input_stones)
combo_list = range(0, max_element + 1)

cumulative_sum = 0
for current_combination in itertools.product(*combo_list):
    # now I need to do some calculations to the current combination
    # e.g. get sum of all combinations, this is just an example
    cumulative_sum += sum(current_combination)

    # another example
    # get XOR sum of current combination, more at https://en.wikipedia.org/wiki/Exclusive_or
    print reduce(operator.xor, current_combination, 0)

# runs fast for list_small, then takes some time for list_medium and then takes ages for list_huge
print cumulative_sum

Answer 1

Создание таких вложенных списков может привести к проблемам с ограничением памяти. Вместо многократного создания подсписков, вы можете использовать только один супер-список, созданный из самого большого числа в списке. Просто храните индексы, где меньшие элементы остановились бы.

Например, [1, 6, 10] - [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10], [1, 6, 10]

Второй список говорит вам, где остановиться в первом списке, чтобы извлечь интересующие списки для вычислений

Это должно сэкономить вам немного места.

list_small = [1, 2, 3]
list_medium = [444, 666, 242]
list_huge = [1680, 7559, 5573, 43658, 530, 11772, 284, 50078, 783, 37809, 6740, 37765, 74492, 50078, 783, 37809, 6740, 37765, 74492]

max_element = max(list_huge)   # being lazy here - write a max function
combo_list = range(0, max_element + 1)  # xrange does not support slicing

cumulative_sum = 0
for element in list_huge:
    cumulative_sum += sum(combo_list[:element])

print(cumulative_sum)