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

Question

是否有内置功能可以从Python中的列表中删除重复项,同时保留顺序？我知道我可以使用一个集来删除重复项,但这会破坏原始顺序.我也知道我可以像这样滚动自己:

def uniq(input):
  output = []
  for x in input:
    if x not in output:
      output.append(x)
  return output

(感谢您放松该代码示例.)

但是如果可能的话,我想利用内置或更多的Pythonic习语.

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

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)每次操作的插入,删除和成员检查.

Answer 2

编辑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.

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

Answer 3

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

Answer 4

sequence = ['1', '2', '3', '3', '6', '4', '5', '6']
unique = []
[unique.append(item) for item in sequence if item not in unique]

独特→ ['1', '2', '3', '6', '4', '5']

Answer 5

不要踢死马(这个问题很老,而且已经有很多好的答案),但这里有一个使用熊猫的解决方案,在很多情况下都很快,并且使用起来很简单.

import pandas as pd

my_list = [0, 1, 2, 3, 4, 1, 2, 3, 5]

>>> pd.Series(my_list).drop_duplicates().tolist()
# Output:
# [0, 1, 2, 3, 4, 5]

Answer 6

from itertools import groupby
[ key for key,_ in groupby(sortedList)]

甚至不必对列表进行排序,充分条件是将相等的值组合在一起.

编辑:我认为"保留顺序"意味着列表实际上是有序的.如果不是这种情况,那么MizardX的解决方案是正确的.

社区编辑:然而,这是"将重复的连续元素压缩为单个元素"的最优雅方式.

Answer 7

我想如果你想保持秩序,

你可以试试这个:

list1 = ['b','c','d','b','c','a','a']    
list2 = list(set(list1))    
list2.sort(key=list1.index)    
print list2

或者类似地,你可以这样做:

list1 = ['b','c','d','b','c','a','a']  
list2 = sorted(set(list1),key=list1.index)  
print list2 

你也可以这样做:

list1 = ['b','c','d','b','c','a','a']    
list2 = []    
for i in list1:    
    if not i in list2:  
        list2.append(i)`    
print list2

它也可以写成:

list1 = ['b','c','d','b','c','a','a']    
list2 = []    
[list2.append(i) for i in list1 if not i in list2]    
print list2 

Answer 8

在Python 3.7及更高版本中,字典可以保证记住它们的密钥插入顺序.这个问题的答案总结了当前的事态.

因此,OrderedDict解决方案已经过时,如果没有任何导入语句,我们可以简单地发出:

>>> lst = [1, 2, 1, 3, 3, 2, 4]
>>> list(dict.fromkeys(lst))
[1, 2, 3, 4]

Answer 9

对另一个非常古老的问题的另一个非常晚的答案:

该itertools食谱有做到这一点,利用函数seen集技术,但是:

• 处理标准key功能.
• 使用没有不合时宜的黑客.
• 通过预绑定优化循环,seen.add而不是查找N次.(f7也是这样,但有些版本没有.)
• 通过使用优化循环ifilterfalse,因此您只需循环遍历Python中的唯一元素,而不是所有元素.(ifilterfalse当然,你仍然会在里面迭代所有这些,但那是在C中,并且要快得多.)

它真的比快f7吗？这取决于您的数据,因此您必须对其进行测试并查看.如果你想要一个列表,最后f7使用listcomp,这里没办法做到这一点.(您可以直接append代替yielding,或者您可以将生成器提供给list函数,但是任何一个都不能像listcomp中的LIST_APPEND一样快.)无论如何,通常,挤出几微秒不会像重要的是具有易于理解,可重复使用,已经编写的功能,当您想要装饰时不需要DSU.

与所有食谱一样,它也可用于more-iterools.

如果您只是想要无key案例,可以将其简化为:

def unique(iterable):
    seen = set()
    seen_add = seen.add
    for element in itertools.ifilterfalse(seen.__contains__, iterable):
        seen_add(element)
        yield element

Answer 10

刚添加另一个(非常高性能的)实现的这样的功能从外部模块¹:iteration_utilities.unique_everseen:

>>> from iteration_utilities import unique_everseen
>>> lst = [1,1,1,2,3,2,2,2,1,3,4]

>>> list(unique_everseen(lst))
[1, 2, 3, 4]

计时

我做了一些时间安排(Python 3.6),这些显示它比我测试的所有其他选项更快,包括OrderedDict.fromkeys,f7和more_itertools.unique_everseen:

%matplotlib notebook

from iteration_utilities import unique_everseen
from collections import OrderedDict
from more_itertools import unique_everseen as mi_unique_everseen

def f7(seq):
    seen = set()
    seen_add = seen.add
    return [x for x in seq if not (x in seen or seen_add(x))]

def iteration_utilities_unique_everseen(seq):
    return list(unique_everseen(seq))

def more_itertools_unique_everseen(seq):
    return list(mi_unique_everseen(seq))

def odict(seq):
    return list(OrderedDict.fromkeys(seq))

from simple_benchmark import benchmark

b = benchmark([f7, iteration_utilities_unique_everseen, more_itertools_unique_everseen, odict],
              {2**i: list(range(2**i)) for i in range(1, 20)},
              'list size (no duplicates)')
b.plot()

并且只是为了确保我还进行了更多重复的测试,以检查它是否有所作为:

import random

b = benchmark([f7, iteration_utilities_unique_everseen, more_itertools_unique_everseen, odict],
              {2**i: [random.randint(0, 2**(i-1)) for _ in range(2**i)] for i in range(1, 20)},
              'list size (lots of duplicates)')
b.plot()

一个只包含一个值:

b = benchmark([f7, iteration_utilities_unique_everseen, more_itertools_unique_everseen, odict],
              {2**i: [1]*(2**i) for i in range(1, 20)},
              'list size (only duplicates)')
b.plot()

在所有这些情况下,iteration_utilities.unique_everseen功能最快(在我的计算机上).

此iteration_utilities.unique_everseen函数还可以处理输入中的不可用值(但是当值可以清除时,O(n*n)性能而不是O(n)性能).

>>> lst = [{1}, {1}, {2}, {1}, {3}]

>>> list(unique_everseen(lst))
[{1}, {2}, {3}]

¹免责声明:我是该套餐的作者.

Answer 11

对于没有可清除类型(例如列表列表),基于MizardX:

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

Answer 12

pandas 用户应该查看pandas.unique.

>>> import pandas as pd
>>> lst = [1, 2, 1, 3, 3, 2, 4]
>>> pd.unique(lst)
array([1, 2, 3, 4])

该函数返回一个 NumPy 数组。如果需要，您可以使用该方法将其转换为列表tolist。