Usuń zduplikowany dykt na liście w Pythonie

Mam listę dykt i chciałbym usunąć dykty z identycznymi parami klucza i wartości.

W przypadku tej listy: [{'a': 123}, {'b': 123}, {'a': 123}]

Chciałbym to zwrócić: [{'a': 123}, {'b': 123}]

Inny przykład:

W przypadku tej listy: [{'a': 123, 'b': 1234}, {'a': 3222, 'b': 1234}, {'a': 123, 'b': 1234}]

Chciałbym to zwrócić: [{'a': 123, 'b': 1234}, {'a': 3222, 'b': 1234}]

Spróbuj tego:

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

Strategia polega na przekonwertowaniu listy słowników na listę krotek, w której krotki zawierają pozycje ze słownika. Ponieważ krotki mogą być haszowane, możesz usunąć duplikaty za pomocą set(używając zestawu pojmowania tutaj, starsza alternatywa dla Pythona będzie set(tuple(d.items()) for d in l)), a następnie ponownie utwórz słowniki z krotek za pomocą dict.

gdzie:

• l to oryginalna lista
• d jest jednym ze słowników na liście
• t jest jedną z krotek utworzonych ze słownika

Edycja: Jeśli chcesz zachować kolejność, powyższa linijka nie zadziała, ponieważ settego nie zrobi. Jednak za pomocą kilku wierszy kodu możesz również to zrobić:

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

Przykładowe dane wyjściowe:

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

Uwaga: jak wskazał @alexis, może się zdarzyć, że dwa słowniki z tymi samymi kluczami i wartościami nie utworzą tej samej krotki. Może się to zdarzyć, jeśli przejdą przez inną historię dodawania / usuwania kluczy. Jeśli tak jest w przypadku Twojego problemu, rozważ sortowanie d.items()zgodnie z sugestią.

Kolejna jedna linijka oparta na zrozumieniu list:

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

Tutaj, ponieważ możemy użyć dictporównania, zachowujemy tylko te elementy, których nie ma w pozostałej części początkowej listy (to pojęcie jest dostępne tylko przez indeks n, stąd użycie enumerate).

Inne odpowiedzi nie zadziałają, jeśli pracujesz na zagnieżdżonych słownikach, takich jak zdeserializowane obiekty JSON. W tym przypadku możesz użyć:

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]

Jeśli użycie pakietu innej firmy byłoby w porządku, możesz użyć 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}]

Zachowuje kolejność oryginalnej listy i ut może również obsługiwać elementy, których nie można zhasować, takie jak słowniki, wycofując się na wolniejszym algorytmie ( O(n*m)gdzie zamiast elementów oryginalnej listy nznajdują się elementy oryginalnej listy i munikalne elementy na oryginalnej liście O(n)). W przypadku, gdy zarówno klucze, jak i wartości są hashowalne, możesz użyć keyargumentu tej funkcji do utworzenia pozycji hashable dla „testu unikalności” (tak, aby działał O(n)).

W przypadku słownika (który porównuje niezależnie od kolejności) musisz odwzorować go na inną strukturę danych, która porównuje w ten sposób, na przykład frozenset:

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

Zwróć uwagę, że nie powinieneś używać prostego tuplepodejścia (bez sortowania), ponieważ równe słowniki niekoniecznie mają tę samą kolejność (nawet w Pythonie 3.7, gdzie kolejność wstawiania - a nie kolejność bezwzględna - jest gwarantowana):

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

A nawet sortowanie krotki może nie działać, jeśli klucze nie są sortowalne:

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

Reper

Pomyślałem, że warto zobaczyć, jak wypada porównanie tych podejść, więc zrobiłem mały test porównawczy. Wykresy porównawcze przedstawiają czas w funkcji rozmiaru listy na podstawie listy nie zawierającej duplikatów (która została wybrana arbitralnie, czas wykonania nie zmienia się znacząco, jeśli dodam kilka lub wiele duplikatów). Jest to wykres log-log, więc obejmuje cały zakres.

Absolutne czasy:

Czasy w stosunku do najszybszego podejścia:

Drugie podejście od czwórki jest tutaj najszybsze. unique_everseenPodejście z keyfunkcji znajduje się na drugim miejscu, jednak jest to najszybszy podejście, że przetwory zamówić. Inne podejścia z jcollado i the fourye są prawie tak samo szybkie. Podejście unique_everseenbez klucza i rozwiązania Emmanuel i Scorpil są bardzo powolne w przypadku dłuższych list i O(n*n)zamiast tego zachowują się znacznie gorzej O(n). Podejście stpk z jsonnie jest, O(n*n)ale jest znacznie wolniejsze niż podobne O(n)podejścia.

Kod do odtworzenia wzorców:

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)

Aby uzyskać kompletność, oto czas dla listy zawierającej tylko duplikaty:

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

Czasy nie zmieniają się znacząco, z wyjątkiem unique_everseenbraku keyfunkcji, co w tym przypadku jest najszybszym rozwiązaniem. Jest to jednak najlepszy przypadek (a więc niereprezentatywny) dla tej funkcji z wartościami, których nie można zhasować, ponieważ jej czas wykonywania zależy od liczby unikatowych wartości na liście: O(n*m)w tym przypadku jest to tylko 1, a zatem działa O(n).

Zastrzeżenie: jestem autorem iteration_utilities.

Czasami pętle w starym stylu są nadal przydatne. Ten kod jest trochę dłuższy niż jcollado, ale bardzo łatwy do odczytania:

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

Jeśli chcesz zachować Zakon, możesz to zrobić

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

Jeśli kolejność nie ma znaczenia, możesz to zrobić

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

Jeśli używasz Pand w swoim przepływie pracy, jedną z opcji jest przesłanie listy słowników bezpośrednio do pd.DataFramekonstruktora. Następnie użyj metod drop_duplicatesi to_dict, aby uzyskać wymagany wynik.

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

Nie jest to uniwersalna odpowiedź , ale jeśli zdarzy się, że twoja lista jest posortowana według jakiegoś klucza, na przykład:

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

to rozwiązanie jest tak proste, jak:

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

Wynik:

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

Działa z zagnieżdżonymi słownikami i (oczywiście) zachowuje porządek.

Możesz użyć zestawu, ale musisz zmienić dykty w typ haszujący.

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)

Wyjątkowy teraz równa się

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

Aby odzyskać dyktowanie:

[dict(x) for x in unique]

Oto szybkie, jednowierszowe rozwiązanie z podwójnie zagnieżdżonym zrozumieniem list (w oparciu o rozwiązanie @Emmanuel).

To używa pojedynczego klucza (na przykład a) w każdym dyktacie jako klucza podstawowego, zamiast sprawdzać, czy cały dykt jest zgodny

[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:]]]

Nie o to prosił OP, ale to właśnie doprowadziło mnie do tego wątku, więc pomyślałem, że opublikuję rozwiązanie, z którym skończyłem

Nie tak krótkie, ale łatwe do odczytania:

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)

Teraz lista list_of_data_uniqbędzie miała unikalne dykty.