Determining index each group duplicate values in an array in Python with the fastest way

user_11118581 0
Viewed 109

I want to find an index of each group duplicate value like this:

s = [2,6,2,88,6,...]

The results must return the index from original s: [[0,2],[1,4],..] or the result can show another way.

I find many solutions so I find the fastest way to get duplicate group:

s = np.sort(a, axis=None)
s[:-1][s[1:] == s[:-1]]

But after sort I got wrong index from original s.

In my case, I have ~ 200mil value on the list and I want to find the fastest way to do that. I use an array to store value because I want to use GPU to make it faster.

duplicates numpy python performance
3 Answers

Using hash structures like dict helps.

For example:

import numpy as np
from collections import defaultdict

a=np.array([2,4,2,88,15,4])
table=defaultdict(list)
for ind,num in enumerate(a):
    table[num]+=[ind]

Outputs:

{2: [0, 2], 4: [1, 5], 88: [3], 15: [4]}

If you want to show duplicated elements in the order from small to large:

for k,v in sorted(table.items()):
    if len(v)>1:
        print(k,":",v)

Outputs:

2 : [0, 2]
4 : [1, 5]

The speed is determined by how many different values in the number list.

user_150223020

See if this meets your performance requirements (here, s is your input array):

counts       = np.bincount(s)
cum_counts   = np.add.accumulate(counts)
sorted_inds  = np.argsort(s)

result       = np.split(sorted_inds, cum_counts[:-1])

Notes:

  1. The result would be a list of arrays.

  2. Each of these arrays would contain indices of a repeated value in s. Eg, if the value 13 is repeated 7 times in s, there would be an array with 7 indices among the arrays of result

  3. If you want to ignore singleton values of s (values that occur only once in s), you can pass minlength=2 to np.bincount()

user_85619570

(This is a variation of my other answer. Here, instead of splitting the large array sorted_inds, we take slices from it, so it's likely to have a different kind of performance characteristic)

If s is the input array:

counts       = np.bincount(s)
cum_counts   = np.add.accumulate(counts)
sorted_inds  = np.argsort(s)

result = [sorted_inds[:cum_counts[0]]] + [sorted_inds[cum_counts[i]:cum_counts[i+1]] for i in range(cum_counts.size-1)]
user_85619570
Related