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

Question

如何在保留订单的同时从列表中删除重复项？是否有内置功能可以从Python中的列表中删除重复项，同时保留顺序？我知道我可以使用一个集来删除重复项，但这会破坏原始顺序。我也知道我可以像这样滚动自己：def uniq(input):   output = []   for x in input:     if x not in output:       output.append(x)   return output（感谢您放松该代码示例。）但是如果可能的话，我想利用内置或更多的Pythonic习语。

Answer 1

正如Raymond所指出的那样，在OrderedDict用C语言实现的python 3.5+中，列表理解方法会慢于OrderedDict（除非你实际上需要最后的列表 - 即便如此，只有当输入非常短时）。所以3.5+的最佳解决方案是OrderedDict。

more_itertoolslibrary（pip install more_itertools）包含一个unique_everseen用于解决此问题的函数，而列表推导中没有任何不可读（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)]

并没有利用丑陋的黑客：

not seen.add(x)

它依赖于set.add一个就地方法的事实，它始终返回None所以not None求值True。

但请注意，虽然hack解决方案具有相同的运行时复杂度O（N），但它的原始速度更快。

Answer 2

在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中，保证常规字典在所有实现中都有序。 因此，最短和最快的解决方案是：

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

---

对@max的响应：一旦你移动到3.6或3.7并使用常规字典而不是OrderedDict，你就无法以任何其他方式击败性能。字典很密集，很容易转换成几乎没有开销的列表。目标列表预先调整为len（d），其保存列表推导中出现的所有调整大小。此外，由于内部密钥列表是密集的，因此复制指针几乎快速作为列表副本。