1.10.移除重复序列同时维持排序.md

1.10.移除重复序列同时维持排序

问题

如何移除重复数据的同时，保持既有排序？

解决方法

如果序列中的值是哈希过的，这个问题可同set和generator轻易解决，例如：

def dedupe(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(dedupe(a))
[1, 5, 2, 9, 10]
>>>

这仅在序列是哈希时有效。如果想对非哈希的序列去重（比如dicts），你可以改造一下上述代码：

def dedupe(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)

这里的key参数旨在指定一个可以把item转化成哈希类型的函数，这样就可以工作了，如下：

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

后面的这个解决方法对单值或者属性或者更大的数据结构的序列都在去重上都能很好的工作。

讨论

如果想去重，使用set通常很简单，比如：

>>> a
[1, 5, 2, 1, 9, 1, 5, 10]
>>> set(a)
{1, 2, 10, 5, 9}
>>>

然而， 这种实现不保持任何类型的排序。因此得到的数据顺序是杂乱的。而我们的方法解决了这个问题。

本方法的generator函数可以使得此函数具有通用性——没有直接绑定到list执行。比如，你可以使用这个函数对一个文本进行去重：

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

本方法中的key函数可以说是模仿了一些内建函数，比如sorted()，min()和max()的功能。请参见1.8和1.13。