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.addseen_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_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

但请注意,虽然具有相同的运行时复杂度O(N),但黑客解决方案的原始速度更快。

添加评论

友情链接:蝴蝶教程