Inplace changing position of an element in array by shifting others forward - NumPy

Question

After searching I find no native way or current solution to change efficiently the position of an element in a numpy array, which seems to me quite natural operation. For example if I want to move the 3th element in the 1st position it should be like this:

x = np.array([1,2,3,4,5])
f*(x, 3, 1)

print x
array([1,4,2,3,5])

Im looking for a f* function here. This is different of rolling every elements, also for moves in big array I want to avoid copying operation that could be used by using insert and delete operation

Thanks, but Im not sure the solution proposed [here](http://stackoverflow.com/questions/22847410/swap-two-values-in-a-numpy-array): will work, since don't want to swap values. — dtrckd, Oct 30 '16 at 19:37
Partially ok, since if the move occur forward, the shift need to be backward... — dtrckd, Oct 30 '16 at 21:05

Divakar · Answer 1 · 2016-10-30T21:12:46.640

Not sure about the efficiency, but here's an approach using masking -

def change_pos(in_arr, pick_idx, put_idx ):    
    range_arr = np.arange(in_arr.size)  
    tmp = in_arr[pick_idx]
    in_arr[range_arr != put_idx ] = in_arr[range_arr != pick_idx]
    in_arr[put_idx] = tmp

This would support both forward and backward movement.

Sample runs

1) Element moving backward -

In [542]: in_arr
Out[542]: array([4, 9, 3, 6, 8, 0, 2, 1])
                                   *    
In [543]: change_pos(in_arr,6,1)

In [544]: in_arr
Out[544]: array([4, 2, 9, 3, 6, 8, 0, 1])
                    ^

2) Element moving forward -

In [546]: in_arr
Out[546]: array([4, 9, 3, 6, 8, 0, 2, 1])
                    *
In [547]: change_pos(in_arr,1,6)

In [548]: in_arr
Out[548]: array([4, 3, 6, 8, 0, 2, 9, 1])
                                   ^

Thanks, this is quite functionnal for 1-d arrays. – dtrckd Oct 30 '16 at 23:47 — dtrckd, Oct 30 '16 at 23:47

score 2 · Answer 2 · edited May 23 '17 at 12:16

With the small example, this wholesale copy tests faster than @Divakar's masked in-place copy:

def foo4(arr, i,j):
    L=arr.shape[0]
    idx=np.concatenate((np.arange(j),[i],np.arange(j,i),np.arange(i+1,L)))
    return arr[idx]

I didn't try to make it work for forward moves. An analogous inplace function runs at about the same speed as Divakar's.

def foo2(arr, i,j):
    L=arr.shape[0]
    tgt=np.arange(j,i+1)
    src=np.concatenate([[i],np.arange(j,i)])
    arr[tgt]=arr[src]

But timings could well be different if the array was much bigger and the swap involved a small block in the middle.

Since the data for an array is stored in a contiguous block of memory, elements cannot change place without some sort of copy. You'd have implement lists as a linked list to have a no-copy form of movement.

It just occurred to me that there are some masked copyto and place functions, that might make this sort of copy/movement faster. But I haven't worked with those much.

https://stackoverflow.com/a/40228699/901925

================

np.roll does

idx = np.concatenate((np.arange(2,5),np.arange(2)))
#  array([2, 3, 4, 0, 1])
np.take(a, idx)   # or a[idx]

Thanks for the insight. I don't now how np.roll works internally in terms of copy, but maybe one way to do it is by using np.roll on the sub-array to be shifted and then assigning 'pick' and 'put' values. — dtrckd, Oct 30 '16 at 23:49
I added a summary of `roll` - it constructs an index and uses `take`. — hpaulj, Oct 31 '16 at 00:44

paddyg · Accepted Answer · 2016-11-01T20:15:50.100

In the past I have found the simple numpy indexing i.e. a[:-1]=a[1:] to be faster than most alternatives (including np.roll()). Comparing the two other answers with an 'in place' shift I get:

for shift from 40000 to 100

1.015ms divakar
1.078ms hpaulj
29.7micro s in place shift (34 x faster)

for shift from 40000 to 39900

0.975ms divakar
0.985ms hpaulj
3.47micro s in place shift (290 x faster)

timing comparison using:

import timeit

init = '''
import numpy as np

def divakar(in_arr, pick_idx, put_idx ):    
    range_arr = np.arange(in_arr.size)  
    tmp = in_arr[pick_idx]
    in_arr[range_arr != put_idx ] = in_arr[range_arr != pick_idx]
    in_arr[put_idx] = tmp

def hpaulj(arr, fr, to):
  L = arr.shape[0]
  idx = np.concatenate((np.arange(to), [fr], np.arange(to, fr), np.arange(fr+1, L)))
  return arr[idx]

def paddyg(arr, fr, to):
  if fr >= arr.size or to >= arr.size:
    return None
  tmp = arr[fr].copy()
  if fr > to:
    arr[to+1:fr+1] = arr[to:fr]
  else:
    arr[fr:to] = arr[fr+1:to+1]
  arr[to] = tmp
  return arr

a = np.random.randint(0, 1000, (100000))
'''


fns = ['''
divakar(a, 40000, 100)
''', '''
hpaulj(a, 40000, 100)
''', '''
paddyg(a, 40000, 100)
''']

for f in fns:
  print(timeit.timeit(f, setup=init, number=1000))

This is not valid, since swaping values is not the question, the element that moves imply partially rolling... — dtrckd, Oct 30 '16 at 21:24
@dtrckd sorry, modified answer with a "roll" line. I have found this approach to almost always be faster than things like np.roll() i.e. save the end value then x[:-1] = x[1:] and write back the end value. — paddyg, Oct 31 '16 at 11:16
By adding an argument (axis=0), removing the test on size, and adding this line: arr = arr.T if axis == 1 else arr; add to your function the nice ability to work on multi dimensionnal array ;) — dtrckd, Nov 02 '16 at 00:34

Inplace changing position of an element in array by shifting others forward - NumPy

3 Answers3