Pertanyaan Hapus duplikat dict dalam daftar dengan Python


Saya memiliki daftar dicts, dan saya ingin menghapus dicts dengan pasangan kunci dan nilai yang identik.

Untuk daftar ini: [{'a': 123}, {'b': 123}, {'a': 123}]

Saya ingin mengembalikan ini: [{'a': 123}, {'b': 123}]

Contoh lain:

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

Saya ingin mengembalikan ini: [{'a': 123, 'b': 1234}, {'a': 3222, 'b': 1234}]


75
2018-02-24 07:46


asal


Jawaban:


Coba ini:

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

Strateginya adalah mengubah daftar kamus menjadi daftar tupel di mana tupel berisi item-item kamus. Karena tupel dapat di-hash, Anda dapat menghapus duplikat menggunakan set (menggunakan sebuah mengatur pemahaman di sini, alternatif python yang lebih tua akan set(tuple(d.items()) for d in l)) dan, setelah itu, buat ulang kamus dari tuples dengan dict.

dimana:

  • l adalah daftar asli
  • d adalah salah satu kamus dalam daftar
  • t adalah salah satu tupel yang dibuat dari kamus

Edit: Jika Anda ingin mempertahankan pemesanan, liner satu di atas tidak akan berfungsi set tidak akan melakukan itu. Namun, dengan beberapa baris kode, Anda juga dapat melakukannya:

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

Contoh keluaran:

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

Catatan: Seperti yang ditunjukkan oleh @alexis mungkin terjadi bahwa dua kamus dengan kunci dan nilai yang sama, tidak menghasilkan tupel yang sama. Itu bisa terjadi jika mereka melalui riwayat penambahan / penghapusan kunci yang berbeda. Jika itu masalahnya, maka pertimbangkan untuk menyortir d.items() seperti sarannya.


131
2018-02-24 07:51



Satu-liner lainnya berdasarkan daftar pemahaman:

>>> 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}]

Di sini karena kita dapat menggunakan dict Sebagai perbandingan, kami hanya menyimpan unsur-unsur yang tidak ada dalam daftar awal lainnya (pengertian ini hanya dapat diakses melalui indeks n, maka penggunaan enumerate).


28
2018-02-24 09:05



Terkadang loop gaya lama masih berguna. Kode ini sedikit lebih panjang dari jcollado, tetapi sangat mudah dibaca:

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

11
2018-02-24 08:10



Jawaban lain tidak akan berfungsi jika Anda mengoperasikan kamus bertingkat seperti objek JSON deserialized. Untuk kasus ini Anda bisa menggunakan:

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



Jika Anda ingin mempertahankan Order, maka Anda bisa melakukannya

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

Jika urutannya tidak penting, maka Anda bisa melakukannya

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

7
2018-04-29 07:52



Anda dapat menggunakan satu set, tetapi Anda perlu mengubah dikt menjadi tipe yang dapat di-hash.

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)

Unik sekarang sama

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

Untuk mendapatkan kembali perintah:

[dict(x) for x in unique]

0
2018-02-24 08:03



Bukan jawaban universal, tetapi jika daftar Anda kebetulan disortir oleh beberapa kunci, seperti ini:

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}]

maka solusinya sesederhana:

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

Hasil:

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

Bekerja dengan kamus bertingkat dan (jelas) menjaga ketertiban.


0
2018-06-14 07:49



Jika menggunakan paket pihak ketiga akan baik-baik saja maka Anda bisa menggunakannya 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}]

Ini mempertahankan urutan daftar asli dan ut juga dapat menangani item yang tidak dapat dirapikan seperti kamus dengan mundur kembali pada algoritma yang lebih lambat (O(n*m) dimana n adalah elemen dalam daftar asli dan m elemen unik dalam daftar asli, bukan O(n)). Dalam hal kedua kunci dan nilai-nilai yang dapat Anda gunakan, Anda dapat menggunakan key argumen dari fungsi tersebut untuk membuat item yang dapat di-hash untuk "uji keunikan" (agar berfungsi dalam O(n)).

Dalam kasus kamus (yang membandingkan independen pesanan) Anda perlu memetakannya ke struktur data lain yang membandingkan seperti itu, misalnya frozenset:

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

Perhatikan bahwa Anda tidak seharusnya menggunakan yang sederhana tuplependekatan (tanpa pemilahan) karena kamus yang sama tidak selalu memiliki urutan yang sama (bahkan dengan Python 3.7 di mana urutan penyisipan - bukan pesanan mutlak - dijamin):

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

Dan bahkan penyortiran tupel mungkin tidak berfungsi jika kunci tidak dapat diurutkan:

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

Benchmark

Saya pikir mungkin berguna untuk melihat bagaimana kinerja pendekatan ini dibandingkan, jadi saya melakukan patokan kecil. Grafik patokan adalah waktu vs ukuran daftar berdasarkan daftar yang tidak berisi duplikat (yang dipilih secara sewenang-wenang, waktu proses tidak berubah secara signifikan jika saya menambahkan beberapa atau banyak duplikat). Ini adalah plot log-log sehingga rentang lengkapnya tertutup.

Saat-saat mutlak:

enter image description here

Pengaturan waktu relatif terhadap pendekatan tercepat:

enter image description here

Pendekatan kedua dari thefourtheye tercepat di sini. Itu unique_everseen pendekatan dengan key fungsi berada di tempat kedua, namun itu adalah pendekatan tercepat yang menjaga ketertiban. Pendekatan lain dari jcollado dan thefourtheye hampir sama cepatnya. Pendekatan menggunakan unique_everseen tanpa kunci dan solusi dari Emmanuel dan Scorpil sangat lambat untuk daftar yang lebih panjang dan berperilaku lebih buruk O(n*n) dari pada O(n). stpks pendekatan dengan json tidak O(n*n) tetapi jauh lebih lambat daripada yang serupa O(n) pendekatan.

Kode untuk mereproduksi tolok ukur:

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)

Untuk kelengkapannya di sini adalah waktu untuk daftar yang hanya berisi duplikat:

# 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

Timing tidak berubah secara signifikan kecuali unique_everseen tanpa key fungsi, yang dalam hal ini adalah solusi tercepat. Namun itu hanya kasus terbaik (jadi tidak representatif) untuk fungsi tersebut dengan nilai yang tidak dapat diraba karena runtime bergantung pada jumlah nilai unik dalam daftar: O(n*m) yang dalam hal ini hanya 1 dan dengan demikian berjalan masuk O(n).


Disclaimer: Saya adalah penulis dari iteration_utilities.


0
2017-07-17 19:43