Python从序列中移除重复项且保持元素间顺序不变

问题

我们想去除序列中出现的重复元素，但仍然保持剩下的元素顺序不变。

解决方案

如果序列中的值是可哈希的（hashable: 如果一个对象是可哈希的，那么在它的生存期内必须是不可变的，它需要有一个__hash__()方法。整数、浮点数、字符串、元组都是不可变的），那么这个问题可以通过使用集合和生成器轻松解决。示例如下：

def dedupe(items):
    seen = set()
    for item in items:
        if item not in seen:
            yield item
            seen.add(item)

这里是如何使用这个函数的例子：

>>> data = [1, 2, 1, 3, 5, 3]
>>> list(dedupe(data))
[1, 2, 3, 5]
>>> data = ('A', 'B', 'C', 'A', 'B', 'D')
>>> list(dedupe(data))
['A', 'B', 'C', 'D']

只有当序列中的元素时可哈希的时候才能这么做。如果想在不可哈希的对象（比如列表）序列中去除重复项，需要对上述代码稍作修改：

def dedupe(items, key=None):
    seen = set()
    for item in items:
        value = item if key is None else key(item)
        if value not in seen:
            yield item
            seen.add(value)

这里参数key的作用是指定一个函数用来将序列中的元素转换为可哈希的类型，这么做的目的是为了检测重复项（集合中的元素必须是可哈希的），它可以像这样工作：

>>> data = [{'x':1, 'y':2}, {'x':1, 'y':3}, {'x':1, 'y':2}, {'x':2, 'y':4}]
>>> list(dedupe(data, key=lambda d: (d['x'], d['y'])))
[{'x': 1, 'y': 2}, {'x': 1, 'y': 3}, {'x': 2, 'y': 4}]
>>> list(dedupe(data, key=lambda d: d['x']))
[{'x': 1, 'y': 2}, {'x': 2, 'y': 4}]

如果希望在一个较复杂的数据结构中，只根据对象的某个字段或属性来去除重复项，那么后一种解决方案同样能完美工作。

讨论

如果想要做的只是去除重复项，那么通常足够简单的办法就是构建一个集合。例如：

>>> data = [1, 2, 1, 3, 5, 3]
>>> set(data)
{1, 2, 3, 5}
>>> list(set(data))
[1, 2, 3, 5]

但是这种方法不能保证元素间顺序不变（集合的特点就是集合中的元素是唯一的，但不保证它们之间的顺序），因此得到的结果会被打乱。前面展示的解决方案可避免这个问题。
本文中对生成器的使用反映出一个事实，那就是我们可能会希望这个函数尽可能的通用，不必绑定在只能对列表进行处理。比如，如果读一个文件，去除其中重复的文本行，可以只需这样处理：

with open('somefile.txt') as f:
    for line in dedupe(f):
        ...

我们的dedupe函数也模仿了内置函数sorted()、min()、max()对key函数的使用方式。