Efficiently index rows of numpy array by exclusion

Question

I need a function that takes a numpy array and a row number as inputs and returns the array (or copy of the array) excluding the given row. I want to do this as efficiently as possible.

# Test array
x = np.repeat(range(10),2).reshape([10,2])

Indexing by slices is very fast in numpy, but as far as I can tell this can only be used to get a contiguous set of rows. For instance, I know I can use slicing to exclude the first row

def index_rows_by_exclusion_firstrow(arr):
    """
    Return slice of arr excluding first row using slice-based indexing
    """
    return arr[1:]

%timeit index_rows_by_exclusion_firstrow(x)   

#The slowest run took 33.84 times longer than the fastest. This could mean that an intermediate result is being cached 
#1000000 loops, best of 3: 204 ns per loop

There is a numpy function, numpy.delete, that does the operation that I'm looking for, but it creates a new array and is therefore very slow.

def index_rows_by_exclusion_npdel(arr, i):
    """
    Return copy of arr excluding single row of position i using
    numpy delete function
    """
    return np.delete(arr, i, 0)

%timeit index_rows_by_exclusion_npdel(x, 1)
#The slowest run took 5.51 times longer than the fastest. This could mean that an intermediate result is being cached 
#100000 loops, best of 3: 9.65 µs per loop

The best I have come up with is indexing by a list, which is about twice as fast as the numpy.delete version of the function, but still ~30 times as slow as slicing

def index_rows_by_exclusion_list(arr, i):
    """
    Return slice of arr excluding single row of position i using
    list-based indexing
    """
    return arr[[ x for x in range(arr.shape[0]) if x != i]]

%timeit index_rows_by_exclusion_list(x,1)
#The slowest run took 12.54 times longer than the fastest. This could mean that an intermediate result is being cached 
#100000 loops, best of 3: 5.82 µs per loop

My question is: is there any faster way to index a numpy array like this? Is there any way to use slicing to index all but one row in an array?

One additional note: the code I'm writing has to be compatible with Cython, which means I can't use boolean masking arrays because Numpy in Cython does not support boolean arrays (this is what I was doing before I realized that boolean arrays don't work in Cython).

Answer 1

Since the result's buffer will have a gap, compared to the original, it will have to be a copy. I believe delete takes different approaches depending on the inputs.

One approach is a boolean index, e.g.

ind = np.ones((10,), bool)
ind[n] = False
A1 = A[ind,:]

Another is to do the equivalent with index values

ind = range(n) + range(n+1:A.shape[0]] # using list concatenate
A1 = A[ind,:]

And as you note, using that index with take may be faster than direct indexing. I doubt if the difference is big, but I haven't timed it recently.

ind could also made by concatenation of 1d arrays. Alternatively, index the two parts, and concatenate them:

 np.concatenate([A[:n,:],A[n+1:],axis=0)

The inputs to concatenate are slices, but result is a copy.

 np.r_[0:n, n+1:A.shape[0]]

is a convenient way of generating the integer index list - but not necessarily a speed solution.

Why is the difference time difference between a view and a copy significant? If you do it a few times in the program, it shouldn't matter. If you do this deletion repeatedly, I'd question the larger program design. Could, you for example, accumulate the deletion indices, and perform the deletion step just once?

---

A few timings:

In [17]: arr=np.arange(1000)

In [18]: timeit arr[np.r_[:500,501:1000]].shape
10000 loops, best of 3: 55.7 us per loop

In [19]: timeit arr.take(np.r_[:500,501:1000]).shape
10000 loops, best of 3: 44.2 us per loop

In [20]: timeit np.r_[:500,501:1000]
10000 loops, best of 3: 36.3 us per loop

In [23]: timeit ind=np.ones(arr.shape[0],bool);ind[500]=False;arr[ind].shape
100000 loops, best of 3: 12.8 us per loop

Oops, the boolean index is faster in this test case.

Best yet:

In [26]: timeit np.concatenate((arr[:500],arr[501:])).shape
100000 loops, best of 3: 4.61 us per loop

Answer 2

I was able to come up with a function that uses np.take that runs faster than the list method.

def index_rows_by_exclusion_nptake(arr, i):
    """
    Return copy of arr excluding single row of position i using
    numpy.take function
    """
    return arr.take(range(i)+range(i+1,arr.shape[0]), axis=0)


%timeit index_rows_by_exclusion_nptake(x,1)
#The slowest run took 9.46 times longer than the fastest. This could mean that an intermediate result is being cached 
#100000 loops, best of 3: 2.95 µs per loop