[Numpy-discussion] Inverted indices

[Gregor Thalhammer]

Am 07.08.2014 um 13:59 schrieb Gregor Thalhammer <gregor.thalhammer at gmail.com>:

> 
> Am 07.08.2014 um 13:16 schrieb Nicolas P. Rougier <Nicolas.Rougier at inria.fr>:
> 
>> 
>> Hi,
>> 
>> I've a small problem for which I cannot find a solution and I'm quite sure there is an obvious one:
>> 
>> I've an array Z (any dtype) with some data.
>> I've a (sorted) array I (of integer, same size as Z) that tells me the  index of Z[i]  (if necessary, the index can be stored in Z).
>> 
>> Now, I have an arbitrary sequence S of indices (in the sense of I), how do I build the corresponding data ?
>> 
>> Here is a small example:
>> 
>> Z = [(0,0), (1,1), (2,2), (3,3), (4,4))
>> I  = [0, 20, 23, 24, 37]
>> 
>> S = [ 20,20,0,24]
>> -> Result should be [(1,1), (1,1), (0,0),(3,3)]
>> 
>> S = [15,15]
>> -> Wrong (15 not in I) but ideally, I would like this to be converted to [(0,0), (0,0)]
>> 
>> 
>> Any idea ?
>> 
> 
> If I is sorted, I would propose to use a bisection algorithm, faster than linear search:
> 
> Z = array([(0,0), (1,1), (2,2), (3,3), (4,4)])
> I = array([0, 20, 23, 24, 37])
> S = array([ 20,20,0,24,15,27])
> 
> a = zeros(S.shape,dtype=int)
> b = a + S.shape[0]-1
> for i in range(int(log2(S.shape[0]))+2):
>    c = (a+b)>>1
>    sel = I[c]<=S
>    a[sel] = c[sel]
>    b[~sel] = c[~sel]

or even simpler:
c = searchsorted(I, S)
Z[c]

Gregor

> Z[c]
> 
> If I[c] != S, then there is no corresponding index entry in I to match S.
> 
> Gregor

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/numpy-discussion/attachments/20140807/44b478f2/attachment.html>