如何检查平面列表中是否有重复项？

Question

举个例子，如果给定的列表是 ['one', 'two', 'one']，那么这个算法应该返回 True，而如果是 ['one', 'two', 'three']，它就应该返回 False。

Answer 1

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

所以在这个情况下，Denis Otkidach 提出的解决方案是最快的。

有些方法的性能曲线非常陡峭，这些方法的运行时间随着元素数量的增加而呈二次增长（比如 Alex Martelli 的第一个解决方案、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()

Answer 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 平方)，这就没办法了 :-(。

Answer 3

如果所有的值都是可以被“哈希”的，也就是说它们可以被唯一标识，那么可以使用 set() 来去掉重复的值：

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

如何检查平面列表中是否有重复项？

15 个回答

撰写回答