Xóa các phần tử trùng lặp khỏi danh sách Python có chứa các phần tử không thể khắc phục được trong khi vẫn giữ nguyên thứ tự?

Question

Tôi có một datastructure như thế này:

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

Và tôi muốn có được điều này:

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

Có cách nào tốt để làm điều này trong khi vẫn giữ trật tự như thể hiện?

lệnh cho copy-dán:

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

Answer 1

Đây là một câu hỏi hơi nổi tiếng mà cũng được trả lời bởi một Pythonista nổi tiếng từ lâu: http://code.activestate.com/recipes/52560-remove-duplicates-from-a-sequence/

Nếu bạn có thể giả định các hồ sơ tương đương là liền kề, có công thức trong số itertools docs:

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))) 

Nếu bạn chỉ có thể giả định các yếu tố có thể đặt hàng, ở đây một biến thể sử dụng bisect m odule. Với các đầu vào là n với r giá trị duy nhất, bước tìm kiếm của nó có chi phí O (n log r). Nếu tìm thấy một giá trị duy nhất mới, nó sẽ được chèn vào trong danh sách được xem với chi phí 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 

Answer 2

Đây là biến thể bảo toàn đơn hàng của thành ngữ sắp xếp/duy nhất. Điều này sẽ cung cấp cho bạn hiệu suất O (n log n), miễn là các mục của bạn ít nhất có thể sắp xếp được.

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] 

Ví dụ (với mục hashable vì đơn giản):

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