Find unsorted indices after using numpy.searchsorted

Question

I have a large (millions) array of ID numbers ids, and I want to find the indices where another array of targets (targets) exist in the ids array. For example, if

ids = [22, 5, 4, 0, 100]
targets = [5, 0]

then I want the result:

>>> [1,3]

If I pre-sort the array of ids, then it's easy to find matches using numpy.searchsorted, e.g.

>>> ids = np.array([22, 5, 4, 0, 100])
>>> targets = [5, 0]
>>> sort = np.argsort(ids)
>>> ids[sort]
[0,4,5,22,100]
>>> np.searchsorted(ids, targets, sorter=sort)
[2,0]

But how can I find the reverse mapping to 'unsort' this result? I.e. to map the sorted entries at [2,0] back to where they were before: [1,3].

Answer 1

There are a few answers dancing around this already, but just to make it clear all you need to do is use sort[rank].

# Setup
ids = np.array([22, 5, 4, 0, 100])
targets = np.array([5, 0])

sort = np.argsort(ids)
rank = np.searchsorted(ids, targets, sorter=sort)
print(sort[rank])
# array([1, 3])

Answer 2

Could you just do this?

sort[np.searchsorted(ids, targets, sorter=sort)]

Alternatively:

np.hstack([np.where(ids==x)[0] for x in targets])

both give:

array([1, 3])

Answer 3

I think I've come up with something.

We can construct a 'cipher' or sorts: key = numpy.arange(len(ids)) applying the initial sorter to this key then gives the reverse mapping: revsort = key[np.argsort(ids)]

---

edit: as @birico points out, key[sort] is identical to sort itself!

>>> sort = np.argsort(ids)
>>> ids[sort]
[0,4,5,22,100]
>>> found = np.searchsorted(ids, targets, sorter=sort)
>>> found
[2,0]
>>> sort[found]
[1,3]