Numpy: Duplicate mask for an array (returning True if we've seen that value before, False otherwise)

user_2601515 0
Viewed 187

I'm looking for a vectorized function that returns a mask with values of True if the value in the array has been seen before and False otherwise.

I'm looking for the fastest solution possible as speed is very important.

For example this is what I would like to see:

array = [1, 2, 1, 2, 3]
mask = [False, False, True, True, False]

So is_duplicate = array[mask] should return [1, 2].

Is there a fast, vectorized way to do this? Thanks!

list numpy python
4 Answers

Approach #1 : With sorting

def mask_firstocc(a):
    sidx = a.argsort(kind='stable')
    b = a[sidx]
    out = np.r_[False,b[:-1] == b[1:]][sidx.argsort()]
    return out

We can use array-assignment to boost perf. further -

def mask_firstocc_v2(a):
    sidx = a.argsort(kind='stable')
    b = a[sidx]
    mask = np.r_[False,b[:-1] == b[1:]]
    out = np.empty(len(a), dtype=bool)
    out[sidx] = mask
    return out

Sample run -

In [166]: a
Out[166]: array([2, 1, 1, 0, 0, 4, 0, 3])

In [167]: mask_firstocc(a)
Out[167]: array([False, False,  True, False,  True, False,  True, False])

Approach #2 : With np.unique(..., return_index)

We can leverage np.unique with its return_index which seems to return the first occurence of each unique elemnent, hence a simple array-assignment and then indexing works -

def mask_firstocc_with_unique(a):
    mask = np.ones(len(a), dtype=bool)
    mask[np.unique(a, return_index=True)[1]] = False
    return mask
user_32938810

Use np.unique

a = np.array([1, 2, 1, 2, 3])
_, ix = np.unique(a, return_index=True)
b = np.full(a.shape, True)
b[ix] = False

In [45]: b
Out[45]: array([False, False,  True,  True, False])
user_101892140

You can achieve that using the enumerate method - which lets you loop through using index + value :

array = [1, 2, 1, 2, 3]

mask = []

for i,v in enumerate(array):
  if array.index(v) == i:
    mask.append(False)
  else:
    mask.append(True)


print(mask)

Output:

[False, False, True, True, False]
user_64907440

Almost by definition, this can't be vectorized. The value of mask for any index depends on the value of array for every value between 0 and index. There may be some algorithm where you expand array into a NxN matrix and do fancy tests, but you're still going to have an O(n^2) algorithm. The straightforward set algorithm is O(n log n).

user_64574070
Related