У меня есть уравнение вида:
, где a и b - это одномерные массивы размером n и m. Я хочу избежать формирования чего-либо размером n * m на промежуточном этапе, потому что n и m оба очень велики, необходимая память будет слишком дорогой.
Одним из решений является простой цикл Python:
total = 0
for j in range(n):
total += a[j] * b**j
Я ищу нативное решение без петли. Но чтобы решить без цикла питона, я не могу найти функцию numpy, которая будет работать без формирования массива n by m из [0 * b, b, b ** 2, b ** 3, ...] в качестве входных данных .
Edit:
Как указал hpaulj, полиномиальное решение может работать. Я нашел это:
from numpy.polynomial import polynomial
total = polynomial.polyval(b, a)
Это дает те же значения в быстром тесте, и согласно примечаниям к polyval он использует метод Хорнера и кажется оптимальным. На самом деле моя проблема - это сумма по двум измерениям, но я думаю, что это решение будет обобщать.
Редактировать 2:
Поливал, кажется, вызывает
RuntimeWarning: overflow encountered in multiply c0 = c[-i] + c0*x
при меньших размерах массива, чем даже np.outer, вызывает MemoryError. Когда он работает, он гораздо быстрее, чем цикл python.
Редактировать 3:
Игнорировать правки 1 и 2. Следующее выполняется быстрее (на моей машине) с циклом python. polyval по крайней мере кажется эффективным с точки зрения памяти.
import numpy as np
from numpy.polynomial import polynomial
a_size = 3
b_size = 6
a = np.random.rand(10**a_size)
b = np.exp(2j * np.pi * np.random.rand(10**b_size))
start = time.time()
c = polynomial.polyval(b, a)
middle = time.time()
print(middle - start)
c2, b_current = 0, b**0
for i in range(0, a.size):
c2 += a[i] * b_current
b_current *= b
end = time.time()
print(end-middle)