Fast way to select from numpy array without intermediate index array
Question: Given the following 2-column array, I want to select items from the second
column that correspond to "edges" in the first column. This is just an
example, as in reality my `a` has potentially millions of rows. So, ideally
I'd like to do this as fast as possible, and without creating intermediate
results.

    
    
    import numpy as np
    a = np.array([[1,4],[1,2],[1,3],[2,6],[2,1],[2,8],[2,3],[2,1],
                  [3,6],[3,7],[5,4],[5,9],[5,1],[5,3],[5,2],[8,2],
                  [8,6],[8,8]])
    

i.e. I want to find the result,

    
    
    desired = np.array([4,6,6,4,2])
    

which is entries in `a[:,1]` corresponding to where `a[:,0]` changes.

One solution is,

    
    
    b = a[(a[1:,0]-a[:-1,0]).nonzero()[0]+1, 1]
    

which gives `np.array([6,6,4,2])`, I could simply prepend the first item, no
problem. However, this creates an intermediate array of the indexes of the
first items. I could avoid the intermediate by using a list comprehension:

    
    
    c = [a[i+1,1] for i,(x,y) in enumerate(zip(a[1:,0],a[:-1,0])) if x!=y]
    

This also gives `[6,6,4,2]`. Assuming a generator-based `zip` (true in Python
3), this doesn't need to create an intermediate representation and should be
very memory efficient. However, the inner loop is not numpy, and it
necessitates generating a list which must be subsequently turned back into a
numpy array.

Can you come up with a numpy-only version with the memory efficiency of `c`
but the speed efficiency of `b`? Ideally only one pass over `a` is needed.

(Note that measuring the speed won't help much here, unless `a` is very big,
so I wouldn't bother with benchmarking this, I just want something that is
theoretically fast and memory efficient. For example, you can assume rows in
`a` are streamed from a file and are slow to access -- another reason to avoid
the `b` solution, as it requires a second random-access pass over `a`.)

Edit: a way to generate a large `a` matrix for testing:

    
    
    from itertools import repeat
    N, M = 100000, 100
    a = np.array(zip([x for y in zip(*repeat(np.arange(N),M)) for x in y ], np.random.random(N*M)))
    


Answer: I am afraid if you are looking to do this in a vectorized way, you can't avoid
an intermediate array, as there's no built-in for it.

Now, let's look for vectorized approaches other than `nonzero()`, which might
be more performant. Going by the same idea of performing differentiation as
with the original code of `(a[1:,0]-a[:-1,0])`, we can use boolean indexing
after looking for non-zero differentiations that correspond to "edges" or
shifts.

Thus, we would have a vectorized approach like so -

    
    
    a[np.append(True,np.diff(a[:,0])!=0),1]
    

**Runtime test**

The original solution `a[(a[1:,0]-a[:-1,0]).nonzero()[0]+1,1]` would skip the
first row. But, let's just say for the sake of timing purposes, it's a valid
result. Here's the runtimes with it against the proposed solution in this post
-

    
    
    In [118]: from itertools import repeat
         ...: N, M = 100000, 2
         ...: a = np.array(zip([x for y in zip(*repeat(np.arange(N),M))\
                                  for x in y ], np.random.random(N*M)))
         ...: 
    
    In [119]: %timeit a[(a[1:,0]-a[:-1,0]).nonzero()[0]+1,1]
    100 loops, best of 3: 6.31 ms per loop
    
    In [120]: %timeit a[1:][np.diff(a[:,0])!=0,1]
    100 loops, best of 3: 4.51 ms per loop
    

Now, let's say you want to include the first row too. The updated runtimes
would look something like this -

    
    
    In [123]: from itertools import repeat
         ...: N, M = 100000, 2
         ...: a = np.array(zip([x for y in zip(*repeat(np.arange(N),M))\
                                  for x in y ], np.random.random(N*M)))
         ...: 
    
    In [124]: %timeit a[np.append(0,(a[1:,0]-a[:-1,0]).nonzero()[0]+1),1]
    100 loops, best of 3: 6.8 ms per loop
    
    In [125]: %timeit a[np.append(True,np.diff(a[:,0])!=0),1]
    100 loops, best of 3: 5 ms per loop
    

