在列表中去除重复项

Question

如何检查列表是否有任何重复项，并返回一个没有重复项的新列表？

- Neemaximo

---

如何使用多进程在一个非常大的列表中删除重复项？ - Darkonaut

有趣的是，这里的所有顶级答案都没有回答实际问题：创建一个仅包含原始列表中未重复项的新列表。我将其解读为 [1, 2, 3, 4, 5, 2, 4] -> [1, 3, 5]，因为2和4是重复的。 - 9769953

根据您的说法，使用Rev 11并仅保留由顶部答案回答的第一个子问题（即[1,2,3,1]→[1,2,3]）是否有意义？ 接受的答案暗示了可能实现第二个子问题的方法（即[1,2,3,1]→[2,3]）。 目前，问题和最佳答案在某种程度上不完全同步。 - Mateen Ulhaq

@MateenUlhaq 我更喜欢保留原始问题。此外，第11版更改了问题以更好地适应答案，但不一定适合原始问题。我想这取决于您希望SO成为多少论坛/邮件列表风格，或者与技巧和技巧网站（具有非常纯净的问题和答案）有多接近。我认为两者都无法实现。 - 9769953

换句话说，这将使问题成为 从另一个列表中删除所有出现的元素 的重复，该问题从一开始就提得更好。但似乎几乎每个人都看到了不同的问题。 - Karl Knechtel

Answer 1

常用的获取唯一项的方法是使用 set。集合是无序的，包含不同对象的集合。要从任何可迭代对象创建一个集合，只需将其传递给内置的 set() 函数即可。如果您稍后需要一个真正的列表，可以类似地将集合传递给 list() 函数。

以下示例应该涵盖您正在尝试做的任何事情：

>>> t = [1, 2, 3, 1, 2, 3, 5, 6, 7, 8]
>>> list(set(t))
[1, 2, 3, 5, 6, 7, 8]
>>> s = [1, 2, 3]
>>> list(set(t) - set(s))
[8, 5, 6, 7]

如您从示例结果中所见，原始顺序未保留。如上所述，集合本身是无序集合，因此顺序丢失。将集合转换回列表时，会创建任意顺序。

保持顺序

如果顺序对您很重要，则必须使用不同的机制。一个非常常见的解决方案是依靠 OrderedDict 在插入期间保持键的顺序:

>>> from collections import OrderedDict
>>> list(OrderedDict.fromkeys(t))
[1, 2, 3, 5, 6, 7, 8]

从Python 3.7开始, 内置字典保证维护插入顺序，因此如果您使用的是Python 3.7或更高版本（或者CPython 3.6），您也可以直接使用它：

>>> list(dict.fromkeys(t))
[1, 2, 3, 5, 6, 7, 8]

注意，这可能需要先创建一个字典，然后再从中创建一个列表，会有一些开销。如果你实际上不需要保留顺序，使用集合通常更好，特别是因为它给了你更多的操作。查看这个问题以获取更多详细信息和在删除重复项时保留顺序的替代方法。

---

最后请注意，无论是set还是OrderedDict/dict解决方案都需要你的项目是可哈希的。这通常意味着它们必须是不可变的。如果你必须处理不可哈希的项目（例如列表对象），那么你将不得不使用一种缓慢的方法，在其中你将基本上必须在嵌套循环中将每个项目与每个其他项目进行比较。

- poke

---

将此添加到示例中，t = [3, 2, 1, 1, 2, 5, 6, 7, 8]，清楚地显示了差异！ - sailfish009

"...首先创建字典的开销...如果你实际上不需要保留顺序，最好使用集合。" — 我进行了分析，因为我很好奇这是否是真的。我的时序表明，确实集合稍微快一些：在1M次循环中每个循环用时1.12微秒（集合）vs 1.53微秒（字典），在1M次迭代中绝对时间差约为4秒。所以，如果你在紧密的内部循环中执行此操作，则可能会关心，否则可能不太需要。 - millerdev

@millerdev 我本来想说一些类似“开销不只是时间”的话，但是我查了一下，发现一个带键字的词典实际上比具有相同元素的集合在内存中更小。至少在目前的Python版本中是这样的。这真的很令人惊讶，但是确实是个好点子！谢谢！ - poke

这段代码解决了不可哈希类型的问题（其中t是一个字典列表）：[dict(d) for d in set([frozenset(i.items()) for i in t])] - Fredrik Erlandsson

@BigDreamz dict.fromkeys() 可以在线性时间内创建一个字典，而 list() 也可以在线性时间内从中创建一个列表。 - poke

Answer 2

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

- Raymond Hettinger

---

我认为这是保持物品井然有序的唯一方式。 - Herberth Amaral

这与事实相差甚远，请参阅如何在Python中删除列表中的重复项并保留顺序？。 - Martijn Pieters

@MartijnPieters 纠正：我认为这是保持项目有序的唯一简单方法。 - Herberth Amaral

为此，原始列表的内容也必须是可哈希的。 - Davide

正如@Davide提到的那样，原始列表必须是可哈希的。这意味着，对于字典列表是不起作用的。 “TypeError: unhashable type: 'dictlist'” - CraZ

如果原始列表不可哈希，more-itertools 包提供了 unique_everseen 函数，可以处理可哈希和不可哈希的项。 - Asclepius

Answer 3

一行代码解决问题：list(set(source_list))。

set 是不可能有重复项的。

更新：保留顺序的做法是两行：

from collections import OrderedDict
OrderedDict((x, True) for x in source_list).keys()

我们在这里利用了 OrderedDict 记住键的插入顺序的特性，并且在特定键的值被更新时不会改变它。我们将 True 作为值插入，但我们也可以插入任何其他值。 (set 的工作方式与忽略值的 dict 很像。)

- 9000

---

@AdrianKeister：这是真的。有些对象具有合理的相等语义，但不可哈希，例如列表。另一方面，如果我们不能像哈希表那样有一个快捷方式，我们最终会得到一个二次算法，即将每个元素与所有当前已知的唯一元素进行比较。对于短输入，特别是有很多重复项的情况下，这可能完全没问题。 - 9000

没错，确切地说。如果您考虑到这个非常常见的用例，我认为您的答案将会更高质量。 - Adrian Keister

Answer 4

>>> t = [1, 2, 3, 1, 2, 5, 6, 7, 8]
>>> t
[1, 2, 3, 1, 2, 5, 6, 7, 8]
>>> s = []
>>> for i in t:
       if i not in s:
          s.append(i)
>>> s
[1, 2, 3, 5, 6, 7, 8]

- Neeraj

---

请注意，该方法的时间复杂度为O(n^2)，因此在处理大型列表时速度非常慢。 - dotancohen

Answer 5

如果您不关心顺序，可以这样做：

def remove_duplicates(l):
    return list(set(l))

set 保证不会有重复元素。

- Brendan Long

---

真棒，简单而有效。 - Blenzus

Answer 6

为了创建一个新的列表，保留L中重复元素的第一个出现的顺序：

newlist = [ii for n,ii in enumerate(L) if ii not in L[:n]]

例如：如果 L = [1, 2, 2, 3, 4, 2, 4, 3, 5]，那么 newlist 将会是 [1, 2, 3, 4, 5]。 这个操作检查每个新元素在添加之前是否已经出现在列表中。 而且它不需要导入。

- Richard Fredlund

---

这个算法的时间复杂度为**O(n ^ 2)**。使用set和OrderedDict可能会有更低的摊销时间复杂度。 - blubberdiblub

我在我的代码中使用了这个解决方案，效果很好，但我认为它很耗时间。 - Gerasimos Ragavanis

@blubberdiblub，你能解释一下在set和OrderedDict中存在哪些更加代码高效的机制，可以使它们更少耗费时间吗？（不包括加载它们的开销） - ilias iliadis

@iliasiliadis 通常的 set 和 dict 实现使用哈希或（某种平衡）树。您必须考虑构建 set 或 dict 并在其中搜索（多次），但它们的摊销复杂度通常仍低于 **O(n ^ 2)**。简单来说，“摊销”意味着平均情况下（它们可能具有比平均情况更高复杂度的最坏情况）。这仅在您拥有大量项目时才相关。 - blubberdiblub

很好的答案，如果元素不可哈希，它就能正常工作。然而，如果元素是Numpy数组，你可能会有些惊讶，因为in运算符并不像人们期望的那样工作（至少我是这么期望的）。 - Keta

Answer 7

还有使用Pandas和Numpy的解决方案。它们都返回numpy数组，因此如果您想要一个列表，您需要使用函数.tolist()。

t=['a','a','b','b','b','c','c','c']
t2= ['c','c','b','b','b','a','a','a']

Pandas解决方案

使用Pandas函数unique()：

import pandas as pd
pd.unique(t).tolist()
>>>['a','b','c']
pd.unique(t2).tolist()
>>>['c','b','a']

Numpy解决方案

使用numpy函数unique()。

import numpy as np
np.unique(t).tolist()
>>>['a','b','c']
np.unique(t2).tolist()
>>>['a','b','c']

请注意，numpy.unique()也会对值进行排序。因此，列表t2将被返回并排序。如果您想保留顺序，请使用如这个答案中的方法：

_, idx = np.unique(t2, return_index=True)
t2[np.sort(idx)].tolist()
>>>['c','b','a']

这个解决方案与其他方案相比不太优雅，但与pandas.unique()相比，numpy.unique()还允许您检查沿着一个选择的轴是否唯一。

- G M

---

这将把列表转换为numpy数组，但对于字符串来说会很混乱，无法正常工作。 - user227666

@user227666 感谢您的评论，但那不是真的，它甚至可以与字符串一起使用，如果您想获得列表，可以添加.tolist。 - G M

我认为这有点像用大锤子去杀一只蜜蜂。当然可以做到！但是，仅仅为了这个目的导入一个库可能有点过头了，不是吗？ - Debosmit Ray

@DebosmitRay 如果你从事数据科学工作，那么这将非常有用，因为通常你需要使用numpy，并且经常需要处理numpy数组。 - G M

2020年最佳答案： @DebosmitRay，我希望你改变想法，尽可能地使用numpy / pandas。 - Egos

Answer 8

超级晚回答

如果你不在意列表的顺序，你可以使用*arg扩展和set的唯一性来去除重复项，例如：

l = [*{*l}]

Python3 演示

- Pedro Lobito

---

好的，问题在于它太聪明了，你可能需要添加一条评论来说明它的作用。 - mike rodent

Answer 9

在这个答案中，将有两个部分：两个独特的解决方案和特定解决方案速度的图表。

去除重复项

大多数答案仅删除可哈希的重复项，但是这个问题并不意味着它只需要可哈希的项，因此我将提供一些不需要可哈希的项的解决方案。

collections.Counter是标准库中一个强大的工具，非常适合处理这个问题。只有另一个解决方案中包含Counter。然而，该解决方案也仅限于可哈希键。

为了允许Counter中使用不可哈希键，我创建了一个Container类，它将尝试获取对象的默认哈希函数，但如果失败，则尝试其标识函数。它还定义了一个eq和一个hash方法。这应该足以允许不可哈希的项出现在我们的解决方案中。不可哈希的对象将被视为可哈希的对象。但是，这个哈希函数对于不可哈希的对象使用标识符，这意味着两个相等的不可哈希对象都无法正常工作。我建议您覆盖它，并将其更改为使用等效的可变类型的哈希（例如，如果my_list是列表，则使用hash(tuple(my_list))）。

我还制作了两个解决方案。另一个解决方案保留项的顺序，使用OrderedDict和Counter的子类命名为“OrderedCounter”。现在，这些是函数：

from collections import OrderedDict, Counter

class Container:
    def __init__(self, obj):
        self.obj = obj
    def __eq__(self, obj):
        return self.obj == obj
    def __hash__(self):
        try:
            return hash(self.obj)
        except:
            return id(self.obj)

class OrderedCounter(Counter, OrderedDict):
     'Counter that remembers the order elements are first encountered'

     def __repr__(self):
         return '%s(%r)' % (self.__class__.__name__, OrderedDict(self))

     def __reduce__(self):
         return self.__class__, (OrderedDict(self),)
    
def remd(sequence):
    cnt = Counter()
    for x in sequence:
        cnt[Container(x)] += 1
    return [item.obj for item in cnt]

def oremd(sequence):
    cnt = OrderedCounter()
    for x in sequence:
        cnt[Container(x)] += 1
    return [item.obj for item in cnt]

remd是无序排序，而oremd是有序排序。你可以清楚地看出哪一个更快，但我还是会解释一下。非有序排序略快，因为它不存储项目的顺序。

现在，我也想展示每个答案的速度比较。所以，我现在就这样做。

哪个函数最快？

对于去重，我从几个答案中收集了10个函数。我计算了每个函数的速度，并使用matplotlib.pyplot将其放入图表中。

我将此分为三轮绘图。可哈希对象是任何可以哈希的对象，不可哈希对象是任何不能哈希的对象。有序序列是保留顺序的序列，无序序列不保留顺序。现在，这里还有一些术语：

无序可哈希是用于删除重复项的任何方法，它不一定要保持顺序。它不必适用于不可哈希对象，但它可以。

有序可哈希是保持列表中项目顺序的任何方法，但它不必适用于不可哈希对象，但它可以。

有序不可哈希是保持列表中项目顺序并适用于不可哈希对象的任何方法。

在y轴上是所需的秒数。

在x轴上是应用该函数的数字。

我使用以下推导式为无序可散列对象和有序可散列对象生成序列：[list(range(x)) + list(range(x)) for x in range(0, 1000, 10)]

对于有序的不可散列对象：[[list(range(y)) + list(range(y)) for y in range(x)] for x in range(0, 1000, 10)]

请注意，范围中有一个step，因为没有它，这将需要10倍的时间。另外，因为在我个人看来，我认为这可能会看起来更容易阅读。

还要注意图例上的键是我尝试猜测函数实现中最关键的部分。至于哪个函数做得最好或最差？图表说明了一切。

有了这个解决，这里是图表。

无序可散列对象

（放大）

有序可散列对象

(放大)

有序的不可哈希对象

(放大)

- Corman

---

阅读困难。最好在底部有一个顶部列表，将结果包装起来。因此，对于无序的可哈希对象： 不要使用： #- ii for n,ii in enumerate(seq) if ii not in seq[:n] #- cnt = Counter(); cnt[Container(x)] += 1 #- cnt = OrderedCounter(); cnt[Container(x)) += 1 #- if i not in new for i in seq. 最好使用： #- list(set(seq)) #- dict.fromkeys(seq) #- added = set(); for in seq: if not val in added #- OrderedDict.fromkeys(seq) #- OrderedDict((x, True) for x in seq).keys() #- functools.reduce(lambda r, v: v in r[1] and r or ... or ..., ([], set[]))[0] - questionto42

Answer 10

今天我的一个同事在代码审查中将他的已接受答案发送给了我。 虽然我确实欣赏所提出答案的优雅，但是我对其性能并不满意。 我已经尝试过这个解决方案（我使用 set 来减少查找时间）。

def ordered_set(in_list):
    out_list = []
    added = set()
    for val in in_list:
        if not val in added:
            out_list.append(val)
            added.add(val)
    return out_list

为了比较效率，我使用了一个包含100个整数的随机样本——其中有62个是唯一的。

from random import randint
x = [randint(0,100) for _ in xrange(100)]

In [131]: len(set(x))
Out[131]: 62

这里是测量结果。

In [129]: %timeit list(OrderedDict.fromkeys(x))
10000 loops, best of 3: 86.4 us per loop

In [130]: %timeit ordered_set(x)
100000 loops, best of 3: 15.1 us per loop

好的，如果从解决方案中删除了集合会发生什么？

def ordered_set(inlist):
    out_list = []
    for val in inlist:
        if not val in out_list:
            out_list.append(val)
    return out_list

结果与 OrderedDict 相比并不那么糟糕，但仍然比原来的解决方案多了3倍以上

In [136]: %timeit ordered_set(x)
10000 loops, best of 3: 52.6 us per loop

- volcano

---

使用集合进行快速查找以加速循环比较非常不错。如果顺序不重要，list(set(x)) 仍然比这种方法快6倍。 - Joop

@Joop，那是我向同事提出的第一个问题——顺序很重要；否则，这将是一个琐碎的问题。 - volcano

优化版本的有序集合，对于任何感兴趣的人：def unique(iterable):; seen = set(); seen_add = seen.add; return [item for item in iterable if not item in seen and not seen_add(item)] - DrD