Python3 как создать список частичных произведений

Question

у меня есть очень длинный список (из больших чисел), скажем, например:

a=[4,6,7,2,8,2]

Мне нужно, чтобы получить этот результат:

b=[4,24,168,336,2688,5376]

где каждый b[i]=a[0]*a[1]...*a[i]

Я пытаюсь сделать это рекурсивно следующим образом:

b=[4] + [ a[i-1]*a[i] for i in range(1,6)] 

но (неправильно) результат: [4, 24, 42, 14, 16, 16]

Я не хочу, чтобы вычислить все продукты каждый раз, мне нужен эффективный способ (если это возможно), потому что список очень длинный

на данный момент это работает для меня:

b=[0]*6 
b[0]=4 

for i in range(1,6): b[i]=a[i]*b[i-1] 

, но это слишком медленно. Есть идеи? Можно ли избежать «для» или ускорить его другим способом?

Answer 1

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

Что я имею в виду:
1) Рассчитайте продукт для первых i - 1 чисел
2) Я-й продукт будет равен a[i] * продукт из последних i - 1 чисел

Этот метод называется dynamic programming

Динамическое программирование (также известная как динамическая оптимизация) представляет собой метод для решения сложной задачи, расчленяя его в коллекцию более простых подзадач, решая каждый из этих SUBPRO притом только один раз, и хранить их решения

Это реализация:

a = [4, 6, 7, 2, 8, 2] 
b = [] 

product_so_far = 1 

for i in range(len(a)): 
    product_so_far *= a[i] 
    b.append(product_so_far) 

print(b) 

Этот алгоритм работает в линейном времени (O(n)), которая является наиболее эффективной сложности вы получите для такой задачи

Если вы хотите немного оптимизации, вы могли бы генерировать b список предопределенной длины (b = [0] * len(a)) и, вместо добавления, вы могли бы сделать это в цикле: b[i] = product_so_far