Fast rolling-sum

Question

Ich bin auf der Suche nach einem schnellen Weg, um eine rollende Summe zu berechnen, möglicherweise mit Numpy. Hier ist mein erster Ansatz:

def func1(M, w): 
    Rtn = np.zeros((M.shape[0], M.shape[1]-w+1)) 
    for i in range(M.shape[1]-w+1): 
     Rtn[:,i] = np.sum(M[:, i:w+i], axis=1) 
    return Rtn 

M = np.array([[0., 0., 0., 0., 0., 1., 1., 0., 1., 1., 1., 0., 0.], 
       [0., 0., 1., 0., 1., 0., 0., 0., 0., 0., 0., 1., 1.], 
       [1., 1., 0., 1., 0., 0., 0., 1., 0., 0., 0., 0., 0.]]) 

window_size = 4 
print func1(M, window_size) 

[[ 0. 0. 1. 2. 2. 3. 3. 3. 3. 2.] 
    [ 1. 2. 2. 1. 1. 0. 0. 0. 1. 2.] 
    [ 3. 2. 1. 1. 1. 1. 1. 1. 0. 0.]] 

Ich wollte aus dem Fenster (/ sum) verhindern in der Schleife ist nochmals gemacht und hoffentlich macht es viel schneller, damit ich mit der folgenden Funktion aufkam, die die Summe nur begrenzt die ersten und letzten Elemente des Rollfenster:

def func2(M, w): 
    output = np.zeros((M.shape[0], M.shape[1]-w+1)) 
    sum = np.sum(M[:, 0:w], axis=1) 
    output[:,0] = sum 

    for i in range(w, M.shape[1]): 
     sum = sum + M[:,i]- M[:,i-w] 
     output[:,i-w+1] = sum 
    return output 

Aber zu meiner Überraschung, func2 ist kaum schneller als func1:

In [251]: 
M = np.random.randint(2, size=3000).reshape(3, 1000) 

window_size = 100 
%timeit func1(M, window_size) 
10 loops, best of 3: 20.9 ms per loop 

In [252]: 
%timeit func2(M, w) 
10 loops, best of 3: 15.5 ms per loop 

Fehle ich etwas hier? Kennst du einen besseren, ich meine schneller Weg, dies zu erreichen? hier

Answer 1

Angepasst von @ Antwort Jaime: https://stackoverflow.com/a/14314054/553404

import numpy as np 

def rolling_sum(a, n=4) : 
    ret = np.cumsum(a, axis=1, dtype=float) 
    ret[:, n:] = ret[:, n:] - ret[:, :-n] 
    return ret[:, n - 1:] 

M = np.array([[0., 0., 0., 0., 0., 1., 1., 0., 1., 1., 1., 0., 0.], 
       [0., 0., 1., 0., 1., 0., 0., 0., 0., 0., 0., 1., 1.], 
       [1., 1., 0., 1., 0., 0., 0., 1., 0., 0., 0., 0., 0.]]) 

print(rolling_sum(M)) 

Ausgabe

[[ 0. 0. 1. 2. 2. 3. 3. 3. 3. 2.] 
[ 1. 2. 2. 1. 1. 0. 0. 0. 1. 2.] 
[ 3. 2. 1. 1. 1. 1. 1. 1. 0. 0.]] 

Timings

In [7]: %timeit rolling_sum(M, 4) 
100000 loops, best of 3: 7.89 µs per loop 

In [8]: %timeit func1(M, 4) 
10000 loops, best of 3: 70.4 µs per loop 

In [9]: %timeit func2(M, 4) 
10000 loops, best of 3: 54.1 µs per loop