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

Question

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

Answer 1

使用set()删除重复,如果所有的值是可哈希:

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

Answer 2

建议仅用于短名单:

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平方),没有人能做到这一点:-(.

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

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

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

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

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

Answer 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)).要简单地测试"if"是否存在欺骗,它应该包装如下:

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

这可以很好地扩展,并且无论欺诈在列表中的哪个地方都提供一致的操作时间 - 我使用最多1米条目的列表进行了测试.如果你对这些数据有所了解,特别是那些欺骗可能会在上半年出现,或者其他让你扭曲需求的东西,比如需要获得实际的欺骗,那么有几个真正替代的欺骗定位器这可能会超越.我推荐的两个是......

简单的基于dict的方法,非常易读:

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