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

Question

如何在保留顺序的同时从列表中删除重复项？使用集合删除重复项会破坏原始顺序。有内置的或 Pythonic 的成语吗？

相关问题： 在 Python 中，从列表中删除重复项以使所有元素都是唯一的 同时保持顺序 的最快算法是什么？

原文由 Josh Glover 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

在这里你有一些选择： 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 ？ Python 是一种动态语言，解析 seen.add 每次迭代都比解析局部变量的成本更高。 seen.add 可能在迭代之间发生了变化，并且运行时不够聪明，无法排除这种情况。为了安全起见，它必须每次都检查对象。

如果您计划在同一个数据集上大量使用此函数，那么使用有序集可能会更好：http: //code.activestate.com/recipes/528878/

O (1) 每个操作的插入、删除和成员检查。

（小的附加说明： seen.add() 总是返回 None ，所以 or 以上只是作为尝试集合更新的一种方式，而不是作为一个组成部分的逻辑测试。）

原文由 Markus Jarderot 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 2

最佳解决方案因 Python 版本和环境限制而异：

Python 3.7+（以及大多数支持 3.6 的解释器，作为实现细节）：

在 PyPy 2.5.0 中首次引入，并在 CPython 3.6 中作为实现细节采用，在 Python 3.7 中成为语言保证之前，plain dict 是插入顺序的，甚至比（也是 C从 CPython 3.5 开始实施) collections.OrderedDict 。所以到目前为止，最快的解决方案也是最简单的：

 >>> items = [1, 2, 0, 1, 3, 2]
>>> list(dict.fromkeys(items))  # Or [*dict.fromkeys(items)] if you prefer
[1, 2, 0, 3]

就像 list(set(items)) 这会将所有工作推送到 C 层（在 CPython 上），但是由于 dict s 是插入顺序的， dict.fromkeys 不会丢失顺序。它比 list(set(items)) 慢（通常需要 50-100% 的时间），但 比 任何其他保持顺序的解决方案快得多（大约一半的时间 涉及使用 set s列表组件）。

重要说明： unique_everseen 来自 more_itertools 的解决方案（见下文）在懒惰性和对不可散列输入项的支持方面具有一些独特的优势；如果您需要这些功能，它是 唯一 可行的解决方案。

Python 3.5（以及所有旧版本，如果性能 不重要的 话）

正如 Raymond 指出的那样，在 CPython 3.5 中 OrderedDict 是在 C 中实现的，丑陋的列表理解黑客比 OrderedDict.fromkeys 慢（除非你真的需要最后的列表 - 即使那样，仅当输入非常短时）。因此，在性能和可读性方面，CPython 3.5 的最佳解决方案是 OrderedDict 相当于 3.6+ 使用普通 dict ：

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

在 CPython 3.4 及更早版本上，这将比其他一些解决方案慢，因此如果分析显示您需要更好的解决方案，请继续阅读。

Python 3.4 及更早版本，如果性能很关键并且第三方模块是可以接受的

As @abarnert notes, the more_itertools library ( pip install more_itertools ) contains a unique_everseen function that is built to solve this problem without any unreadable ( 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

但与 itertools 配方不同，它支持不可散列的项目（以性能成本为代价；如果 iterable 中的所有元素都是不可散列的，则算法变为 O(n²) -abce , vs. O(n) 如果它们都是可哈希的）。

重要说明：与此处的所有其他解决方案不同， unique_everseen 可以懒惰地使用；峰值内存使用量将是相同的（最终，底层 set 增长到相同的大小），但如果你不 list 验证结果，你只是迭代它，你将能够在找到唯一项时对其进行处理，而不是等到整个输入都被删除后再处理第一个唯一项。

Python 3.4 及更早版本，如果性能至关重要 且 第三方模块不可用

你有两个选择：

1. 将 unique_everseen 配方 复制并粘贴到您的代码中，并按照上面的 more_itertools 示例使用它

2. 使用丑陋的 hacks 允许单个 listcomp 检查和更新 set 以跟踪所看到的内容：

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

以依赖 丑陋的黑客 为代价：

     not seen.add(x)

which relies on the fact that `set.add` is an in-place method that always returns `None` so `not None` evaluates to `True` .

请注意，上面的 所有 解决方案都是 O(n) （保存调用 unique_everseen 不可散列项目的可迭代，这是 O(n²) -f40a，而其他人会立即失败带有 TypeError )，因此所有解决方案在不是最热门的代码路径时都具有足够的性能。使用哪一个取决于您可以依赖的语言规范/解释器/第三方模块的版本，性能是否至关重要（不要假设它是；通常不是），最重要的是可读性（因为如果维护此代码的人后来以杀气腾腾的心情结束，那么您聪明的微优化可能不值得）。

原文由 jamylak 发布，翻译遵循 CC BY-SA 4.0 许可协议