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

https://stackoverflow.com/questions/480214

20-08-2019
|

题

是否有一个内置函数可以从Python列表中删除重复项，同时保留顺序？我知道我可以使用一组来删除重复项，但这会破坏原始顺序。我也知道我可以像这样推出自己的：

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

（谢谢放松为了那个原因代码示例.)

但如果可能的话，我想利用内置的或更Pythonic 的习惯用法。

解决方案

在这里，你有一些选择： http://www.peterbe.com/plog/uniqifiers-基准

最快之一：

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/

0 的（1）插入，删除和每个操作部件检查。

（小的额外注释：seen.add()总是返回None，因此 or 以上是有仅作为一种尝试集更新，而不是作为逻辑测试的一个组成部分）

其他提示

编辑2016

正如雷蒙德指出, ，在 python 3.5+ 中，其中 OrderedDict 是用 C 实现的，列表理解方法会比 OrderedDict （除非您实际上需要最后的列表 - 即使这样，仅当输入非常短时）。所以 3.5+ 的最佳解决方案是 OrderedDict.

2015年重要编辑

作为 @abarnert 笔记， more_itertools 图书馆（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:

运行：在）

>>> 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)，但原始速度更快。

<强>在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），其保存所有发生在一个列表中理解的调整大小。另外，由于内部键列表是致密的，复制指针为约几乎快列表副本。

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']

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

列表不甚至必须是排序，的充分条件是，相等的值组合在一起。

编辑：我认为“维持秩序”意味着该名单实际上是有序的。如果不是这种情况，那么从MizardX溶液是正确的。

社区编辑：这是然而为“压缩重复连续元素到一个单一的元素”
最优雅的方式。

不踢死马（这个问题已经很老了，已经有很多很好的答案），但这里是熊猫使用是相当快的在许多情况下，是死的简单易用的解决方案。

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]

我想，如果你想维持秩序，

你可以试试这个：

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

只是从外部模块添加此类功能的另一个（非常高性能的）实现¹: 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}]

¹ 免责声明：我是那个包的作者。

另一个非常迟的回答另一个非常古老的问题：

的 itertools 食谱有一个功能，这会使用的 seen 设置技术，但是：

处理标准 key 功能。

使用没有不合时宜的黑客。

优化的环预的结合 seen.add 而不是看它了N次。(f7 也不会这样，但一些版本没有。)

优化循环使用 ifilterfalse, 所以你只需要循环的唯一要素在蟒蛇，而不是所有的人。(你还迭代他们内部 ifilterfalse, 当然，但，C，并要快得多。)

它实际上的速度比 f7?这取决于你的数据，所以你必须测试看看。如果你想要一个列表的一端， f7 使用listcomp，而且也没有办法做到这一点。(你可以直接 append 而不是的 yield荷兰国际集团，或者你可以饲料发电机进入 list 功能，但没有一个可以尽快的LIST_APPEND内listcomp.) 在任何速度，通常情况下，挤出几个微秒的不是要作为重要，因为具有一种易于理解、可重复使用，已经编写的功能，不需要争端解决的谅解书》的时候你想来装饰。

如同所有的食谱，它也可以在 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

在 Python 3.7 及以上，字典是保证记住他们的钥匙插入顺序。答案是这问题总结了目前的情况。

这 OrderedDict 因此，解决方案变得过时，没有任何导入语句，我们可以简单地发出：

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

有关没有哈希的类型（例如列表的列表），基于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 ) )]

借用在definining Haskell的对列表nub函数使用的递归想法，这将是一个递归方法：

def unique(lst): return [] if lst==[] else [lst[0]] + unique(filter(lambda x: x!= lst[0], lst[1:]))

e.g：

In [118]: unique([1,5,1,1,4,3,4]) Out[118]: [1, 5, 4, 3]

我尝试了用于生长数据大小和看到的子线性时间复杂度（不是绝对的，但建议这应该是细用于正常的数据）。

In [122]: %timeit unique(np.random.randint(5, size=(1))) 10000 loops, best of 3: 25.3 us per loop In [123]: %timeit unique(np.random.randint(5, size=(10))) 10000 loops, best of 3: 42.9 us per loop In [124]: %timeit unique(np.random.randint(5, size=(100))) 10000 loops, best of 3: 132 us per loop In [125]: %timeit unique(np.random.randint(5, size=(1000))) 1000 loops, best of 3: 1.05 ms per loop In [126]: %timeit unique(np.random.randint(5, size=(10000))) 100 loops, best of 3: 11 ms per loop

我也认为这是有趣的是，这可以通过其他的操作很容易地推广到唯一性。像这样：

import operator def unique(lst, cmp_op=operator.ne): return [] if lst==[] else [lst[0]] + unique(filter(lambda x: cmp_op(x, lst[0]), lst[1:]), cmp_op)

例如，可以通过在使用舍入到相同的整数，如果它是用于唯一目的，“相等”，像这样的概念的函数：

def test_round(x,y): return round(x) != round(y)

然后独特（some_list，test_round）将提供列表，其中唯一不再意味着传统平等（它是通过使用任何种类的组或基于字典密钥为基础的方法解决这个问题的暗示）的独特的元素，而是意味着只需要舍入到K中的每个可能的整数K，这些元件可能轮第一元件，例如：

In [6]: unique([1.2, 5, 1.9, 1.1, 4.2, 3, 4.8], test_round) Out[6]: [1.2, 5, 1.9, 4.2, 3]

5×更快降低变体，但更复杂的

>>> l = [5, 6, 6, 1, 1, 2, 2, 3, 4] >>> reduce(lambda r, v: v in r[1] and r or (r[0].append(v) or r[1].add(v)) or r, l, ([], set()))[0] [5, 6, 1, 2, 3, 4]

说明：

default = (list(), set()) # use list to keep order # use set to make lookup faster def reducer(result, item): if item not in result[1]: result[0].append(item) result[1].add(item) return result >>> reduce(reducer, l, default)[0] [5, 6, 1, 2, 3, 4]

MizardX的回答给出了多种方法收集好。

这是我想出了同时自言自语：

mylist = [x for i,x in enumerate(mylist) if x not in mylist[i+1:]]

可以引用列表理解，因为它是由符号内置“_ [1]”。结果，例如，下面的函数独特-ifies元素的列表，而不通过引用其列表理解改变它们的顺序。

def unique(my_list): return [x for x in my_list if x not in locals()['_[1]']]

演示：

l1 = [1, 2, 3, 4, 1, 2, 3, 4, 5] l2 = [x for x in l1 if x not in locals()['_[1]']] print l2

输出：

[1, 2, 3, 4, 5]

您可以做一个排序列表丑理解黑客的。

[l[i] for i in range(len(l)) if l.index(l[i]) == i]

相对有效的方式与一个_sorted_阵列numpy：

b = np.array([1,3,3, 8, 12, 12,12]) numpy.hstack([b[0], [x[0] for x in zip(b[1:], b[:-1]) if x[0]!=x[1]]])

输出：

array([ 1, 3, 8, 12])

l = [1,2,2,3,3,...] n = [] n.extend(ele for ele in l if ele not in set(n))

使用将O生成表达式（1）查找一组，以确定是否要包括在新的清单的一个元素。

一个简单的递归溶液：

def uniquefy_list(a): return uniquefy_list(a[1:]) if a[0] in a[1:] else [a[0]]+uniquefy_list(a[1:]) if len(a)>1 else [a[0]]

如果你需要一个衬垫那么也许这将有助于：

reduce(lambda x, y: x + y if y[0] not in x else x, map(lambda x: [x],lst))

...应该工作，但纠正我，如果我错了

如果您经常使用 pandas 和美观优于性能，然后再考虑内置功能pandas.Series.drop_duplicates ：

import pandas as pd import numpy as np uniquifier = lambda alist: pd.Series(alist).drop_duplicates().tolist() # from the chosen answer def f7(seq): seen = set() seen_add = seen.add return [ x for x in seq if not (x in seen or seen_add(x))] alist = np.random.randint(low=0, high=1000, size=10000).tolist() print uniquifier(alist) == f7(alist) # True

定时：

In [104]: %timeit f7(alist) 1000 loops, best of 3: 1.3 ms per loop In [110]: %timeit uniquifier(alist) 100 loops, best of 3: 4.39 ms per loop

这将保留次序和在O（n）的时间运行。基本想法是创建一个洞，只要有一个重复的发现和击沉下到谷底。利用一个读写指针。每当重复被发现仅读出指针前进，写指针停留在重复条目将其覆盖。

def deduplicate(l): count = {} (read,write) = (0,0) while read < len(l): if l[read] in count: read += 1 continue count[l[read]] = True l[write] = l[read] read += 1 write += 1 return l[0:write]

，而无需使用导入的模块或组A液：

text = "ask not what your country can do for you ask what you can do for your country" sentence = text.split(" ") noduplicates = [(sentence[i]) for i in range (0,len(sentence)) if sentence[i] not in sentence[:i]] print(noduplicates)

给出的输出：

['ask', 'not', 'what', 'your', 'country', 'can', 'do', 'for', 'you']

在就地方法

此方法是二次的，因为我们有一个线性查找到的列表中列表的每个元素（到我们必须添加重排，因为del S的列表的费用）。

这就是说，有可能在的地方，如果我们从列表的末尾开始并朝向原点进行去除的每个术语，其存在于子列表在运行其左

这个想法在代码仅仅是

for i in range(len(l)-1,0,-1): if l[i] in l[:i]: del l[i]

执行的一个简单的测试

In [91]: from random import randint, seed In [92]: seed('20080808') ; l = [randint(1,6) for _ in range(12)] # Beijing Olympics In [93]: for i in range(len(l)-1,0,-1): ...: print(l) ...: print(i, l[i], l[:i], end='') ...: if l[i] in l[:i]: ...: print( ': remove', l[i]) ...: del l[i] ...: else: ...: print() ...: print(l) [6, 5, 1, 4, 6, 1, 6, 2, 2, 4, 5, 2] 11 2 [6, 5, 1, 4, 6, 1, 6, 2, 2, 4, 5]: remove 2 [6, 5, 1, 4, 6, 1, 6, 2, 2, 4, 5] 10 5 [6, 5, 1, 4, 6, 1, 6, 2, 2, 4]: remove 5 [6, 5, 1, 4, 6, 1, 6, 2, 2, 4] 9 4 [6, 5, 1, 4, 6, 1, 6, 2, 2]: remove 4 [6, 5, 1, 4, 6, 1, 6, 2, 2] 8 2 [6, 5, 1, 4, 6, 1, 6, 2]: remove 2 [6, 5, 1, 4, 6, 1, 6, 2] 7 2 [6, 5, 1, 4, 6, 1, 6] [6, 5, 1, 4, 6, 1, 6, 2] 6 6 [6, 5, 1, 4, 6, 1]: remove 6 [6, 5, 1, 4, 6, 1, 2] 5 1 [6, 5, 1, 4, 6]: remove 1 [6, 5, 1, 4, 6, 2] 4 6 [6, 5, 1, 4]: remove 6 [6, 5, 1, 4, 2] 3 4 [6, 5, 1] [6, 5, 1, 4, 2] 2 1 [6, 5] [6, 5, 1, 4, 2] 1 5 [6] [6, 5, 1, 4, 2] In [94]:

消除重复的值的序列，但保留剩余的项目的顺序。使用通用发生器的功能。

# for hashable sequence def remove_duplicates(items): seen = set() for item in items: if item not in seen: yield item seen.add(item) a = [1, 5, 2, 1, 9, 1, 5, 10] list(remove_duplicates(a)) # [1, 5, 2, 9, 10] # for unhashable sequence def remove_duplicates(items, key=None): seen = set() for item in items: val = item if key is None else key(item) if val not in seen: yield item seen.add(val) a = [ {'x': 1, 'y': 2}, {'x': 1, 'y': 3}, {'x': 1, 'y': 2}, {'x': 2, 'y': 4}] list(remove_duplicates(a, key=lambda d: (d['x'],d['y']))) # [{'x': 1, 'y': 2}, {'x': 1, 'y': 3}, {'x': 2, 'y': 4}]

赞比亚克瓦查的方法是使用列表理解，这是非常快的，但会保留订单自然。用于施加到外壳敏感字符串可被容易地修改。这也保留了原始的情况。

def DelDupes(aseq) : seen = set() return [x for x in aseq if (x.lower() not in seen) and (not seen.add(x.lower()))]

密切联系的功能是：

def HasDupes(aseq) : s = set() return any(((x.lower() in s) or s.add(x.lower())) for x in aseq) def GetDupes(aseq) : s = set() return set(x for x in aseq if ((x.lower() in s) or s.add(x.lower())))

许可以下： CC-BY-SA 和归因

不隶属于 StackOverflow