Efficiently handling duplicates in a Python list
<p>I'm looking to compactly represent duplicates in a Python list / 1D numpy array. For instance, say we have </p>

<pre><code> x = np.array([1, 0, 0, 3, 3, 0])
</code></pre>

<p>this array has several duplicate elements, that can be represented with a </p>

<pre><code> group_id = np.array([0, 1, 1, 2, 2, 1])
</code></pre>

<p>so that all duplicates in a given cluster are found with <code>x[group_id==&lt;some_id&gt;]</code>.</p>

<p>The list of duplicate pairs can be efficiently computed with sorting, </p>

<pre><code>s_idx = np.argsort(x)
diff_idx = np.nonzero(x[s_idx[:-1]] == x[s_idx[1:]])[0]
</code></pre>

<p>where the pair <code>s_idx[diff_idx]</code> &lt;-> <code>s_idx[diff_idx+1]</code> correspond to the indices in the original array that are duplicates. 
(here <code>array([1, 2, 3])</code> &lt;-> <code>array([2, 5, 4])</code>).</p>

<p>However, I'm not sure how to efficiently calculate <code>cluster_id</code> from this linkage information for large arrays sizes (<code>N &gt; 10â¶</code>).</p>

<p><strong>Edit:</strong> as suggested by <strong>@Chris_Rands</strong>, this can indeed be done with <code>itertools.groupby</code>,</p>

<pre><code> import numpy as np
 import itertools

 def get_group_id(x):
     group_id = np.zeros(x.shape, dtype='int')
     for i, j in  itertools.groupby(x):
         j_el = next(j)
         group_id[x==j_el] = i
     return group_id
</code></pre>

<p>however the scaling appears to be <strong>O(n^2)</strong>, and this would not scale to my use case (<code>N &gt; 10â¶</code>),</p>

<pre><code>  for N in [50000, 100000, 200000]:
      %time _ = get_group_id(np.random.randint(0, N, size=N))

  CPU times: total: 1.53 s
  CPU times: total: 5.83 s
  CPU times: total: 23.9 s
</code></pre>

<p>and I belive using the duplicate linkage information would be more efficient as computing duplicate pairs for <code>N=200000</code> takes just 6.44 Âµs in comparison.</p>

<p>You could use <a href="https://docs.scipy.org/doc/numpy/reference/generated/numpy.unique.html" rel="nofollow"><code>numpy.unique</code></a>:</p>

<pre><code>In [13]: x = np.array([1, 0, 0, 3, 3, 0])

In [14]: values, cluster_id = np.unique(x, return_inverse=True)

In [15]: values
Out[15]: array([0, 1, 3])

In [16]: cluster_id
Out[16]: array([1, 0, 0, 2, 2, 0])
</code></pre>

<p>(The cluster IDs are assigned in the order of the sorted unique values, not in the order of a value's first appearance in the input.)</p>

<p>Locations of the items in cluster 0:</p>

<pre><code>In [22]: cid = 0

In [23]: values[cid]
Out[23]: 0

In [24]: (cluster_id == cid).nonzero()[0]
Out[24]: array([1, 2, 5])
</code></pre>

python algorithm numpy grouping graph-algorithm