Python：在容器中高效查找

Question

我有一个容器cont。如果我想查明它是否有重复，我只需检查len(cont) == len(set(cont))。

假设我想找到一个重复的元素，如果它存在（只是任意重复的元素）。有没有简洁而有效的方法来写这个？

[Python的3]

Answer 1

好吧，我的第一个答案已经得到了相当多的高射炮的，所以我想我会尝试这样做的几个不同的方法和报告的差异。这是我的代码。

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

基本上，我以6种不同的方式尝试这种方式，如源文件中所列。我使用过的Linux命令time并收集实时运行时，执行上面的命令，像这样

time python ./test.py 1 

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

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

总之，一个字典LUT似乎是要走的路，集合操作（​​可能在其实现中使用LUT）紧随其后。

---

更新：我试过razpeitia的建议，并且除了你需要准确地知道什么是重复键你要找的，实际算法做了最坏至今（66.366 S）的事实。

---

更新2：我敢肯定有人会说，这个测试是偏颇，因为重复的位置是靠近列表的一端。 尝试运行代码使用其他位置之前downvoting并报告您的结果！

Answer 2

您可以开始将它们添加到组，一旦你尝试添加已经在你发现重复一组元素。

Answer 3

您必须扫描重复项的所有元素，因为它们可能只是您检查的最后一个元素，所以与线性搜索一样，无法获得比最坏情况O（N）时间更高的效率。但是一个简单的线性搜索来找到重复将使用O（N）内存，因为你需要跟踪你到目前为止看到的内容。

如果数组已排序，则可以在O（N）时间内找到重复项，而无需使用任何附加内存，因为重复对将彼此相邻。

Answer 4

试试这个：

def getFirstDup(cont): 
    for i in xrange(0, len(cont)): 
     if cont[i] in cont[:i]: 
      return cont[i] 
    return None 

Answer 5

这不是明显有什么发现是重复或1或收集的多种其它元素任意一个元素的点...你想删除它？将它的属性与它的双胞胎/三胞胎/ .../N-tuplets的属性合并？在任何情况下，这是一个O（N）操作，如果重复，直到检测不到更多副本为O（N ** 2）操作。

但是，您可以在算法仓库获得批量处理：对集合进行排序 - O（N * log（N）） - 然后使用itertools.groupby将重复项串起并在束中巡视，忽略束的大小为1，并且对大小大于1的团簇做任何你想要的 - 所有这些都只是O（N）左右。

Answer 6

from collections import Counter 

cont = [1, 2, 3] 
c = Counter(cont) 
x = someItem 

if c[x] == 0: 
    print("Not in cont") 
elif c[x] == 1: 
    print("Unique") 
else: 
    print("Duplicate") 

Answer 7

如果你的容器是一个列表，你可以通过你正在寻找它的计数（）方法的价值和检查结果：

>>> l = [1,1,2,3] 
>>> l.count(1) 
2 
>>> 

字典不能有重复键，也不可以一套。除此之外，我需要知道它是什么类型的容器。我想真正的重点是在编写自定义解决方案之前，始终确保您没有错过任何明显的解决方案。我有时候会自己陷入这种困境:)

Answer 8

根据http://wiki.python.org/moin/TimeComplexity大多数列表操作是非常低效的（只是确认x in myList确实在python3中似乎是O(N)）。

由原始的海报给出的方法是有效，因为它是O（N）的时间和空间（这是“最好”就可以了，无需进行其他假设你的列表，因为列表操作，如x in myList是O(N) ）。

有一个主要的优化是可能的，它是迭代地建立集合。这将在某些种类的列表上快速返回，例如[0,1,1,2,3,4,5,...]。但是，您隐含地假设了一下您的列表分布（例如，您是针对这种情况优化还是针对最后的重复进行优化？）。这种优化的好处是它不会影响渐近速度。以下是我会优雅地编写它：

def hasDuplicate(iter): 
    visited = set() 
    for item in iter: 
     if item in visited: 
      return True 
     visited.add(item) 
    return False 

您也可以返回第一个重复的，但你不能返回None;由于迭代器可能包含None，因此您必须提出异常。

旁注：有很多方法可以提高空间效率，以提高时间效率（例如布隆过滤器）的效率。

Answer 9

另一个建议，类似jonesy的答案。至少在python3中（没有在python 2.7中测试过），当c [-5000] = 0时，这比原来的答案的解决方案3和4更快。否则它只比解决方案1和2稍快...

elif toTest == '7': 
    for i in c: 
     if c.count(i)>1: 
      return i