How to sample a numpy array and perform computation on each sample efficiently?

Question

Assume I have a 1d array, what I want is to sample with a moving window and within the window divide each element by the first element.

For example if I have [2, 5, 8, 9, 6] and a window size of 3, the result will be

[[1, 2.5, 4],
 [1, 1.6, 1.8],
 [1, 1.125, 0.75]].

What I'm doing now is basically a for loop

import numpy as np
arr = np.array([2., 5., 8., 9., 6.])
window_size = 3
for i in range(len(arr) - window_size + 1):
  result.append(arr[i : i + window_size] / arr[i])

etc.

When the array is large it is quite slow, I wonder whether there's better ways? I guess there is no way around the O(n^2) complexity, but perhaps numpy has some optimizations that I don't know of.

The code you posted does not yield the result you posted. Also please add initialization of your variables. — Khris
– Khris, Commented Oct 21, 2016 at 6:03
Also maybe use an example that does not lead to a symmetric matrix as this makes it hard to get numpy broadcasting right. — Khris
– Khris, Commented Oct 21, 2016 at 6:29

Divakar · Accepted Answer · 2016-10-21 06:41:39Z

5

Here's a vectorized approach using broadcasting -

N = 3  # Window size
nrows = a.size-N+1
a2D = a[np.arange(nrows)[:,None] + np.arange(N)]
out = a2D/a[:nrows,None].astype(float)

We can also use NumPy strides for a more efficient extraction of sliding windows, like so -

n = a.strides[0]
a2D = np.lib.stride_tricks.as_strided(a,shape=(nrows,N),strides=(n,n))

Sample run -

In [73]: a
Out[73]: array([4, 9, 3, 6, 5, 7, 2])

In [74]: N = 3
    ...: nrows = a.size-N+1
    ...: a2D = a[np.arange(nrows)[:,None] + np.arange(N)]
    ...: out = a2D/a[:nrows,None].astype(float)
    ...: 

In [75]: out
Out[75]: 
array([[ 1.        ,  2.25      ,  0.75      ],
       [ 1.        ,  0.33333333,  0.66666667],
       [ 1.        ,  2.        ,  1.66666667],
       [ 1.        ,  0.83333333,  1.16666667],
       [ 1.        ,  1.4       ,  0.4       ]])

edited Oct 21, 2016 at 6:41

answered Oct 21, 2016 at 6:30

Divakar

222k19 gold badges273 silver badges374 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Khris Over a year ago

Your solution gives the correct result with the test array but fails at other array lengths with an operands could not be broadcast together-error.

Divakar Over a year ago

@Khris Thanks for pointing it out, was a bug indeed in my code. Fixed it.

Khris Over a year ago

I was also working on a solution using strides. Your 2nd solution using strides is twice as fast as your first solution. I timed OP's and your two algorithms with an array length of 10000. OP's was 31.7 ms, your first one was 740 µs, your second one was 378 µs. Mine was the same as your second one so I'm not posting it.

Divakar Over a year ago

@Khris Thanks for testing out! Good to see 80x+ speedup!

Collectives™ on Stack Overflow

How to sample a numpy array and perform computation on each sample efficiently?

1 Answer 1

4 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related