python – 如何在保留订单的同时从列表中删除重复项?
是否有内置功能可以从Python中的列表中删除重复项,同时保留顺序?我知道我可以使用一个集来删除重复项,但这会破坏原始顺序。我也知道我可以像这样滚动自己:
def uniq(input):
output = []
for x in input:
if x not in output:
output.append(x)
return output
但是如果可能的话,我想利用内置或更多的Pythonic成语。
相关问题:在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
?Python是一种动态语言,解析seen.add
每次迭代比解析局部变量更昂贵。seen.add
可能在迭代之间发生了变化,并且运行时不够聪明,无法排除这种情况。为了安全起见,每次都必须检查对象。
如果你计划在同一个数据集上大量使用这个函数,也许你最好使用一个有序集:http://code.activestate.com/recipes/528878/
O(1)每次操作的插入,删除和成员检查。
编辑2016
正如Raymond所指出的那样,在OrderedDict
用C语言实现的python 3.5+中,列表理解方法会慢于OrderedDict
(除非你实际上需要最后的列表 – 即便如此,只有输入非常短)。所以3.5+的最佳解决方案是OrderedDict
。
重要编辑2015
正如@abarnert指出的那样,more_itertools
library(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
。
但请注意,虽然具有相同的运行时复杂度O(N),但黑客解决方案的原始速度更快。