在Python列表或numpy数组中检查重复项的最快方法

在这里，我想到了四种方法。

如果你预期重复项很少（少于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

第一种方法是来自该答案的一个早期退出方法，该方法希望返回唯一值，第二种方法是将相同的想法应用于该答案。

如果使用普通的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函数是最好的选择。随着预期重复项的数量增加，早期退出方法占主导地位。

我不确定这个测试是否公平。在你的数据中，重复项几乎不可能发生，因此早期退出是无意义的。如果真实数据集通常会有，比如说10个重复项，早期退出将使其快大约10倍。

非常好的观点。我已经添加了关于预期重复项数量的讨论，事实上，随着重复项数量的增加，早期退出方法占主导地位。

另一个可能需要担心的问题是内存分配是否是个问题。对于大型输入，无论是构建一个包含大量浮点数的集合，还是让unique返回一个包含大量浮点数并使用任何临时存储所需的数组，这可能会产生巨大的差异。但我写了一个回答，解释了如何避免这个问题，因为在评论中写太多了。

根据上述内容，本文将讨论在Python列表/NumPy ndarray中检查重复项的最快方法。

根据数组的大小和重复项的可能性，答案会有所不同。如果你预计平均数组中会有大约3个重复项，提前退出会将平均情况下的时间（和空间）减少2/3；如果你预计只有1000个数组中的1个会有任何重复项，那么它只会增加一点复杂性而没有任何改进。

同时，如果数组足够大，构建一个与数组一样大的临时集合可能会很昂贵，在其前面加上一个类似于布隆过滤器的概率测试可能会大大加快速度，但如果不需要，那么这只是浪费的努力。

最后，如果可能的话，最好使用NumPy。循环遍历一个浮点数数组（或其他类型的数组）并将每个元素装箱到Python对象中所需的时间几乎与哈希和检查值的时间一样长，而且将事物存储在Python的set而不是经过优化的NumPy存储中也是浪费的。但是你必须权衡其他问题，不能使用NumPy进行提前退出，并且可能有一些很好的C优化的布隆过滤器实现可以通过pip install获得，但可能没有任何适用于NumPy的实现。

因此，对于所有可能的情况，没有一个最佳的解决方案。

接下来，为了提供一个编写布隆过滤器的简单示例，这是我在几分钟内拼凑出来的一个示例：

from bitarray import bitarray # pip3 install bitarray
def dupcheck(X):
    # Hardcoded values to give about 5% false positives for 10000 elements
    size = 62352
    hashcount = 4
    bits = bitarray(size)
    bits.setall(0)
    def check(x, hash=hash): # TODO: default-value bits, hashcount, size?
        for i in range(hashcount):
            if not bits[hash((x, i)) % size]: return False
        return True
    def add(x):
        for i in range(hashcount):
            bits[hash((x, i)) % size] = True
    seen = set()
    seen_add = seen.add
    for x in X:
        if check(x) or add(x):
            if x in seen or seen_add(x):
                return True
    return False

这个示例只使用了12KB（一个62352位的bitarray加上一个500个浮点数的set），而不是80KB（一个10000个浮点数的set或np.array）。这对于只处理10000个元素的情况下无关紧要，但对于使用超过一半物理内存的100亿个元素，情况就不同了。

当然，这几乎肯定会比使用np.unique或者set慢一个数量级，因为我们在Python中做了所有这些缓慢的循环。但如果发现值得这样做，重写为Cython应该很容易（并且可以直接访问NumPy数组而无需装箱和取消装箱）。

根据上述内容，我们可以得出结论：要检查Python列表/NumPy ndarray中是否存在重复项的最快方法取决于数组的大小和重复项的可能性。对于不同的情况，可能需要不同的解决方案。有时候，通过提前退出或使用布隆过滤器等概率测试可以加快速度，但在其他情况下可能只会增加复杂性而没有任何改进。同时，尽可能使用NumPy来进行操作，避免使用循环遍历和Python对象。然而，在权衡其他问题时，可能需要在NumPy和布隆过滤器之间进行选择。最后，布隆过滤器可以是一种检查重复项的选择，尽管它可能比使用np.unique或set慢一个数量级。但是，如果值得这样做，可以采用Cython重写以提高性能。

以上就是检查Python列表/NumPy ndarray中是否存在重复项的最快方法的原因和解决方法。

在这段内容中，作者进行了一系列的计时测试，目的是找到在Python中检查列表或numpy数组中是否存在重复项的最快方法。作者使用了Python 3.7.3版本，并分别测试了长度为8和长度为1000的数组。

作者首先比较了使用set()和np.unique()函数的性能。对于长度为8的数组，set()函数比np.unique()函数要快得多，但对于长度为1000的数组，set()函数比np.unique()函数要慢。作者提供了计时测试的结果，包括最小值和平均值。作者认为，np.unique()函数在处理较大的数组时更加高效。

然后，作者尝试了自己的实现方法，但认为要超越set()函数，可能需要使用优化的C代码。作者给出了自己的实现代码，该代码使用了两个嵌套的循环，逐个比较数组中的元素，如果找到相同的元素，则跳出循环。

作者再次进行了计时测试，对比了set()函数、np.unique()函数和自己的实现方法的性能。结果显示，对于长度为8的数组，set()函数是最快的，而np.unique()函数和作者的实现方法都要慢一些。作者的实现方法稍微慢一些。整个测试过程中，作者使用了自己编写的compare_time()函数进行计时。

作者在这段内容中提出了一个问题：在Python中，如何快速检查列表或numpy数组中是否存在重复项。作者进行了一系列的计时测试，并比较了set()函数、np.unique()函数和自己的实现方法的性能。根据测试结果，对于不同长度的数组，不同的方法具有不同的性能优势。