efficient loop over numpy array
<p>Versions of this question have already been asked but I have not found a satisfactory answer.</p>

<p><strong>Problem</strong>: given a large numpy vector, find indices of the vector elements which are duplicated (a variation of that could be comparison with tolerance). </p>

<p>So the problem is ~O(N^2) and memory bound (at least from the current algorithm point of view). I wonder why whatever I tried Python is 100x or more slower than an equivalent C code.</p>

<pre><code>import numpy as np
N = 10000
vect = np.arange(float(N))
vect[N/2] = 1
vect[N/4] = 1
dupl = []
print("init done")
counter = 0
for i in range(N):
    for j in range(i+1, N):
        if vect[i] == vect[j]:
            dupl.append(j)
            counter += 1

print("counter =", counter)
print(dupl)
# For simplicity, this code ignores repeated indices 
# which can be trimmed later. Ref output is
# counter = 3
# [2500, 5000, 5000]
</code></pre>

<p>I tried using numpy iterators but they are even worse (~ x4-5)
<a href="http://docs.scipy.org/doc/numpy/reference/arrays.nditer.html" rel="nofollow">http://docs.scipy.org/doc/numpy/reference/arrays.nditer.html</a></p>

<p>Using N=10,000 I'm getting 0.1 sec in C, 12 sec in Python (code above), 40 sec in Python using np.nditer, 50 sec in Python using np.ndindex. I pushed it to N=160,000 and the timing scales as N^2 as expected.</p>

<p>As an alternative to Ami Tavory's answer, you can use a <a href="https://docs.python.org/3/library/collections.html#collections.Counter" rel="nofollow">Counter</a> from the collections package to detect duplicates. On my computer it seems to be even faster. See the function below which can also find different duplicates.</p>

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

def find_duplicates_original(x):
    d = []
    for i in range(len(x)):
        for j in range(i + 1, len(x)):
            if x[i] == x[j]:
                d.append(j)
    return d

def find_duplicates_outer(x):
    a = np.equal.outer(x, x)
    np.fill_diagonal(a, 0)
    return np.flatnonzero(np.any(a, axis=0))

def find_duplicates_counter(x):
    counter = collections.Counter(x)
    values = (v for v, c in counter.items() if c &gt; 1)
    return {v: np.flatnonzero(x == v) for v in values}


n = 10000
x = np.arange(float(n))
x[n // 2] = 1
x[n // 4] = 1

&gt;&gt;&gt;&gt; find_duplicates_counter(x)
{1.0: array([   1, 2500, 5000], dtype=int64)}

&gt;&gt;&gt;&gt; %timeit find_duplicates_original(x)
1 loop, best of 3: 12 s per loop

&gt;&gt;&gt;&gt; %timeit find_duplicates_outer(x)
10 loops, best of 3: 84.3 ms per loop

&gt;&gt;&gt;&gt; %timeit find_duplicates_counter(x)
1000 loops, best of 3: 1.63 ms per loop
</code></pre>

python arrays loops numpy optimization