Fastest way to shift a Numpy array

Question

I'm running some simulations that involve repeatedly comparing values in 2D Numpy arrays with their 'neighbours'; eg. the value at indicie location (y,x) is compared to the value at indicie location (y-1,x) from the same array.

At the moment I am using functions like this:

# example of the typical size of the arrays
my_array = np.ndarray((500,500))    

shapey, shapex = my_array.shape
Yshape = (1, shapex)
Yzeros = np.zeros((1, shapex))

def syf(A, E=True):
    if E == True:
        return np.concatenate((A[1:], A[-1].reshape(Yshape)), axis=0)
    else:
        return np.concatenate((A[1:], Yzeros), axis=0)

shifted_array = syf(my_array)

difference_in_y = shifted_array - my_array

This has the option to use either the edge values or zeros for comparison at the edge of the array. The functions can also do it in either direction in either axis.

Does anybody have any suggestions for a faster way to do this? I've tried np.roll (much slower) and this:

yf = np.ix_(range(shapey)[1:] + [shapey,], range(shapex))
shifted_array = my_array[yf]

which is a little slower.

These functions are called ~200 times a second in a program that takes 10 hours to run so any small speedups are more that welcome!

Thanks.

EDIT:

So if the same differentiation method is required every time the shift function is called then Divakars method below seems to offer a minor speedup, however if just a shifted array is required both that method and the one I use above seem to be equal speed.

I was going to suggest using scipy.ndimage.convolve1d, but for this case (very short filter) it's actually ~2x slower than your current approach. — Joe Kington
– Joe Kington, Commented May 15, 2015 at 17:15
Looking at the code for roll, it generates an index like your yf, and then uses take. — hpaulj
– hpaulj, Commented May 15, 2015 at 17:16
Given that the new array is nearly identical to the old I'm surprised there isn't a faster way to do this via indexing that avoids making a new array in memory. Although I guess if roll uses np.ix_ indexing then there probably isn't a faster alternative though — Siyh
– Siyh, Commented May 16, 2015 at 19:41

Divakar · Accepted Answer · 2015-05-15 15:42:55Z

5

You could have the shifting and differentiating both done in a function call like so -

def syf1(A, E=True):
    out = np.empty_like(A)
    out[:-1] = A[1:] - A[:-1] # Or np.diff(my_array,axis=0)
    if E == True:
        out[-1] = 0
    else:
        out[-1] = -A[-1]
    return out

Thus, the equivalent modified version of syf for runtime comparison purposes would be -

def syf(A, E=True):
    if E == True:
        return np.concatenate((A[1:], A[-1].reshape(Yshape)), axis=0) - A
    else:
        return np.concatenate((A[1:], Yzeros), axis=0) - A

Runtime tests

Let's compare the equivalent version of syf with the proposed approach on runtime performance for the inputs listed in the question code -

In [113]: %timeit syf(my_array)
1000 loops, best of 3: 518 µs per loop

In [114]: %timeit syf1(my_array)
1000 loops, best of 3: 494 µs per loop

So, there is some improvement there!

answered May 15, 2015 at 15:42

Divakar

222k19 gold badges273 silver badges374 bronze badges

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

9 Comments

Matthew Over a year ago

don't forget you can just do if E: !!

Divakar Over a year ago

@Matthew Thanks for the tip. I would leave it as it is for now, as its a minor thing really and until OP comes back with any feedback. Appreciate that tip nevertheless!

Siyh Over a year ago

Thanks for the suggestion Divakar, I tried a slightly different implementation (my code doesn't always differentiate in that way so just used the 'shift') and the two methods are basically identical speedwise... Odd that they are so similar, I guess thats just the memory access time.

Divakar Over a year ago

@Siyh Different way to shift or shift+diff or something else?

Siyh Over a year ago

Sometimes its differentiating as above, but is also > or < comparisons, finding the middle value, addition of surrounding values etc.. Shifting is forwards and backwards in x any y

|

Collectives™ on Stack Overflow

Fastest way to shift a Numpy array

1 Answer 1

9 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

9 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related