Python:有效地在容器中找到副本

Question

我有一个容器cont.如果我想知道它是否有重复,我会检查len(cont) == len(set(cont)).

假设我想找到一个重复的元素(如果它存在)(只是任意的重复元素).有没有任何整洁有效的方式来写这个？

[Python 3]

Answer 1

您可以开始将它们添加到集合中,并且一旦您尝试添加已在集合中的元素,您就会发现重复.

Answer 2

好吧，我的第一个答案受到了相当多的批评，所以我想我应该尝试几种不同的方法来做到这一点并报告差异。这是我的代码。

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])

基本上，我以六种不同的方式进行尝试，如源文件中所列。我使用 Linuxtime命令并收集实时运行时，运行命令如下

time python ./test.py 1

是1我想尝试的算法。每个算法在 10,000,000 个整数中查找第一个重复项，并运行十次。列表中有一个重复项，它“大部分已排序”，尽管我确实尝试了反向排序列表，但没有注意到算法之间的比例差异。

我最初的建议在 5.014 秒时表现不佳。我对icyrock.com解决方案的理解也很差，为4.305秒。接下来我尝试使用字典创建 LUT，其最佳运行时间为 0.763 秒。我尝试in在集合上使用运算符，得到了 0.772 秒，几乎与字典 LUT 一样好。我尝试对列表进行排序和遍历，这花费了 5.130 秒的可怜时间。最后，我尝试了 John Machin 对 itertools 的建议，它给出了 5.086 秒的糟糕时间。

总之，字典 LUT似乎是可行的方法，而集合操作（​​可能在其实现中使用 LUT）紧随其后。

更新：我尝试了 razpeitia 的建议，除了您需要准确地知道您正在寻找的重复密钥这一事实之外，实际算法到目前为止表现最差（66.366 s）。

更新 2：我确信有人会说这个测试有偏见，因为重复的位置靠近列表的一端。在否决之前尝试使用不同的位置运行代码并报告您的结果！