Câu hỏi Loại bỏ dict trùng lặp trong danh sách bằng Python


Tôi có một danh sách các dicts, và tôi muốn loại bỏ các dicts với các cặp khóa và giá trị giống hệt nhau.

Đối với danh sách này: [{'a': 123}, {'b': 123}, {'a': 123}]

Tôi muốn trả lại điều này: [{'a': 123}, {'b': 123}]

Một vi dụ khac:

Đối với danh sách này: [{'a': 123, 'b': 1234}, {'a': 3222, 'b': 1234}, {'a': 123, 'b': 1234}]

Tôi muốn trả lại điều này: [{'a': 123, 'b': 1234}, {'a': 3222, 'b': 1234}]


76
2018-02-24 07:46


gốc


Bạn có thể cho chúng tôi biết thêm về vấn đề thực tế bạn đang cố giải quyết không? Điều này có vẻ như là một vấn đề kỳ lạ. - gfortune
Tôi đang kết hợp một vài danh sách các dicts và có bản sao. Vì vậy, tôi cần phải loại bỏ những bản sao đó. - Brenden
Tôi tìm thấy một giải pháp trong stackoverflow.com/questions/480214/… trong một câu trả lời mà không cần sử dụng set() - Sebastian Wagner


Các câu trả lời:


Thử cái này:

[dict(t) for t in {tuple(d.items()) for d in l}]

Chiến lược này là chuyển đổi danh sách từ điển thành danh sách các bộ dữ liệu nơi các bộ dữ liệu chứa các mục của từ điển. Vì các tuple có thể được băm, bạn có thể loại bỏ các bản sao bằng cách sử dụng set (sử dụng một thiết lập hiểu ở đây, thay thế python cũ hơn sẽ là set(tuple(d.items()) for d in l)) và, sau đó, tạo lại từ điển từ bộ dữ liệu với dict.

Ở đâu:

  • l là danh sách gốc
  • d là một trong những từ điển trong danh sách
  • t là một trong những bộ tuples được tạo từ một từ điển

Chỉnh sửa: Nếu bạn muốn giữ nguyên thứ tự, một lớp lót phía trên sẽ không hoạt động kể từ set sẽ không làm điều đó. Tuy nhiên, với một vài dòng mã, bạn cũng có thể làm điều đó:

l = [{'a': 123, 'b': 1234},
        {'a': 3222, 'b': 1234},
        {'a': 123, 'b': 1234}]

seen = set()
new_l = []
for d in l:
    t = tuple(d.items())
    if t not in seen:
        seen.add(t)
        new_l.append(d)

print new_l

Ví dụ đầu ra:

[{'a': 123, 'b': 1234}, {'a': 3222, 'b': 1234}]

Lưu ý: Như được chỉ ra bởi @alexis, có thể xảy ra hai từ điển có cùng khóa và giá trị, không dẫn đến cùng một bộ dữ liệu. Điều đó có thể xảy ra nếu họ trải qua lịch sử thêm / xóa khóa khác. Nếu đó là trường hợp cho vấn đề của bạn, sau đó xem xét phân loại d.items() như anh ta gợi ý.


135
2018-02-24 07:51



trong ví dụ này, l là gì? (ở cho d trong l) - Brenden
@Brenden Tôi đã cập nhật câu trả lời với thông tin đó. l là danh sách bạn đang làm việc. - jcollado
Giải pháp tốt nhưng có lỗi: d.items() không được bảo đảm trả về các phần tử theo một thứ tự cụ thể. Bạn nên làm tuple(sorted(d.items())) để đảm bảo bạn không nhận được các bộ dữ liệu khác nhau cho cùng một cặp khóa-giá trị. - alexis
@alexis Tôi đã thực hiện một vài bài kiểm tra và bạn thực sự đúng. Nếu có nhiều khóa được thêm vào giữa và bị xóa sau, thì đó có thể là trường hợp. Cảm ơn rất nhiều về lời bình luận của bạn. - jcollado
Lưu ý, điều này sẽ không hoạt động nếu bạn tải trong danh sách các dicts từ một json module như tôi đã làm - Dhruv Ghulati


Một lớp lót khác dựa trên việc hiểu danh sách:

>>> d = [{'a': 123}, {'b': 123}, {'a': 123}]
>>> [i for n, i in enumerate(d) if i not in d[n + 1:]]
[{'b': 123}, {'a': 123}]

Ở đây vì chúng ta có thể sử dụng dict so sánh, chúng tôi chỉ giữ các phần tử không nằm trong phần còn lại của danh sách ban đầu (khái niệm này chỉ có thể truy cập được thông qua chỉ mục n, do đó việc sử dụng enumerate).


28
2018-02-24 09:05



Điều này cũng làm việc cho một danh sách các từ điển bao gồm các danh sách so với câu trả lời đầu tiên - gbozee
điều này cũng hoạt động khi bạn có thể có một loại không thể loại bỏ như là một giá trị trong từ điển của bạn, không giống như câu trả lời hàng đầu. - Steve Rossiter
Điều này làm việc tốt hơn cho tôi so với câu trả lời đã chọn. - nikhilvj


Đôi khi các vòng kiểu cũ vẫn hữu ích. Mã này dài hơn jcollado một chút, nhưng rất dễ đọc:

a = [{'a': 123}, {'b': 123}, {'a': 123}]
b = []
for i in range(0, len(a)):
    if a[i] not in a[i+1:]:
        b.append(a[i])

12
2018-02-24 08:10



Các 0trong range(0, len(a)) không cần thiết. - Juan Antonio


Các câu trả lời khác sẽ không hoạt động nếu bạn đang hoạt động trên các từ điển lồng nhau như các đối tượng JSON được deserialized. Đối với trường hợp này, bạn có thể sử dụng:

import json
set_of_jsons = {json.dumps(d, sort_keys=True) for d in X}
X = [json.loads(t) for t in set_of_jsons]

8
2017-08-02 13:52





Nếu bạn muốn giữ gìn trật tự, bạn có thể làm

from collections import OrderedDict
print OrderedDict((frozenset(item.items()),item) for item in data).values()
# [{'a': 123, 'b': 1234}, {'a': 3222, 'b': 1234}]

Nếu thứ tự không quan trọng, thì bạn có thể làm

print {frozenset(item.items()):item for item in data}.values()
# [{'a': 3222, 'b': 1234}, {'a': 123, 'b': 1234}]

7
2018-04-29 07:52





Bạn có thể sử dụng một bộ, nhưng bạn cần phải biến các dicts thành một loại hashable.

seq = [{'a': 123, 'b': 1234}, {'a': 3222, 'b': 1234}, {'a': 123, 'b': 1234}]
unique = set()
for d in seq:
    t = tuple(d.iteritems())
    unique.add(t)

Hiện tại bằng

set([(('a', 3222), ('b', 1234)), (('a', 123), ('b', 1234))])

Để có được dicts trở lại:

[dict(x) for x in unique]

0
2018-02-24 08:03





Không phải là một câu trả lời phổ quát, nhưng nếu danh sách của bạn xảy ra sắp xếp bởi một số khóa, như thế này:

l=[{'a': {'b': 31}, 't': 1},
   {'a': {'b': 31}, 't': 1},
 {'a': {'b': 145}, 't': 2},
 {'a': {'b': 25231}, 't': 2},
 {'a': {'b': 25231}, 't': 2}, 
 {'a': {'b': 25231}, 't': 2}, 
 {'a': {'b': 112}, 't': 3}]

thì giải pháp đơn giản như:

import itertools
result = [a[0] for a in itertools.groupby(l)]

Kết quả:

[{'a': {'b': 31}, 't': 1},
{'a': {'b': 145}, 't': 2},
{'a': {'b': 25231}, 't': 2},
{'a': {'b': 112}, 't': 3}]

Làm việc với các từ điển lồng nhau và (rõ ràng) bảo tồn trật tự.


0
2018-06-14 07:49





Nếu sử dụng gói của bên thứ ba thì không sao thì bạn có thể sử dụng iteration_utilities.unique_everseen:

>>> from iteration_utilities import unique_everseen
>>> l = [{'a': 123}, {'b': 123}, {'a': 123}]
>>> list(unique_everseen(l))
[{'a': 123}, {'b': 123}]

Nó giữ nguyên thứ tự của danh sách ban đầu và ut cũng có thể xử lý các mục không thể hoán đổi như từ điển bằng cách giảm về một thuật toán chậm hơn (O(n*m) Ở đâu n là các yếu tố trong danh sách gốc và m các yếu tố duy nhất trong danh sách gốc thay vì O(n)). Trong trường hợp cả khóa và giá trị đều có thể băm, bạn có thể sử dụng key đối số của hàm đó để tạo các mục có thể băm cho "kiểm tra tính duy nhất" (để nó hoạt động trong O(n)).

Trong trường hợp của một từ điển (so sánh độc lập với thứ tự), bạn cần ánh xạ nó tới một cấu trúc dữ liệu khác so sánh như vậy, ví dụ frozenset:

>>> list(unique_everseen(l, key=lambda item: frozenset(item.items())))
[{'a': 123}, {'b': 123}]

Lưu ý rằng bạn không nên sử dụng đơn giản tuplecách tiếp cận (không phân loại) vì các từ điển tương đương không nhất thiết phải có cùng thứ tự (ngay cả trong Python 3.7, thứ tự chèn - không phải thứ tự tuyệt đối - được đảm bảo):

>>> d1 = {1: 1, 9: 9}
>>> d2 = {9: 9, 1: 1}
>>> d1 == d2
True
>>> tuple(d1.items()) == tuple(d2.items())
False

Và thậm chí sắp xếp bộ túp có thể không hoạt động nếu các phím không thể sắp xếp:

>>> d3 = {1: 1, 'a': 'a'}
>>> tuple(sorted(d3.items()))
TypeError: '<' not supported between instances of 'str' and 'int'

Điểm chuẩn

Tôi nghĩ có thể hữu ích khi xem hiệu suất của các phương pháp này so sánh như thế nào, vì vậy tôi đã làm một điểm chuẩn nhỏ. Biểu đồ điểm chuẩn là thời gian so với kích thước danh sách dựa trên danh sách không chứa các bản sao (được chọn tùy ý, thời gian chạy không thay đổi đáng kể nếu tôi thêm một số hoặc nhiều bản sao). Đó là một âm mưu log-log để phạm vi hoàn chỉnh được bao phủ.

Thời gian tuyệt đối:

enter image description here

Thời gian liên quan đến cách tiếp cận nhanh nhất:

enter image description here

Cách tiếp cận thứ hai từ thefourtheye là nhanh nhất ở đây. Các unique_everseen tiếp cận với key chức năng là ở vị trí thứ hai, tuy nhiên đó là phương pháp nhanh nhất giữ gìn trật tự. Các cách tiếp cận khác từ jcollado và thefourtheye gần như là nhanh. Cách tiếp cận sử dụng unique_everseen không có chìa khóa và các giải pháp từ Emmanuel và Scorpil rất chậm đối với các danh sách dài hơn và hoạt động kém hơn nhiều O(n*n) thay vì O(n). stpkcách tiếp cận với json không phải O(n*n) nhưng nó chậm hơn nhiều so với O(n) phương pháp tiếp cận.

Mã để tạo lại điểm chuẩn:

from simple_benchmark import benchmark
import json
from collections import OrderedDict
from iteration_utilities import unique_everseen

def jcollado_1(l):
    return [dict(t) for t in {tuple(d.items()) for d in l}]

def jcollado_2(l):
    seen = set()
    new_l = []
    for d in l:
        t = tuple(d.items())
        if t not in seen:
            seen.add(t)
            new_l.append(d)
    return new_l

def Emmanuel(d):
    return [i for n, i in enumerate(d) if i not in d[n + 1:]]

def Scorpil(a):
    b = []
    for i in range(0, len(a)):
        if a[i] not in a[i+1:]:
            b.append(a[i])

def stpk(X):
    set_of_jsons = {json.dumps(d, sort_keys=True) for d in X}
    return [json.loads(t) for t in set_of_jsons]

def thefourtheye_1(data):
    return OrderedDict((frozenset(item.items()),item) for item in data).values()

def thefourtheye_2(data):
    return {frozenset(item.items()):item for item in data}.values()

def iu_1(l):
    return list(unique_everseen(l))

def iu_2(l):
    return list(unique_everseen(l, key=lambda inner_dict: frozenset(inner_dict.items())))

funcs = (jcollado_1, Emmanuel, stpk, Scorpil, thefourtheye_1, thefourtheye_2, iu_1, jcollado_2, iu_2)
arguments = {2**i: [{'a': j} for j in range(2**i)] for i in range(2, 12)}
b = benchmark(funcs, arguments, 'list size')

%matplotlib widget
import matplotlib as mpl
import matplotlib.pyplot as plt
plt.style.use('ggplot')
mpl.rcParams['figure.figsize'] = '8, 6'

b.plot(relative_to=thefourtheye_2)

Đối với tính đầy đủ ở đây là thời gian cho một danh sách chỉ chứa các bản sao:

# this is the only change for the benchmark
arguments = {2**i: [{'a': 1} for j in range(2**i)] for i in range(2, 12)}

enter image description here

Thời gian không thay đổi đáng kể ngoại trừ unique_everseen không có key chức năng, trong trường hợp này là giải pháp nhanh nhất. Tuy nhiên đó chỉ là trường hợp tốt nhất (do đó không phải là đại diện) cho hàm đó với các giá trị không thể thực hiện được vì thời gian chạy của nó phụ thuộc vào số lượng các giá trị duy nhất trong danh sách: O(n*m) mà trong trường hợp này chỉ là 1 và do đó nó chạy trong O(n).


Disclaimer: Tôi là tác giả của iteration_utilities.


0
2017-07-17 19:43