Python：高效查找容器中的重复项

Question

我有一个容器 cont。如果我想知道里面有没有重复的东西，我只需要检查 len(cont) == len(set(cont))。

假设我想找一个重复的元素，如果有的话（随便找一个重复的元素）。有没有什么简单又高效的方法来写这个呢？

[Python 3]

Answer 1

找出一个集合中重复的元素，听起来似乎没什么意义。你是想把它删掉吗？还是想把它和其他重复的元素的属性合并起来？不管怎样，这个过程的复杂度是O(N)，如果你要重复这个过程直到没有重复元素为止，那就变成O(N ** 2)了。

不过，你可以用一种更聪明的方法来处理这个问题：先对集合进行排序，这个过程的复杂度是O(N*log(N))。然后你可以使用itertools.groupby来把重复的元素分成一组一组的，接着只需要关注那些重复次数大于1的组，忽略掉那些只有一个元素的组。这样做的复杂度大约是O(N)，效率会高很多。

Answer 2

你可以开始把元素添加到集合里，一旦你尝试添加一个已经在集合中的元素，就说明你找到了一个重复的元素。

Answer 3

好吧，我的第一个回答受到了不少批评，所以我想尝试几种不同的方法来做这个，并报告它们之间的差异。以下是我的代码。

import sys
import itertools

def getFirstDup(c, toTest):

    # Original idea using list slicing => 5.014 s
    if toTest == '1':
        for i in xrange(0, len(c)):
            if c[i] in c[:i]:
                return c[i]

    # Using two sets => 4.305 s
    elif toTest == '2':
        s = set()
        for i in c:
            s2 = s.copy()
            s.add(i)
            if len(s) == len(s2):
                return i

    # Using dictionary LUT => 0.763 s
    elif toTest == '3':
        d = {}
        for i in c:
            if i in d:
                return i
            else:
                d[i] = 1

    # Using set operations => 0.772 s
    elif toTest == '4':
        s = set()
        for i in c:
            if i in s:
                return i
            else:
                s.add(i)

    # Sorting then walking => 5.130 s
    elif toTest == '5':
        c = sorted(c)
        for i in xrange(1, len(c)):
            if c[i] == c[i - 1]:
                return c[i]

    # Sorting then groupby-ing => 5.086 s
    else:
        c = sorted(c)
        for k, g in itertools.groupby(c):
            if len(list(g)) > 1:
                return k

    return None


c = list(xrange(0, 10000000))
c[5000] = 0

for i in xrange(0, 10):
    print getFirstDup(c, sys.argv[1])

基本上，我用六种不同的方法来尝试，具体方法在源文件中列出了。我使用了Linux的time命令，收集了实际运行时间，命令的运行方式如下：

time python ./test.py 1

其中1是我想尝试的算法编号。每种算法都会在10,000,000个整数中寻找第一个重复的数字，并运行十次。列表中有一个重复项，数据是“基本有序”的，虽然我也尝试了反向排序的列表，但没有发现算法之间有明显的差异。

我最初的建议表现不佳，耗时5.014秒。我对icyrock.com的解决方案的理解也不太好，耗时4.305秒。接下来，我尝试使用字典来创建查找表（LUT），这个方法的运行时间最好，仅为0.763秒。我还尝试在集合上使用in操作符，结果是0.772秒，几乎和字典查找表一样好。我尝试对列表进行排序并遍历，结果非常糟糕，耗时5.130秒。最后，我尝试了John Machin的itertools建议，结果也不理想，耗时5.086秒。

总结一下，使用字典查找表似乎是最好的选择，而集合操作（可能在实现中使用了查找表）是第二好的选择。

---

更新：我尝试了razpeitia的建议，除了需要准确知道你要找的重复键之外，实际算法的表现是迄今为止最差的（耗时66.366秒）。

---

更新2：我相信会有人说这个测试有偏见，因为重复项的位置靠近列表的一端。在给出差评之前，尝试在不同的位置运行代码并报告你的结果！