How to get a reverse mapping in numpy in O(1)?

Question

I have a numpy array, whose elements are unique, for example:

b = np.array([5, 4, 6, 8, 1, 2])

(Edit2: b can have large numbers, and float numbers. The above example is there for simplicity)

I am getting numbers, that are elements in b.

I want to find their index in b, meaning I want a reverse mapping, from value to index, in b.

I could do

for number in input:
    ind = np.where(number==b)

which would iterate over the entire array every call to where.

I could also create a dictionary,

d = {}
for i, element in enumerate(list(b)):
    d[element] = i

I could create this dictionary at "preprocessing" time, but still I would be left with a strange looking dictionary, in a mostly numpy code, which seems (to me) not how numpy is meant to be used.

How can I do this reverse mapping in numpy?

usage (O(1) time and memory required):

print("index of 8 is: ", foo(b, 8))

---

• Edit1: not a duplicate of this

Using in1d like explained here doesn't solve my problem. Using their example:

b = np.array([1, 2, 3, 10, 4])

I want to be able to find for example 10's index in b, at runtime, in O(1).

Doing a pre-processing move

mapping = np.in1d(b, b).nonzero()[0]

>> [0, 1, 2, 3, 4]

(which could be accomplished using np.arange(len(b)))

doesn't really help, because when 10 comes in as input, It is not possible to tell its index in O(1) time with this method.

Answer 1

It's simpler than you think, by exploiting numpy's advanced indexing.

What we do is make our target array and just assign usign b as an index. We'll assign the indices we want by using arange.

>>> t = np.zeros((np.max(b) + 1,))
>>> t[b] = np.arange(0, b.size)
>>> t
array([0., 4., 5., 0., 1., 0., 2., 0., 3.])

You might use nans or -1 instead of zeros to construct the target to help detect invalid lookups.

Memory usage: this is optimally performant in both space and time as it's handled entirely by numpy.

If you can tolerate collisions, you can implement a poor man's hashtable. Suppose we have currencies, for example:

h = np.int32(b * 100.0) % 101  # Typically some prime number
t = np.zeros((101,))
t[h] = np.arange(0, h.size)

# Retrieving a value v; keep in mind v can be an ndarray itself.
t[np.int32(v * 100.0) % 101]

You can do any other steps to munge the address if you know what your dataset looks like.

This is about the limit of what's useful to do with numpy.