检查 python 列表/numpy ndarray 中是否存在重复项的最快方法

我想确定我的列表（实际上是numpy.ndarray) 在尽可能最快的执行时间内包含重复项。请注意，我并不关心删除重复项，我只是想知道是否有重复项。

注意：如果这不是重复的，我会感到非常惊讶，但我已尽力而为却找不到。最近的是这个问题 https://stackoverflow.com/questions/89178/in-python-what-is-the-fastest-algorithm-for-removing-duplicates-from-a-list-so and 这个问题 https://stackoverflow.com/questions/480214/how-do-you-remove-duplicates-from-a-list-whilst-preserving-order，两者都要求返回唯一列表。

以下是我想到的四种方法。

TL;DR：如果您期望很少（小于 1/1000）的重复项：

def contains_duplicates(X):
    return len(np.unique(X)) != len(X)

如果您期望频繁（超过 1/1000）重复：

def contains_duplicates(X):
    seen = set()
    seen_add = seen.add
    for x in X:
        if (x in seen or seen_add(x)):
            return True
    return False

第一种方法是提前退出这个答案 https://stackoverflow.com/a/89250/3996580它想要返回唯一的值，其中第二个与应用于这个答案 https://stackoverflow.com/a/480227/3996580.

>>> import numpy as np
>>> X = np.random.normal(0,1,[10000])
>>> def terhorst_early_exit(X):
...:     elems = set()
...:     for i in X:
...:         if i in elems:
...:             return True
...:         elems.add(i)
...:     return False
>>> %timeit terhorst_early_exit(X)
100 loops, best of 3: 10.6 ms per loop
>>> def peterbe_early_exit(X):
...:     seen = set()
...:     seen_add = seen.add
...:     for x in X:
...:         if (x in seen or seen_add(x)):
...:             return True
...:     return False
>>> %timeit peterbe_early_exit(X)
100 loops, best of 3: 9.35 ms per loop
>>> %timeit len(set(X)) != len(X)
100 loops, best of 3: 4.54 ms per loop
>>> %timeit len(np.unique(X)) != len(X)
1000 loops, best of 3: 967 µs per loop

如果你从一个普通的 Python 列表开始，而不是一个numpy.ndarray?

>>> X = X.tolist()
>>> %timeit terhorst_early_exit(X)
100 loops, best of 3: 9.34 ms per loop
>>> %timeit peterbe_early_exit(X)
100 loops, best of 3: 8.07 ms per loop
>>> %timeit len(set(X)) != len(X)
100 loops, best of 3: 3.09 ms per loop
>>> %timeit len(np.unique(X)) != len(X)
1000 loops, best of 3: 1.83 ms per loop

编辑：如果我们事先期望重复项的数量怎么办？

上述比较是在以下假设下进行的：a）可能没有重复项，或者 b）我们更担心最坏的情况而不是平均情况。

>>> X = np.random.normal(0, 1, [10000])
>>> for n_duplicates in [1, 10, 100]:
>>>     print("{} duplicates".format(n_duplicates))
>>>     duplicate_idx = np.random.choice(len(X), n_duplicates, replace=False)
>>>     X[duplicate_idx] = 0
>>>     print("terhost_early_exit")
>>>     %timeit terhorst_early_exit(X)
>>>     print("peterbe_early_exit")
>>>     %timeit peterbe_early_exit(X)
>>>     print("set length")
>>>     %timeit len(set(X)) != len(X)
>>>     print("numpy unique length")
>>>     %timeit len(np.unique(X)) != len(X)
1 duplicates
terhost_early_exit
100 loops, best of 3: 12.3 ms per loop
peterbe_early_exit
100 loops, best of 3: 9.55 ms per loop
set length
100 loops, best of 3: 4.71 ms per loop
numpy unique length
1000 loops, best of 3: 1.31 ms per loop
10 duplicates
terhost_early_exit
1000 loops, best of 3: 1.81 ms per loop
peterbe_early_exit
1000 loops, best of 3: 1.47 ms per loop
set length
100 loops, best of 3: 5.44 ms per loop
numpy unique length
1000 loops, best of 3: 1.37 ms per loop
100 duplicates
terhost_early_exit
10000 loops, best of 3: 111 µs per loop
peterbe_early_exit
10000 loops, best of 3: 99 µs per loop
set length
100 loops, best of 3: 5.16 ms per loop
numpy unique length
1000 loops, best of 3: 1.19 ms per loop

因此，如果您期望很少有重复项，numpy.unique功能才是出路。随着预期重复次数的增加，早期退出方法占主导地位。