Waste roll in several sizes

Question

I need to shift a three-dimensional array by a 3D displacement vector for the algorithm. At the moment, I am using this (very ugly possible) method:

shiftedArray = np.roll(np.roll(np.roll(arrayToShift, shift[0], axis=0) , shift[1], axis=1), shift[2], axis=2) 

Which works, but means I call 3 rolls! (58% of my algorithm time is spent on them, according to my profiling)

From the Numpy.roll docs:

Options:
shift: int

axis: int optional

There is no mention of the array parameter in the parameter ... Therefore, I can’t have multidimensional rolling?

I thought I could just call such a function (sounds like a thing to do with Numpy):

 np.roll(arrayToShift,3DshiftVector,axis=(0,1,2)) 

Maybe with a modified version of my array? but how can I calculate the shift vector? and is this shift really the same?

I am surprised that I did not find an easy solution for this, since I thought it would be a fairly ordinary thing (well, not so, but ...)

So, how do we - relatively - effectively shift ndarray by an N-dimensional vector?

Answer 1

I think scipy.ndimage.interpolation.shift will do what you want from docs

shift: float or sequence, optional

Axial shift. If the float, the shift is the same for each axis. If a sequence, the shift should contain one value for each axis.

This means that you can do the following:

 from scipy.ndimage.interpolation import shift import numpy as np arrayToShift = np.reshape([i for i in range(27)],(3,3,3)) print('Before shift') print(arrayToShift) shiftVector = (1,2,3) shiftedarray = shift(arrayToShift,shift=shiftVector,mode='wrap') print('After shift') print(shiftedarray) 

What gives,

 Before shift [[[ 0 1 2] [ 3 4 5] [ 6 7 8]] [[ 9 10 11] [12 13 14] [15 16 17]] [[18 19 20] [21 22 23] [24 25 26]]] After shift [[[16 17 16] [13 14 13] [10 11 10]] [[ 7 8 7] [ 4 5 4] [ 1 2 1]] [[16 17 16] [13 14 13] [10 11 10]]] 

Answer 2

Theoretically, using scipy.ndimage.interpolation.shift described by @Ed Smith should work, but due to an open error ( https://github.com/scipy/scipy/issues/1323 ), it does not produce a result equivalent to several calls np.roll .

---

UPDATE: "Multi-roll" was added to numpy.roll in numpy version 1.12.0. Here is a two-dimensional example in which the first axis is rolled in one position, and the second axis is rolled in three positions:

 In [7]: x = np.arange(20).reshape(4,5) In [8]: x Out[8]: array([[ 0, 1, 2, 3, 4], [ 5, 6, 7, 8, 9], [10, 11, 12, 13, 14], [15, 16, 17, 18, 19]]) In [9]: numpy.roll(x, [1, 3], axis=(0, 1)) Out[9]: array([[17, 18, 19, 15, 16], [ 2, 3, 4, 0, 1], [ 7, 8, 9, 5, 6], [12, 13, 14, 10, 11]]) 

This makes the code below obsolete. I will leave it there for posterity.

---

The code below defines a function that I call multiroll that does what you want. Here's an example in which it is applied to an array with the form (500, 500, 500):

 In [64]: x = np.random.randn(500, 500, 500) In [65]: shift = [10, 15, 20] 

Use multiple calls to np.roll to generate the expected result:

 In [66]: yroll3 = np.roll(np.roll(np.roll(x, shift[0], axis=0), shift[1], axis=1), shift[2], axis=2) 

Generate the shifted array with multiroll :

 In [67]: ymulti = multiroll(x, shift) 

Make sure we get the expected result:

 In [68]: np.all(yroll3 == ymulti) Out[68]: True 

For an array of this size, making three calls to np.roll is almost three times slower than calling multiroll :

 In [69]: %timeit yroll3 = np.roll(np.roll(np.roll(x, shift[0], axis=0), shift[1], axis=1), shift[2], axis=2) 1 loops, best of 3: 1.34 s per loop In [70]: %timeit ymulti = multiroll(x, shift) 1 loops, best of 3: 474 ms per loop 

Here is the definition of multiroll :

 from itertools import product import numpy as np def multiroll(x, shift, axis=None): """Roll an array along each axis. Parameters ---------- x : array_like Array to be rolled. shift : sequence of int Number of indices by which to shift each axis. axis : sequence of int, optional The axes to be rolled. If not given, all axes is assumed, and len(shift) must equal the number of dimensions of x. Returns ------- y : numpy array, with the same type and size as x The rolled array. Notes ----- The length of x along each axis must be positive. The function does not handle arrays that have axes with length 0. See Also -------- numpy.roll Example ------- Here a two-dimensional array: >>> x = np.arange(20).reshape(4,5) >>> x array([[ 0, 1, 2, 3, 4], [ 5, 6, 7, 8, 9], [10, 11, 12, 13, 14], [15, 16, 17, 18, 19]]) Roll the first axis one step and the second axis three steps: >>> multiroll(x, [1, 3]) array([[17, 18, 19, 15, 16], [ 2, 3, 4, 0, 1], [ 7, 8, 9, 5, 6], [12, 13, 14, 10, 11]]) That equivalent to: >>> np.roll(np.roll(x, 1, axis=0), 3, axis=1) array([[17, 18, 19, 15, 16], [ 2, 3, 4, 0, 1], [ 7, 8, 9, 5, 6], [12, 13, 14, 10, 11]]) Not all the axes must be rolled. The following uses the `axis` argument to roll just the second axis: >>> multiroll(x, [2], axis=[1]) array([[ 3, 4, 0, 1, 2], [ 8, 9, 5, 6, 7], [13, 14, 10, 11, 12], [18, 19, 15, 16, 17]]) which is equivalent to: >>> np.roll(x, 2, axis=1) array([[ 3, 4, 0, 1, 2], [ 8, 9, 5, 6, 7], [13, 14, 10, 11, 12], [18, 19, 15, 16, 17]]) """ x = np.asarray(x) if axis is None: if len(shift) != x.ndim: raise ValueError("The array has %d axes, but len(shift) is only " "%d. When 'axis' is not given, a shift must be " "provided for all axes." % (x.ndim, len(shift))) axis = range(x.ndim) else: # axis does not have to contain all the axes. Here we append the # missing axes to axis, and for each missing axis, append 0 to shift. missing_axes = set(range(x.ndim)) - set(axis) num_missing = len(missing_axes) axis = tuple(axis) + tuple(missing_axes) shift = tuple(shift) + (0,)*num_missing # Use mod to convert all shifts to be values between 0 and the length # of the corresponding axis. shift = [s % x.shape[ax] for s, ax in zip(shift, axis)] # Reorder the values in shift to correspond to axes 0, 1, ..., x.ndim-1. shift = np.take(shift, np.argsort(axis)) # Create the output array, and copy the shifted blocks from x to y. y = np.empty_like(x) src_slices = [(slice(n-shft, n), slice(0, n-shft)) for shft, n in zip(shift, x.shape)] dst_slices = [(slice(0, shft), slice(shft, n)) for shft, n in zip(shift, x.shape)] src_blks = product(*src_slices) dst_blks = product(*dst_slices) for src_blk, dst_blk in zip(src_blks, dst_blks): y[dst_blk] = x[src_blk] return y 

Answer 3

I believe that roll slow because a collapsed array cannot be expressed as representing the original data as a slice operation or shape change. Thus, the data is copied every time. For reference, see https://scipy-lectures.imtqy.com/advanced/advanced_numpy/#life-of-ndarray

What might be worth trying to process your array first (with "wrap" mode) and then use slices in the filled array to get a shiftedArray : http://docs.scipy.org/doc/numpy/reference/generated/numpy.pad. html

Answer 4

take in wrap mode can be used, and I think that it does not change the array in memory.

Here is an implementation using @EdSmith inputs:

 arrayToShift = np.reshape([i for i in range(27)],(3,3,3)) shiftVector = np.array((1,2,3)) ind = 3-shiftVector np.take(np.take(np.take(arrayToShift,range(ind[0],ind[0]+3),axis=0,mode='wrap'),range(ind[1],ind[1]+3),axis=1,mode='wrap'),range(ind[2],ind[2]+3),axis=2,mode='wrap') 

which gives the same thing as OP:

 np.roll(np.roll(np.roll(arrayToShift, shift[0], axis=0) , shift[1], axis=1),shift[2], axis=2) 

gives:

 array([[[21, 22, 23], [24, 25, 26], [18, 19, 20]], [[ 3, 4, 5], [ 6, 7, 8], [ 0, 1, 2]], [[12, 13, 14], [15, 16, 17], [ 9, 10, 11]]])