我如何检查是否有重复在一个平面列表?

例如，给定列表['one', 'two', 'one']，算法应该返回True，而给定列表['one', 'two', 'three']，算法应该返回False。

337025 次浏览
小开

仅推荐用于短列表:

any(thelist.count(x) > 1 for x in thelist)

在一个很长的列表上使用不——它需要的时间与列表中项目数量的广场成正比!

对于具有可哈希项(字符串，数字，&c)的较长列表:

def anydup(thelist):
seen = set()
for x in thelist:
if x in seen: return True
seen.add(x)
return False

如果你的项目是不可哈希的(子列表，字典等)，它会变得更加复杂，尽管它仍然有可能得到O(N logN)，如果它们至少具有可比性。但你需要知道或测试项目的特征(可哈希与否，可比性与否)，以获得最佳性能——可哈希对象为O(N)，不可哈希对象为O(N log N)，否则就会变成O(N平方)，没有人能做什么:-(。

小开
最佳答案

如果所有值都是hashable，则使用set()删除重复项:

>>> your_list = ['one', 'two', 'one']
>>> len(your_list) != len(set(your_list))
True
小开

如果你喜欢函数式编程风格，这里有一个有用的函数，自文档和测试代码使用doctest。

def decompose(a_list):
"""Turns a list into a set of all elements and a set of duplicated elements.


Returns a pair of sets. The first one contains elements
that are found at least once in the list. The second one
contains elements that appear more than once.


>>> decompose([1,2,3,5,3,2,6])
(set([1, 2, 3, 5, 6]), set([2, 3]))
"""
return reduce(
lambda (u, d), o : (u.union([o]), d.union(u.intersection([o]))),
a_list,
(set(), set()))


if __name__ == "__main__":
import doctest
doctest.testmod()

从这里你可以通过检查返回对的第二个元素是否为空来测试唯一性:

def is_set(l):
"""Test if there is no duplicate element in l.


>>> is_set([1,2,3])
True
>>> is_set([1,2,1])
False
>>> is_set([])
True
"""
return not decompose(l)[1]

注意，这并不有效，因为您是显式地构造分解。但是在使用reduce的过程中，你可以得到一些等价的(但效率稍低)答案5:

def is_set(l):
try:
def func(s, o):
if o in s:
raise Exception
return s.union([o])
reduce(func, l, set())
return True
except:
return False
小开

这是老问题了，但这里的答案让我找到了一个略有不同的解决方案。如果您准备滥用推导式，您可能会以这种方式短路。

xs = [1, 2, 1]
s = set()
any(x in s or s.add(x) for x in xs)
# You can use a similar approach to actually retrieve the duplicates.
s = set()
duplicates = set(x for x in xs if x in s or s.add(x))
小开

我最近用生成器在列表中回答了一个与建立所有副本相关的问题。它的优点是，如果只是用来确定“是否有重复”，那么你只需要获取第一项，其余的可以忽略，这是终极捷径。

这是一个有趣的基于集合的方法，我直接改编自moooeeeep:

def getDupes(l):
seen = set()
seen_add = seen.add
for x in l:
if x in seen or seen_add(x):
yield x

因此，一个完整的dupes列表将是list(getDupes(etc))。为了简单地测试“是否”存在欺骗，它应该被包装如下:

def hasDupes(l):
try:
if getDupes(l).next(): return True    # Found a dupe
except StopIteration:
pass
return False

这可以很好地扩展，并且在列表中提供一致的操作时间——我测试了多达1m个条目的列表。如果您对数据有所了解，特别是，被欺骗者可能会在前半段出现，或者其他让您偏离需求的事情，比如需要获得实际的被欺骗者，那么有几个真正的替代dupe定位器可能会表现更好。我推荐的两个是……

简单的基于字典的方法，非常易读:

def getDupes(c):
d = {}
for i in c:
if i in d:
if d[i]:
yield i
d[i] = False
else:
d[i] = True

利用itertools(本质上是一个过滤器/izip/tee)在排序列表上，如果你得到所有的dupes，非常有效，但没有那么快得到第一个:

def getDupes(c):
a, b = itertools.tee(sorted(c))
next(b, None)
r = None
for k, g in itertools.ifilter(lambda x: x[0]==x[1], itertools.izip(a, b)):
if k != r:
yield k
r = k

这些是我为完整的被骗名单尝试的方法中表现最好的，第一次欺骗发生在1m元素列表中从开始到中间的任何地方。令人惊讶的是，排序步骤增加的开销很少。你的里程可能会有所不同，但以下是我的具体计时结果:

Finding FIRST duplicate, single dupe places "n" elements in to 1m element array


Test set len change :        50 -  . . . . .  -- 0.002
Test in dict        :        50 -  . . . . .  -- 0.002
Test in set         :        50 -  . . . . .  -- 0.002
Test sort/adjacent  :        50 -  . . . . .  -- 0.023
Test sort/groupby   :        50 -  . . . . .  -- 0.026
Test sort/zip       :        50 -  . . . . .  -- 1.102
Test sort/izip      :        50 -  . . . . .  -- 0.035
Test sort/tee/izip  :        50 -  . . . . .  -- 0.024
Test moooeeeep      :        50 -  . . . . .  -- 0.001 *
Test iter*/sorted   :        50 -  . . . . .  -- 0.027


Test set len change :      5000 -  . . . . .  -- 0.017
Test in dict        :      5000 -  . . . . .  -- 0.003 *
Test in set         :      5000 -  . . . . .  -- 0.004
Test sort/adjacent  :      5000 -  . . . . .  -- 0.031
Test sort/groupby   :      5000 -  . . . . .  -- 0.035
Test sort/zip       :      5000 -  . . . . .  -- 1.080
Test sort/izip      :      5000 -  . . . . .  -- 0.043
Test sort/tee/izip  :      5000 -  . . . . .  -- 0.031
Test moooeeeep      :      5000 -  . . . . .  -- 0.003 *
Test iter*/sorted   :      5000 -  . . . . .  -- 0.031


Test set len change :     50000 -  . . . . .  -- 0.035
Test in dict        :     50000 -  . . . . .  -- 0.023
Test in set         :     50000 -  . . . . .  -- 0.023
Test sort/adjacent  :     50000 -  . . . . .  -- 0.036
Test sort/groupby   :     50000 -  . . . . .  -- 0.134
Test sort/zip       :     50000 -  . . . . .  -- 1.121
Test sort/izip      :     50000 -  . . . . .  -- 0.054
Test sort/tee/izip  :     50000 -  . . . . .  -- 0.045
Test moooeeeep      :     50000 -  . . . . .  -- 0.019 *
Test iter*/sorted   :     50000 -  . . . . .  -- 0.055


Test set len change :    500000 -  . . . . .  -- 0.249
Test in dict        :    500000 -  . . . . .  -- 0.145
Test in set         :    500000 -  . . . . .  -- 0.165
Test sort/adjacent  :    500000 -  . . . . .  -- 0.139
Test sort/groupby   :    500000 -  . . . . .  -- 1.138
Test sort/zip       :    500000 -  . . . . .  -- 1.159
Test sort/izip      :    500000 -  . . . . .  -- 0.126
Test sort/tee/izip  :    500000 -  . . . . .  -- 0.120 *
Test moooeeeep      :    500000 -  . . . . .  -- 0.131
Test iter*/sorted   :    500000 -  . . . . .  -- 0.157
小开

另一种简洁的方法是使用计数器。

要确定原始列表中是否有重复项:

from collections import Counter


def has_dupes(l):
# second element of the tuple has number of repetitions
return Counter(l).most_common()[0][1] > 1

或者获取重复项的列表:

def get_dupes(l):
return [k for k, v in Counter(l).items() if v > 1]
小开

我发现这是最好的性能，因为当它发现第一个复制时，它会短路操作，那么这个算法的时间和空间复杂度为O(n)，其中n是列表的长度:

def has_duplicated_elements(iterable):
""" Given an `iterable`, return True if there are duplicated entries. """
clean_elements_set = set()
clean_elements_set_add = clean_elements_set.add


for possible_duplicate_element in iterable:


if possible_duplicate_element in clean_elements_set:
return True


else:
clean_elements_set_add( possible_duplicate_element )


return False
小开

我真的不知道布景的幕后是做什么的，所以我只想让它简单。

def dupes(num_list):
unique = []
dupes = []
for i in num_list:
if i not in unique:
unique.append(i)
else:
dupes.append(i)
if len(dupes) != 0:
return False
else:
return True
小开

一个更简单的解决方案如下。只需用pandas .duplicated()方法检查True/False，然后取sum。请参见pandas. series . replicated - pandas 0.24.1文档

import pandas as pd


def has_duplicated(l):
return pd.Series(l).duplicated().sum() > 0


print(has_duplicated(['one', 'two', 'one']))
# True
print(has_duplicated(['one', 'two', 'three']))
# False
小开

如果列表包含不可哈希项，则可以使用Alex Martelli的解决方案，但使用列表而不是集合，尽管对于较大的输入，它会较慢:O(N^2)。

def has_duplicates(iterable):
seen = []
for x in iterable:
if x in seen:
return True
seen.append(x)
return False
小开

我认为比较这里提出的不同解决方案的时间是有用的。为此，我使用了自己的库simple_benchmark:

enter image description here

因此在这种情况下，来自丹尼斯Otkidach的解决方案确实是最快的。

一些方法还显示出更陡峭的曲线，这些方法是用元素数量缩放二次的方法(Alex Martellis的第一个解，wjandrea和Xavier Decorets的两个解)。同样重要的是，来自Keiku的熊猫解决方案有一个非常大的常数因子。但对于更大的列表，它几乎赶上了其他的解。

如果副本在第一个位置。这对于查看哪些解决方案短路很有用:

enter image description here

这里有几种方法不会短路:Kaiku、Frank、Xavier_Decoret(第一个解决方案)、Turn、Alex Martelli(第一个解决方案)和Denis Otkidach提出的方法(在无重复情况下最快)。

我在这里包含了我自己库中的一个函数:iteration_utilities.all_distinct，它可以在无重复的情况下与最快的解决方案竞争，并在开始时重复的情况下以常数时间执行(尽管不是最快的)。

基准测试代码:

from collections import Counter
from functools import reduce


import pandas as pd
from simple_benchmark import BenchmarkBuilder
from iteration_utilities import all_distinct


b = BenchmarkBuilder()


@b.add_function()
def Keiku(l):
return pd.Series(l).duplicated().sum() > 0


@b.add_function()
def Frank(num_list):
unique = []
dupes = []
for i in num_list:
if i not in unique:
unique.append(i)
else:
dupes.append(i)
if len(dupes) != 0:
return False
else:
return True


@b.add_function()
def wjandrea(iterable):
seen = []
for x in iterable:
if x in seen:
return True
seen.append(x)
return False


@b.add_function()
def user(iterable):
clean_elements_set = set()
clean_elements_set_add = clean_elements_set.add


for possible_duplicate_element in iterable:


if possible_duplicate_element in clean_elements_set:
return True


else:
clean_elements_set_add( possible_duplicate_element )


return False


@b.add_function()
def Turn(l):
return Counter(l).most_common()[0][1] > 1


def getDupes(l):
seen = set()
seen_add = seen.add
for x in l:
if x in seen or seen_add(x):
yield x


@b.add_function()
def F1Rumors(l):
try:
if next(getDupes(l)): return True    # Found a dupe
except StopIteration:
pass
return False


def decompose(a_list):
return reduce(
lambda u, o : (u[0].union([o]), u[1].union(u[0].intersection([o]))),
a_list,
(set(), set()))


@b.add_function()
def Xavier_Decoret_1(l):
return not decompose(l)[1]


@b.add_function()
def Xavier_Decoret_2(l):
try:
def func(s, o):
if o in s:
raise Exception
return s.union([o])
reduce(func, l, set())
return True
except:
return False


@b.add_function()
def pyrospade(xs):
s = set()
return any(x in s or s.add(x) for x in xs)


@b.add_function()
def Alex_Martelli_1(thelist):
return any(thelist.count(x) > 1 for x in thelist)


@b.add_function()
def Alex_Martelli_2(thelist):
seen = set()
for x in thelist:
if x in seen: return True
seen.add(x)
return False


@b.add_function()
def Denis_Otkidach(your_list):
return len(your_list) != len(set(your_list))


@b.add_function()
def MSeifert04(l):
return not all_distinct(l)

关于论点:


# No duplicate run
@b.add_arguments('list size')
def arguments():
for exp in range(2, 14):
size = 2**exp
yield size, list(range(size))


# Duplicate at beginning run
@b.add_arguments('list size')
def arguments():
for exp in range(2, 14):
size = 2**exp
yield size, [0, *list(range(size)]


# Running and plotting
r = b.run()
r.plot()
小开

我使用了pyrospade的方法，因为它很简单，并在一个由不区分大小写的Windows注册表组成的简短列表中对其进行了稍微修改。

如果原始PATH值字符串被分割成单独的路径，所有'null'路径(空的或只有空格的字符串)可以使用以下方法删除:

PATH_nonulls = [s for s in PATH if s.strip()]


def HasDupes(aseq) :
s = set()
return any(((x.lower() in s) or s.add(x.lower())) for x in aseq)


def GetDupes(aseq) :
s = set()
return set(x for x in aseq if ((x.lower() in s) or s.add(x.lower())))


def DelDupes(aseq) :
seen = set()
return [x for x in aseq if (x.lower() not in seen) and (not seen.add(x.lower()))]

原始的PATH有“null”条目和用于测试目的的副本:

[list]  Root paths in HKLM\SYSTEM\CurrentControlSet\Control\Session Manager\Environment:PATH[list]  Root paths in HKLM\SYSTEM\CurrentControlSet\Control\Session Manager\Environment
1  C:\Python37\
2
3
4  C:\Python37\Scripts\
5  c:\python37\
6  C:\Program Files\ImageMagick-7.0.8-Q8
7  C:\Program Files (x86)\poppler\bin
8  D:\DATA\Sounds
9  C:\Program Files (x86)\GnuWin32\bin
10  C:\Program Files (x86)\Intel\iCLS Client\
11  C:\Program Files\Intel\iCLS Client\
12  D:\DATA\CCMD\FF
13  D:\DATA\CCMD
14  D:\DATA\UTIL
15  C:\
16  D:\DATA\UHELP
17  %SystemRoot%\system32
18
19
20  D:\DATA\CCMD\FF%SystemRoot%
21  D:\DATA\Sounds
22  %SystemRoot%\System32\Wbem
23  D:\DATA\CCMD\FF
24
25
26  c:\
27  %SYSTEMROOT%\System32\WindowsPowerShell\v1.0\
28

空路径已经被删除，但仍然有重复的路径，例如(1,3)和(13,20):

    [list]  Null paths removed from HKLM\SYSTEM\CurrentControlSet\Control\Session Manager\Environment:PATH
1  C:\Python37\
2  C:\Python37\Scripts\
3  c:\python37\
4  C:\Program Files\ImageMagick-7.0.8-Q8
5  C:\Program Files (x86)\poppler\bin
6  D:\DATA\Sounds
7  C:\Program Files (x86)\GnuWin32\bin
8  C:\Program Files (x86)\Intel\iCLS Client\
9  C:\Program Files\Intel\iCLS Client\
10  D:\DATA\CCMD\FF
11  D:\DATA\CCMD
12  D:\DATA\UTIL
13  C:\
14  D:\DATA\UHELP
15  %SystemRoot%\system32
16  D:\DATA\CCMD\FF%SystemRoot%
17  D:\DATA\Sounds
18  %SystemRoot%\System32\Wbem
19  D:\DATA\CCMD\FF
20  c:\
21  %SYSTEMROOT%\System32\WindowsPowerShell\v1.0\

最后，被愚弄的人被删除了:

[list]  Massaged path list from in HKLM\SYSTEM\CurrentControlSet\Control\Session Manager\Environment:PATH
1  C:\Python37\
2  C:\Python37\Scripts\
3  C:\Program Files\ImageMagick-7.0.8-Q8
4  C:\Program Files (x86)\poppler\bin
5  D:\DATA\Sounds
6  C:\Program Files (x86)\GnuWin32\bin
7  C:\Program Files (x86)\Intel\iCLS Client\
8  C:\Program Files\Intel\iCLS Client\
9  D:\DATA\CCMD\FF
10  D:\DATA\CCMD
11  D:\DATA\UTIL
12  C:\
13  D:\DATA\UHELP
14  %SystemRoot%\system32
15  D:\DATA\CCMD\FF%SystemRoot%
16  %SystemRoot%\System32\Wbem
17  %SYSTEMROOT%\System32\WindowsPowerShell\v1.0\
小开 
my_list = ['one', 'two', 'one']


duplicates = []


for value in my_list:
if my_list.count(value) > 1:
if value not in duplicates:
duplicates.append(value)


print(duplicates) //["one"]
小开 
def check_duplicates(my_list):
seen = {}
for item in my_list:
if seen.get(item):
return True
seen[item] = True
return False
小开

另一个解决方案是使用切片，它也适用于字符串和其他可枚举的东西。

def has_duplicates(x):
for idx, item in enumerate(x):
if item in x[(idx + 1):]:
return True
return False




>>> has_duplicates(["a", "b", "c"])
False
>>> has_duplicates(["a", "b", "b", "c"])
True
>>> has_duplicates("abc")
False
>>> has_duplicates("abbc")
True

提交答案