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

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），其保存列表推导中出现的所有调整大小。此外，由于内部密钥列表是密集的，因此复制指针几乎快速作为列表副本。