Hapus duplikat daftar di dalam 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}]

Coba ini:

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

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

dimana:

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

Sunting: Jika Anda ingin mempertahankan pemesanan, satu-liner di atas tidak akan berfungsi karena settidak 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 output:

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

Catatan: Seperti yang ditunjukkan oleh @alexis, mungkin terjadi dua kamus dengan kunci dan nilai yang sama, tidak menghasilkan tupel yang sama. Itu bisa terjadi jika mereka melalui riwayat kunci tambah / hapus yang berbeda. Jika itu yang menjadi masalah Anda, maka pertimbangkan untuk menyortir d.items()sesuai sarannya.

Satu baris lain 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 dictperbandingan, kita hanya menyimpan elemen-elemen yang tidak ada dalam daftar awal (gagasan ini hanya dapat diakses melalui indeks n, karenanya penggunaan enumerate).

Jawaban lain tidak akan berfungsi jika Anda beroperasi pada kamus bersarang seperti objek JSON deserialized. Untuk kasus ini, Anda dapat 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]

Jika menggunakan paket pihak ketiga tidak apa-apa maka Anda bisa menggunakan 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 menjaga urutan daftar asli dan ut juga dapat menangani barang-barang yang tidak dapat diakses seperti kamus dengan mundur pada algoritma yang lebih lambat (di O(n*m)mana nelemen dalam daftar asli dan melemen unik dalam daftar asli bukan O(n)). Jika kunci dan nilai hashable, Anda dapat menggunakan keyargumen fungsi tersebut untuk membuat item hashable untuk "uji keunikan" (sehingga berfungsi O(n)).

Dalam kasus kamus (yang membandingkan tanpa urutan) 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 boleh menggunakan tuplependekatan sederhana (tanpa pengurutan) karena kamus yang sama tidak harus memiliki urutan yang sama (bahkan dalam Python 3.7 di mana urutan penyisipan - bukan urutan absolut - dijamin):

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

Dan bahkan mengurutkan tuple 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'

Tolok ukur

Saya pikir mungkin berguna untuk melihat bagaimana kinerja pendekatan ini dibandingkan, jadi saya melakukan tolok ukur kecil. Grafik benchmark adalah waktu vs. ukuran daftar berdasarkan daftar yang tidak mengandung duplikat (yang dipilih secara sewenang-wenang, runtime tidak berubah secara signifikan jika saya menambahkan beberapa atau banyak duplikat). Ini adalah plot log-log sehingga jangkauan lengkapnya tercakup.

Waktu absolut:

Pengaturan waktu relatif terhadap pendekatan tercepat:

Pendekatan kedua dari mereka adalah yang tercepat di sini. The unique_everseenpendekatan dengan keyfungsi di tempat kedua, namun itu pendekatan tercepat yang diawetkan memesan. Pendekatan lain dari jcollado dan theouroureye hampir sama cepatnya. Pendekatan menggunakan unique_everseentanpa kunci dan solusi dari Emmanuel dan Scorpil sangat lambat untuk daftar lagi dan berperilaku jauh lebih buruk O(n*n)daripada O(n). Pendekatan stpk dengan jsontidak O(n*n)tetapi itu jauh lebih lambat daripada O(n)pendekatan serupa .

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

Pengaturan waktu tidak berubah secara signifikan kecuali unique_everseentanpa keyfungsi, yang dalam hal ini adalah solusi tercepat. Namun itu hanya kasus terbaik (jadi tidak representatif) untuk fungsi itu dengan nilai-nilai yang tidak dapat dicapai karena runtime tergantung pada jumlah nilai unik dalam daftar: O(n*m)yang dalam hal ini hanya 1 dan karenanya berjalan dalam O(n).

Penafian: Saya penulis iteration_utilities.

Kadang-kadang loop gaya lama masih bermanfaat. Kode ini sedikit lebih panjang dari kode 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])

Jika Anda ingin mempertahankan Order, maka Anda dapat 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 pesanan tidak masalah, maka Anda bisa melakukannya

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

Jika Anda menggunakan Panda dalam alur kerja Anda, satu opsi adalah untuk memberi makan daftar kamus langsung ke pd.DataFramekonstruktor. Kemudian gunakan drop_duplicatesdan to_dictmetode untuk hasil yang diperlukan.

import pandas as pd

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

d_unique = pd.DataFrame(d).drop_duplicates().to_dict('records')

print(d_unique)

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

Bukan jawaban universal , tetapi jika daftar Anda diurutkan berdasarkan 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 bersarang dan (jelas) menjaga ketertiban.

Anda dapat menggunakan satu set, tetapi Anda harus mengubah dicts menjadi tipe 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)

Unik sekarang sama

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

Untuk mendapatkan kembali dikte:

[dict(x) for x in unique]

Berikut ini adalah solusi satu baris cepat dengan pemahaman daftar bersarang ganda (berdasarkan solusi @Emmanuel).

Ini menggunakan kunci tunggal (misalnya, a) di setiap dikt sebagai kunci utama, daripada memeriksa apakah seluruh dikt cocok

[i for n, i in enumerate(list_of_dicts) if i.get(primary_key) not in [y.get(primary_key) for y in list_of_dicts[n + 1:]]]

Bukan itu yang diminta OP, tapi itu yang membawa saya ke utas ini, jadi saya pikir saya akan memposting solusi yang akhirnya saya dapatkan

Tidak terlalu pendek tapi mudah dibaca:

list_of_data = [{'a': 123}, {'b': 123}, {'a': 123}]

list_of_data_uniq = []
for data in list_of_data:
    if data not in list_of_data_uniq:
        list_of_data_uniq.append(data)

Sekarang, daftar list_of_data_uniqakan memiliki dikte unik.