我如何检查一个列表是否有任何重复,并返回一个没有重复的新列表?


当前回答

今天,一位同事将接受的答案作为他的代码的一部分发给了我进行代码审阅。 虽然我很欣赏这个问题答案的优雅,但我对他的表现并不满意。 我尝试过这个解决方案(我使用set来减少查找时间)

def ordered_set(in_list):
    out_list = []
    added = set()
    for val in in_list:
        if not val in added:
            out_list.append(val)
            added.add(val)
    return out_list

为了比较效率,我使用了100个整数的随机样本,其中62个是唯一的

from random import randint
x = [randint(0,100) for _ in xrange(100)]

In [131]: len(set(x))
Out[131]: 62

这是测量结果

In [129]: %timeit list(OrderedDict.fromkeys(x))
10000 loops, best of 3: 86.4 us per loop

In [130]: %timeit ordered_set(x)
100000 loops, best of 3: 15.1 us per loop

如果把set从解中移除会发生什么?

def ordered_set(inlist):
    out_list = []
    for val in inlist:
        if not val in out_list:
            out_list.append(val)
    return out_list

结果并不像OrderedDict那样糟糕,但仍然是原始解决方案的3倍多

In [136]: %timeit ordered_set(x)
10000 loops, best of 3: 52.6 us per loop

其他回答

与回复中列出的其他解决方案相比,下面是最快的python解决方案。

使用短路计算的实现细节允许使用列表理解,这足够快。visit .add(item)总是返回None作为结果,它被赋值为False,所以or的右边总是这样的表达式的结果。

自己计时

def deduplicate(sequence):
    visited = set()
    adder = visited.add  # get rid of qualification overhead
    out = [adder(item) or item for item in sequence if item not in visited]
    return out

为了完整起见,由于这是一个非常流行的问题,toolz库提供了一个独特的函数:

>>> tuple(unique((1, 2, 3)))
(1, 2, 3)
>>> tuple(unique((1, 2, 1, 3)))
(1, 2, 3)

到目前为止,我看到的所有保持顺序的方法要么使用朴素比较(时间复杂度最多为O(n^2)),要么使用限制于可哈希输入的重载OrderedDicts/set+list组合。下面是一个与哈希无关的O(nlogn)解决方案:

更新增加了关键参数、文档和Python 3兼容性。

# from functools import reduce <-- add this import on Python 3

def uniq(iterable, key=lambda x: x):
    """
    Remove duplicates from an iterable. Preserves order. 
    :type iterable: Iterable[Ord => A]
    :param iterable: an iterable of objects of any orderable type
    :type key: Callable[A] -> (Ord => B)
    :param key: optional argument; by default an item (A) is discarded 
    if another item (B), such that A == B, has already been encountered and taken. 
    If you provide a key, this condition changes to key(A) == key(B); the callable 
    must return orderable objects.
    """
    # Enumerate the list to restore order lately; reduce the sorted list; restore order
    def append_unique(acc, item):
        return acc if key(acc[-1][1]) == key(item[1]) else acc.append(item) or acc 
    srt_enum = sorted(enumerate(iterable), key=lambda item: key(item[1]))
    return [item[1] for item in sorted(reduce(append_unique, srt_enum, [srt_enum[0]]))] 
>>> t = [1, 2, 3, 1, 2, 5, 6, 7, 8]
>>> t
[1, 2, 3, 1, 2, 5, 6, 7, 8]
>>> s = []
>>> for i in t:
       if i not in s:
          s.append(i)
>>> s
[1, 2, 3, 5, 6, 7, 8]

这里有很多答案使用set(..)(考虑到元素是可哈希的,这是快速的)或list(它的缺点是它会导致O(n2)算法。

我建议的函数是一个混合的函数:我们使用set(..)来表示可哈希的项,使用list(..)来表示不可哈希的项。此外,它被实现为一个生成器,例如,我们可以限制项目的数量,或做一些额外的过滤。

最后,我们还可以使用一个key参数来指定元素应以何种方式惟一。例如,如果我们想过滤一个字符串列表,这样输出中的每个字符串都有不同的长度,我们可以使用这个。

def uniq(iterable, key=lambda x: x):
    seens = set()
    seenl = []
    for item in iterable:
        k = key(item)
        try:
            seen = k in seens
        except TypeError:
            seen = k in seenl
        if not seen:
            yield item
            try:
                seens.add(k)
            except TypeError:
                seenl.append(k)

我们现在可以这样使用:

>>> list(uniq(["apple", "pear", "banana", "lemon"], len))
['apple', 'pear', 'banana']
>>> list(uniq(["apple", "pear", "lemon", "banana"], len))
['apple', 'pear', 'banana']
>>> list(uniq(["apple", "pear", {}, "lemon", [], "banana"], len))
['apple', 'pear', {}, 'banana']
>>> list(uniq(["apple", "pear", {}, "lemon", [], "banana"]))
['apple', 'pear', {}, 'lemon', [], 'banana']
>>> list(uniq(["apple", "pear", {}, "lemon", {}, "banana"]))
['apple', 'pear', {}, 'lemon', 'banana']

因此,它是一个唯一性过滤器,可以在任何可迭代对象上工作并过滤出唯一性对象,而不管这些唯一性对象是否可哈希。

它做了一个假设:如果一个对象是可哈希的,而另一个对象不是,这两个对象永远不相等。严格地说,这是可能发生的,尽管它是非常罕见的。