从包含不可哈希元素的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')])

- Legend

---

重复项是否总是相邻的？ - Cameron

Answer 1

这是一个比较有名的问题，早先由一位著名的Pythonista进行了很好的回答：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模块的一种变体。 对于具有r个唯一值的n个输入，其搜索步骤的成本为O（n log r）。 如果发现新的唯一值，则将其插入“seen”列表，成本为O（r * r）。

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

- Raymond Hettinger

---

Tim Peters 提出的唯一保序算法是暴力破解。尽管如此，排序算法可以被修改以保持 O(n log n) 的性能同时保持顺序。 - Sven Marnach

有保序变体是由Alex Martelli编写的，并在评论中列出了Tim的代码之后。 - Raymond Hettinger

据我所知，Alex Martelli 的所有变体都假定具有 hasability。 - Sven Marnach

我认为在那里有一个非可哈希、非暴力破解的变体，并且它已经被纳入了Python Cookbook。如果它不在那里，我已经编辑了上面的答案，展示了如何使用bisect来完成（假设具有可排序性，但不具备可哈希性）。 - Raymond Hettinger

我认为你的算法是O(n*n)，因为有seen.insert(i, x)。（这是插入排序。） - Sven Marnach

在最坏的情况下，每个输入都是唯一的。插入步骤仅在遇到新的唯一值时发生。当存在许多重复项时，插入通常会被跳过。dedup('GATTACAACGTCAT')进行了四次插入。 - Raymond Hettinger

Answer 2

这里是排序/去重套路的一个保序变体。如果你的项至少可以排序，那么这将为您提供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']

- Sven Marnach