如何在保留订单的同时从列表中删除重复项？

是否有内置的程序在保留顺序的同时从 Python 列表中删除重复项？我知道我可以使用集合来删除重复项，但这会破坏原始顺序。我也知道我可以这样滚动自己：

def uniq(input):
  output = []
  for x in input:
    if x not in output:
      output.append(x)
  return output

（感谢您放松该代码示例。）

但是如果可能的话，我想利用内置的或更多的 Python 习语。

答案

在这里，您有一些选择： http : //www.peterbe.com/plog/uniqifiers-benchmark

最快的：

def f7(seq):
    seen = set()
    seen_add = seen.add
    return [x for x in seq if not (x in seen or seen_add(x))]

为什么seen.add seen_add分配给seen_add而不是仅仅调用seen.add呢？ Python 是一种动态语言，因此解析seen.add每个迭代比解析局部变量的开销更大。 seen.add可能在seen.add迭代之间发生了变化，并且运行时不够智能，无法排除这种情况。为了安全起见，它必须每次检查对象。

如果您打算在同一数据集上大量使用此功能，则最好使用有序集： http : //code.activestate.com/recipes/528878/

O （1）每个操作的插入，删除和成员检查。

（小小的附加说明： seen.add()始终返回None ，因此or以上仅是尝试进行集合更新的一种方法，而不是逻辑测试的组成部分。）

编辑 2016

正如 Raymond 所指出的那样，在 Python 3.5 + 中，其中OrderedDict是用 C 实现的，列表理解方法将比OrderedDict慢（除非您实际上需要列表的末尾，即使输入很短也是如此）。因此，3.5 + 的最佳解决方案是OrderedDict 。

重要编辑 2015

正如@abarnert指出的那样， more_itertools库（ pip install more_itertools ）包含一个unique_everseen函数，该函数旨在解决此问题而not seen.add在列表理解中造成任何不可读的 （ not seen.add ）突变。这也是最快的解决方案：

>>> from  more_itertools import unique_everseen
>>> items = [1, 2, 0, 1, 3, 2]
>>> list(unique_everseen(items))
[1, 2, 0, 3]

只需导入一个简单的库，就不会有黑客入侵。这来自 itertools 配方unique_everseen的实现，如下所示：

def unique_everseen(iterable, key=None):
    "List unique elements, preserving order. Remember all elements ever seen."
    # unique_everseen('AAAABBBCCDAABBB') --> A B C D
    # unique_everseen('ABBCcAD', str.lower) --> A B C D
    seen = set()
    seen_add = seen.add
    if key is None:
        for element in filterfalse(seen.__contains__, iterable):
            seen_add(element)
            yield element
    else:
        for element in iterable:
            k = key(element)
            if k not in seen:
                seen_add(k)
                yield element

在 Python 2.7+ ， ~~可接受的通用习惯用法~~ （可以使用，但并未针对速度进行优化，我现在将使用unique_everseen ），因为它使用collections.OrderedDict ：

运行时间： O（N）

>>> from collections import OrderedDict
>>> items = [1, 2, 0, 1, 3, 2]
>>> list(OrderedDict.fromkeys(items))
[1, 2, 0, 3]

看起来比：

seen = set()
[x for x in seq if x not in seen and not seen.add(x)]

并且不利用丑陋的 hack ：

not seen.add(x)

这依赖于set.add是始终就返回None的就地方法的事实，因此not None求值结果not None True 。

但是请注意，尽管破解解决方案具有相同的运行时复杂度 O（N），但其原始速度更快。

在 Python 2.7 中 ，从迭代器中删除重复项并同时保持其原始顺序的新方法是：

>>> from collections import OrderedDict
>>> list(OrderedDict.fromkeys('abracadabra'))
['a', 'b', 'r', 'c', 'd']

在 Python 3.5 中 ，OrderedDict 具有 C 实现。我的时间表明，这是 Python 3.5 各种方法中最快也是最短的方法。

在 Python 3.6 中 ，常规字典变得有序且紧凑。（此功能适用于 CPython 和 PyPy，但在其他实现中可能不存在）。这为我们提供了一种在保留订单的同时进行重复数据删除的最快方法：

>>> list(dict.fromkeys('abracadabra'))
['a', 'b', 'r', 'c', 'd']

在 Python 3.7 中 ，保证常规 dict 在所有实现中都排序。 因此，最短，最快的解决方案是：

>>> list(dict.fromkeys('abracadabra'))
['a', 'b', 'r', 'c', 'd']

对 @max 的响应：一旦移至 3.6 或 3.7 并使用常规 dict 而不是OrderedDict ，就无法以任何其他方式真正击败性能。该词典很密集，几乎可以无开销地转换为列表。目标列表的大小预先设置为 len（d），这样可以保存列表推导中发生的所有调整大小。另外，由于内部键列表很密集，因此指针的复制几乎快如列表副本。