1

I have the following array:

import numpy as np
a = np.array(['a', 'b', 'c','a','a','d','e'])
b = np.array(['a','b'])

actual data stored in the arrays are uuids, example:

123e4567-e89b-12d3-a456-426614174000

I would like to search b in a and get the indices:

array([0, 3, 4, 1])

this solution can work for me:

np.nonzero(b[:, None] == a)[1]

but the problem is I'm dealing with huge arrays (15M in the non-unique and 150k in the unique sub-array with str_ type), so for the given operation I would need 1.8TB of memory which I don't have.

any idea how can I solve this issue or workaround the memory restrictions with my own solution?

thanks.

9
  • Would they be all one character strings?
    – Divakar
    Jul 10, 2020 at 9:18
  • no actually its more like long unique identifier: "abd2-ffb3-ffv3-dda1" (something like this)
    – Andreyn
    Jul 10, 2020 at 9:24
  • So, are all strings of the same length?
    – Divakar
    Jul 10, 2020 at 9:25
  • yes they are of the same length. Its a uuid
    – Andreyn
    Jul 10, 2020 at 9:27
  • Also, do you need output in that specific order of array([0, 3, 4, 1]) or would a sorted order array([0, 1, 3, 4]) be okay?
    – Divakar
    Jul 10, 2020 at 9:28

2 Answers 2

1

Since the order of the indices isn't really relevant, you can use np.isin, and then np.flatnonzero on the results to retrieve the indices where the returned array is True:

a = np.array(['a', 'b', 'c','a','a','d','e'])
b = np.array(['a','b'])

np.flatnonzero(np.isin(a,b))
# array([0, 1, 3, 4], dtype=int64)

This should be reasonably fast and memory efficient (O(len(a))) unlike the broadcasting approach (O(len(a)*len(b))), even with the array sizes mentioned in the question:

a = np.random.randint(0,15e2,int(15e6))
b = np.random.randint(0,150e3,int(150e3))

%timeit np.flatnonzero(np.isin(a,b))
# 2.58 s ± 28.8 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
1

Here's one based on view+lookup -

def map_indices_conststring(a, b):
    a2D = a.view(np.uint8)[::4].reshape(len(a),-1)
    b2D = b.view(np.uint8)[::4].reshape(len(b),-1)
    
    n = b2D.shape[1]
    lookup = np.zeros(256, dtype=bool)
    mask = np.ones(len(a), dtype=bool)
    for i in range(n):
        lookup[b2D[:,i]] = 1
        mask &= lookup[a2D[:,i]]
    out = np.flatnonzero(mask)
    return out

Sample run -

In [46]: a
Out[46]: 
array(['a123', 'b232', 'c434', 'b235', 'a123', 'd223', 'b232'],
      dtype='<U4')

In [47]: b
Out[47]: array(['a123', 'b232'], dtype='<U4')

In [48]: map_indices_conststring(a, b)
Out[48]: array([0, 1, 4, 6])

Timings on string data with 1.5M non-unique and 15K unique sized string arrays -

In [2]: a = np.random.randint(10000000000,99999999999,(1500000)).astype(str)

In [3]: b = np.unique(np.random.randint(10000000000,99999999999,(15000)).astype(str))

In [4]: %timeit map_indices_conststring(a, b)
266 ms ± 2.63 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

# @yatu's soln
In [5]: %timeit np.flatnonzero(np.isin(a,b))
1.03 s ± 3.75 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.