如何检查平面列表中是否存在重复项？-IT科技

摘要：问题描述：例如，给定列表['one', 'two', 'one']，算法应该返回True，而给定['one', 'two', 'three']它应该返回False。解决方案 1：如果所有值都是可哈希的，则用于set()删除重复项：>>> your_list = ['one', 'two', ...

问题描述：

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

解决方案 1：

如果所有值都是可哈希的，则用于set()删除重复项：

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

解决方案 2：

仅推荐用于短名单：

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

不要在长列表上使用——它所花费的时间与列表中项目数量的平方成正比！

对于包含可散列项（字符串，数字等）的较长列表：

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 平方)，对此无能为力:-(。

解决方案 3：

我认为比较一下这里介绍的不同解决方案的时间会很有用。为此，我使用了我自己的库simple_benchmark：

在此处输入图片描述

因此，对于这种情况，Denis Otkidach的解决方案是最快的。

一些方法还表现出更陡峭的曲线，这些方法随元素数量呈二次方增长（Alex Martellis 的第一个解决方案、wjandrea 和 Xavier Decorets 的两个解决方案）。同样值得一提的是，Keiku 的 pandas 解决方案有一个非常大的常数因子。但对于较大的列表，它几乎赶上了其他解决方案。

假设重复项位于第一个位置。这对于查看哪些解决方案是短路很有用：

在此处输入图片描述

这里有几种方法不会短路：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()

解决方案 4：

这已经过时了，但这里的答案让我想到了一个略有不同的解决方案。如果您打算滥用理解，您可以通过这种方式获得短路。

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

解决方案 5：

如果您喜欢函数式编程风格，这里有一个有用的函数，使用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

解决方案 6：

我最近回答了一个相关问题，使用生成器确定列表中的所有重复项。它的优点是，如果仅用于确定“是否有重复项”，则只需获取第一个项目，其余项目可以忽略，这是终极捷径。

这是一个有趣的基于集合的方法，我直接从moooeeeep改编而来：

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

因此，完整的重复项列表将是list(getDupes(etc))。为了简单地测试“是否”存在重复项，应将其包装如下：

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

无论列表中的重复项在哪里，它都可以很好地扩展并提供一致的操作时间——我测试了最多 100 万个条目的列表。如果您对数据有所了解，特别是重复项很可能出现在前半部分，或者其他让您扭曲需求的事情，例如需要获取实际的重复项，那么有几个真正替代的重复项定位器可能会表现更好。我推荐的两个是...

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

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（本质上是 ifilter/izip/tee），如果获取所有重复项则非常有效，尽管获取第一个重复项的速度并不快：

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

解决方案 7：

另一种简洁的方法是使用Counter。

仅确定原始列表中是否有重复项：

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]

解决方案 8：

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

解决方案 9：

我发现这样做性能最好，因为它在发现第一个重复时短路操作，然后该算法的时间和空间复杂度为 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

解决方案 10：

如果列表包含不可散列的项目，您可以使用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

解决方案 11：

我使用了 pyrospade 的方法，因为它简单易懂，并在由不区分大小写的 Windows 注册表制作的简短列表上对其进行了稍微的修改。

如果将原始 PATH 值字符串拆分为单独的路径，则可以使用以下命令删除所有“空”路径（空或仅空白的字符串）：

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 同时具有“空”条目和重复项：

[list]  Root paths in HKLMSYSTEMCurrentControlSetControlSession ManagerEnvironment:PATH[list]  Root paths in HKLMSYSTEMCurrentControlSetControlSession ManagerEnvironment
  1  C:Python37\n  2
  3
  4  C:Python37Scripts\n  5  c:python37\n  6  C:Program FilesImageMagick-7.0.8-Q8
  7  C:Program Files (x86)popplerin
  8  D:DATASounds
  9  C:Program Files (x86)GnuWin32in
 10  C:Program Files (x86)InteliCLS Client\n 11  C:Program FilesInteliCLS Client\n 12  D:DATACCMDFF
 13  D:DATACCMD
 14  D:DATAUTIL
 15  C:\n 16  D:DATAUHELP
 17  %SystemRoot%system32
 18
 19
 20  D:DATACCMDFF%SystemRoot%
 21  D:DATASounds
 22  %SystemRoot%System32Wbem
 23  D:DATACCMDFF
 24
 25
 26  c:\n 27  %SYSTEMROOT%System32WindowsPowerShell1.0\n 28

空路径已被删除，但仍然有重复，例如（1，3）和（13，20）：

    [list]  Null paths removed from HKLMSYSTEMCurrentControlSetControlSession ManagerEnvironment:PATH
  1  C:Python37\n  2  C:Python37Scripts\n  3  c:python37\n  4  C:Program FilesImageMagick-7.0.8-Q8
  5  C:Program Files (x86)popplerin
  6  D:DATASounds
  7  C:Program Files (x86)GnuWin32in
  8  C:Program Files (x86)InteliCLS Client\n  9  C:Program FilesInteliCLS Client\n 10  D:DATACCMDFF
 11  D:DATACCMD
 12  D:DATAUTIL
 13  C:\n 14  D:DATAUHELP
 15  %SystemRoot%system32
 16  D:DATACCMDFF%SystemRoot%
 17  D:DATASounds
 18  %SystemRoot%System32Wbem
 19  D:DATACCMDFF
 20  c:\n 21  %SYSTEMROOT%System32WindowsPowerShell1.0\n

最后，重复项已被删除：

[list]  Massaged path list from in HKLMSYSTEMCurrentControlSetControlSession ManagerEnvironment:PATH
  1  C:Python37\n  2  C:Python37Scripts\n  3  C:Program FilesImageMagick-7.0.8-Q8
  4  C:Program Files (x86)popplerin
  5  D:DATASounds
  6  C:Program Files (x86)GnuWin32in
  7  C:Program Files (x86)InteliCLS Client\n  8  C:Program FilesInteliCLS Client\n  9  D:DATACCMDFF
 10  D:DATACCMD
 11  D:DATAUTIL
 12  C:\n 13  D:DATAUHELP
 14  %SystemRoot%system32
 15  D:DATACCMDFF%SystemRoot%
 16  %SystemRoot%System32Wbem
 17  %SYSTEMROOT%System32WindowsPowerShell1.0\n

解决方案 12：

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

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

解决方案 13：

更简单的解决方案如下。只需使用 pandas.duplicated()方法检查 True/False，然后求和。另请参阅 pandas.Series.duplicated — 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

解决方案 14：

def check_duplicates(my_list):
    seen = {}
    for item in my_list:
        if seen.get(item):
            return True
        seen[item] = True
    return False

解决方案 15：

还有一些更有创意的解决方案...

解决方案 1：批次

简单的len(set(xs)) < len(xs)解决方案非常适合没有重复项的大型列表，但如果早期出现重复项，其他解决方案就会提前停止，甚至不查看其余部分，这很糟糕。我们可以通过分批处理在这两种情况下获得快速时间，即在“一次性”和“逐个”之间找到中间立场：

def batches(xs):
    seen = set()
    n = 0
    for batch in batched(xs, 100):
        n += len(batch)
        seen.update(batch)
        if len(seen) < n:
            return True
    return False

用途itertools.batched。我选择批量大小为 100，因为它仍然比批量大小 50 快 10%，但超过 100 后就没有明显的加速了。

作为免费奖励，这不仅适用于支持的列表或其他集合len(xs)，也适用于其他可迭代对象。

解决方案 2：`set.isdisjoint`

def isdisjoint(xs):
    seen = set()
    ahead = iter(xs)
    next(ahead, None)
    return not seen.isdisjoint(compress(
        ahead,
        zip(map(seen.add, xs))
    ))

假设xs是[1, 2, 3, 4, ...]。我的ahead迭代器领先一项，因此它会产生2、3、4等。我zip(map(seen.add, xs))将1、2、3等添加到集合中，并始终产生(None,)。因此，在第一步中，1将其添加到集合中，然后isdisjoint检查它是否包含2。然后在第二步中，2将其添加到集合中，然后isdisjoint检查它是否包含3。依此类推。（由于移位，这不会检查第一个元素是否已在集合中，也不会将最后一个元素添加到集合中。这样就可以了。）

用途set.isdisjoint和itertools.compress。

解决方案 3：再次压缩

与解决方案 2 类似。但此处compress仅当发现重复时才会产生结果。

def compress_contains(xs):
    seen = set()
    ahead = iter(xs)
    next(ahead, None)
    return None in compress(
        map(seen.add, xs),
        map(seen.__contains__, ahead)
    )

解决方案 4：更短但更慢

结果不如其他的那么快，但是它有点短，我仍然觉得它很有趣。

def shorter_but_slower(xs):
    seen = set()
    return any(compress(
        map(seen.__contains__, xs),
        zip(map(seen.add, xs))
    ))

基准测试结果

无重复的情况：

xs = list(range(10**5))

   3.0 ± 0.0 ms  set_size
   3.9 ± 0.0 ms  batches
   7.1 ± 0.1 ms  isdisjoint
   7.4 ± 0.1 ms  loop_optimized
   7.5 ± 0.1 ms  loop
   7.7 ± 0.1 ms  compress_contains
   8.8 ± 0.1 ms  shorter_but_slower

立即复制：

xs = [0, *range(10**5)]

   0.3 ± 0.0 μs  loop
   0.4 ± 0.0 μs  loop_optimized
   0.8 ± 0.0 μs  isdisjoint
   0.8 ± 0.0 μs  compress_contains
   1.0 ± 0.0 μs  shorter_but_slower
   3.2 ± 0.0 μs  batches
2928.6 ± 70.3 μs  set_size

Python: 3.13.0 (main, Nov  9 2024, 10:04:25) [GCC 14.2.1 20240910]

基准代码

def batches(xs):
    seen = set()
    n = 0
    for batch in batched(xs, 100):
        n += len(batch)
        seen.update(batch)
        if len(seen) < n:
            return True
    return False


def isdisjoint(xs):
    seen = set()
    ahead = iter(xs)
    next(ahead, None)
    return not seen.isdisjoint(compress(
        ahead,
        zip(map(seen.add, xs))
    ))


def compress_contains(xs):
    seen = set()
    ahead = iter(xs)
    next(ahead, None)
    return None in compress(
        map(seen.add, xs),
        map(seen.__contains__, ahead)
    )


def shorter_but_slower(xs):
    seen = set()
    return any(compress(
        map(seen.__contains__, xs),
        zip(map(seen.add, xs))
    ))


def set_size(xs):
    return len(set(xs)) < len(xs)


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


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


funcs = [
    batches,
    isdisjoint,
    compress_contains,
    shorter_but_slower,
    set_size,
    loop,
    loop_optimized,
]

from itertools import *
from time import perf_counter as time
from statistics import mean, stdev
import sys
import random

# Correctness
for n in range(7):
    for xs in product(range(7), repeat=n):
        expect = set_size(xs)
        for f in funcs:
            if f(xs) is not expect:
                print('fail', f.__name__)

# Speed
def benchmark(xs_str, reps, unit, scale):
    print('xs =', xs_str)
    print()
    xs = eval(xs_str)
    times = {f: [] for f in funcs}
    def stats(f):
        ts = [t * scale for t in sorted(times[f])[:5]]
        return f'{mean(ts):6.1f} ± {stdev(ts):3.1f} {unit} '
    for _ in range(100):
        random.shuffle(funcs)
        for f in funcs:
            t = time()
            for _ in range(reps):
                f(xs)
            times[f].append((time() - t) / reps)
    for f in sorted(funcs, key=stats):
        print(stats(f), f.__name__)
    print()

benchmark('list(range(10**5))', 1, 'ms', 1e3)
benchmark('[0, *range(10**5)]', 10, 'μs', 1e6)

print('Python:', sys.version)

在线尝试！

解决方案 16：

我真的不知道 set 在幕后做了什么，所以我只是想让它保持简单。

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