Суммарная сумма значений в подмассивах между парами индексов

Question

Предположим, у меня есть массив A. У меня есть серия пар индексов (a1, b1), (a2, b2) ... (an, bn)

Я хочу получить все суммы элементов между этими парами. т.е.

sum(A[a1:b1]), sum(A[a2:b2]), sum(A[a3:b3]) ...

С точки зрения времени выполнения, какой самый эффективный способ сделать это?

Спасибо!

Answer 1

Предполагая, что ваши индексные пары хранятся в массиве NumPy indices формы (n, 2) и n довольно велики, вероятно, лучше избегать любого цикла Python:

c = numpy.r_[0, A.cumsum()][indices]
sums = c[:,1] - c[:,0]

Answer 2

Вот еще один способ:

a = np.random.rand(3000)
indices = np.array([[0,3], [9,20], [5,30], [9,33]])
sums = np.add.reduceat(a, indices.ravel())[::2]

assert np.all(sums == np.array([a[i:j].sum() for i,j in indices]))

Приведенный выше cumsum, вероятно, более эффективен, если имеется много индексов.

Answer 3

В первом случае я бы попробовал прямое решение:

[np.sum(A[a:b]) for (a,b) in ab]

, где ab - последовательность пар.

A[a:b] создает представление в массиве;копирование данных не выполняется.

Если это окажется слишком медленным, расскажите, пожалуйста, подробнее о размере A, сколько пар индексов вы ожидаете получить, будь то (a,b)диапазоны имеют тенденцию перекрываться и т. д.

Answer 4

Если у вас много пар индексов, а ваш массив длинный, то кэширование может быть вариантом.Я бы попробовал рекурсивный подход, например

CACHE = {}
def mysum(a, b):
    if (a, b) in CACHE:
        return CACHE[(a, b)]

    if a >= b:
        return 0

    s = A[a] + mysum(a+1, b)
    CACHE[(a, b)] = s
    return s

Не проверено на правильность или эффективность, хотя.Можно также использовать уменьшение верхнего индекса b.