7

I am looking for a fast way to compute a rolling-sum, possibly using Numpy. Here is my first approach:

 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.]]

I wanted to prevent the window (/sum) from being redone in the loop and hopefully make it much faster so I came up with the following function which limits the sum to only the first and last elements of the rolling window:

 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

But to my surprise, func2 is barely faster than 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

Am I missing something here? Do you guys know a better, I mean faster way to achieve this?

Trevor Boyd Smith
  • 18,164
  • 32
  • 127
  • 177
user3329302
  • 627
  • 2
  • 8
  • 12
  • 2
    Since running sum == moving average, possible duplicate: http://stackoverflow.com/questions/14313510/moving-average-function-on-numpy-scipy – Slater Victoroff Feb 02 '15 at 22:48
  • Apart from the division part, but otherwise yes – YXD Feb 02 '15 at 23:00
  • 1
    You're not taking the actual sum. You're looking for a **sliding-window**, not a running-sum. – smci Feb 02 '15 at 23:12
  • I don't think sliding-window on its own is correct either. I think you can have a sum over a sliding window (or a rolling window) or a mean over a sliding window. I propose to edit it to rolling sum, which seems to be closer to the right thing. – YXD Feb 02 '15 at 23:19
  • 1
    I agree with Mr E. Fast rolling-sum is what I had in mind. Sorry about the confusion. – user3329302 Feb 02 '15 at 23:24
  • i changed the title to make clear that this question is not a duplicate of https://stackoverflow.com/questions/13728392/moving-average-or-running-mean – Trevor Boyd Smith Apr 24 '19 at 13:15

1 Answers1

13

Adapted from @Jaime's answer here: 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))

Output

[[ 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
Community
  • 1
  • 1
YXD
  • 31,741
  • 15
  • 75
  • 115