从可比较、不可哈希的项目列表中删除重复项的最快方法

Question

如果我知道列表的元素是可以排序的，但我不关心列表中项目的顺序，该如何从列表中删除重复的项目？像如何从Python列表中删除重复项并保留顺序？或在列表中去除重复项这样的现有问题需要使用集合，即要求列表中的项目是可哈希的。但在我的情况下，哈希性不能保证。请注意保持 HTML 标签不变。

- vitiral

---

这是对于“如何从列表中删除重复项”的问题的荒谬要求--列表可以包含任何内容，因此它并没有真正回答这个问题，是吧？ - vitiral

@TigerhawkT3 请重新开放。我花了很长时间才找到这个问题，John La Rooy的答案非常棒！ - vitiral

哇，那个评论被埋得很深，是第三个答案，而实际上对评论的回复才是答案。但无论如何。 - vitiral

让Python集合来完成所有工作怎么样？list(set(list)) 集合需要可哈希元素吗？ - Trilarion

是的，集合需要可哈希的元素。set([{'a': 2}])会抛出TypeError: unhashable type: 'dict'异常。如果我想从一个字典列表中删除重复项，我不能使用那些用户标记的“重复项”。 - vitiral

Answer 1

在Python中，对已经排序好的列表调用sorted函数几乎没有额外的开销。因此，没有必要增加额外的复杂性和可能会导致某人不小心传递错误参数给函数的可能性。

from itertools import groupby
def remove_duplicates(data):
    ''' Remove duplicates from the data (normally a list).
        The data must be sortable and have an equality operator
    '''
    data = sorted(data)
    return [k for k, v in groupby(data)]

- John La Rooy

---

太棒了！我没想到itertools的groupby可以这样使用，真是太聪明了！看着groupby的代码，似乎"k"甚至不需要是可哈希的，这正是我所期待的。 - vitiral

由于问题要求“最快”，因此可能需要添加比较结果来支持该说法。 - ivan_pozdeev

Answer 2

编辑：请参考John La Rooy的答案，那个更好。

再次说明，这个解决方案仅适用于可排序的列表。如果您预先对其进行了排序（实际上只需要将对象进行分组），则可以设置sort=False，然后它只需要比较运算符。

def remove_duplicates(data, sort=True):
    ''' Remove duplicates from the data (normally a list).
        The data must be sortable and have an equality operator
    '''
    if not data:
        return data
    if sort:
        data = sorted(data)
    out = [data[0]]
    for i, n in enumerate(data[1:]):
        if data[i] != n:
            out.append(n)
    return out

- vitiral

---

你最好定义__hash__，这样你就可以使用set()。 - TigerhawkT3

测试不够精确，但是你的标题说“最快”，我似乎使用from itertools import izip_longest和out = [x for (x,y) in izip_longest(data,data[1:]) if x != y]可以获得更快的结果。给定range(1000)*3，所以所有内容都被复制三次，并且预先排序，运行10,000次迭代，使用你的代码需要约5秒钟，而使用izip_longest只需要3.3秒，结果列表相同。 - TessellatingHeckler

这大致是此用户在其中一个重复线程中建议的，但a）与numpy无关，b）我怀疑如果它不是重复项，则会漏掉最后一个列表项的错误，并且c）他们正在使用内置的zip，当我尝试时，它没有相同的加速。 （也许在Python 3中？）itertools版本使用None填充较短的列表并修复了最后一个项目错误，我认为它也更快。 - TessellatingHeckler

迭代一个额外的项目比复制切片data[1：]更快。 - John La Rooy

@TessellatingHeckler - Python 3的zip()，itertools.zip_longest()，range()等已经生成惰性对象而不是急切地创建一个list。 - TigerhawkT3