如何在保持顺序的同时从包含不可哈希元素的Python列表中移除重复项？

Question

我有一个这样的数据结构：

[
[('A', '1'), ('B', '2')],
[('A', '1'), ('B', '2')],
[('A', '4'), ('C', '5')]
]

我想得到这个：

[
[('A', '1'), ('B', '2')],
[('A', '4'), ('C', '5')]
]

有没有好的方法可以做到这一点，同时保持显示的顺序呢？

可以直接复制粘贴的命令：

sample = []
sample.append([('A', '1'), ('B', '2')])
sample.append([('A', '1'), ('B', '2')])
sample.append([('A', '4'), ('C', '5')])

Answer 1

这里有一个保持顺序的排序和去重的方法。这种方法的性能是 O(n log n)，前提是你的项目至少是可以排序的。

def unique(a):
    indices = sorted(range(len(a)), key=a.__getitem__)
    indices = set(next(it) for k, it in 
                  itertools.groupby(indices, key=a.__getitem__))
    return [x for i, x in enumerate(a) if i in indices]

举个例子（为了简单起见，这里使用可以哈希的项目）：

>>> a = ['F', 'J', 'B', 'F', 'V', 'A', 'E', 'U', 'B', 'U', 'Z', 'K']
>>> unique(a)
['F', 'J', 'B', 'V', 'A', 'E', 'U', 'Z', 'K']

Answer 2

这是一个比较有名的问题，早在很久以前就被一位著名的Python高手很好地回答过： http://code.activestate.com/recipes/52560-remove-duplicates-from-a-sequence/

如果你可以假设相同的记录是相邻的，那么在itertools文档中有一个解决方案：

from operator import itemgetter
from itertools import groupby, imap

def unique_justseen(iterable, key=None):
    "List unique elements, preserving order. Remember only the element just seen."
    # unique_justseen('AAAABBBCCDAABBB') --> A B C D A B
    # unique_justseen('ABBCcAD', str.lower) --> A B C A D
    return imap(next, imap(itemgetter(1), groupby(iterable, key)))

如果你只能假设元素是可以排序的，这里有一个使用bisect模块的变体。给定n个输入和r个唯一值，它的搜索步骤的复杂度是O(n log r)。如果发现了一个新的唯一值，它会以O(r * r)的成本插入到seen列表中。

from bisect import bisect_left, insort

def dedup(seq):
    'Remove duplicates. Preserve order first seen.  Assume orderable, but not hashable elements'
    result = []
    seen = []
    for x in seq:
        i = bisect_left(seen, x)
        if i == len(seen) or seen[i] != x:
            seen.insert(i, x)
            result.append(x)
    return result