Supprimer le dict en double dans la liste en Python

153

J'ai une liste de dictés et j'aimerais supprimer les dictionnaires avec des paires clé et valeur identiques.

Pour cette liste: [{'a': 123}, {'b': 123}, {'a': 123}]

Je voudrais rendre cela: [{'a': 123}, {'b': 123}]

Un autre exemple:

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

Je voudrais rendre cela: [{'a': 123, 'b': 1234}, {'a': 3222, 'b': 1234}]

Brenden
la source
Pouvez-vous nous en dire plus sur le problème réel que vous essayez de résoudre? Cela semble être un problème étrange à avoir.
gfortune
Je combine quelques listes de dictionnaires et il y a des doublons. Je dois donc supprimer ces doublons.
Brenden
J'ai trouvé une solution dans stackoverflow.com/questions/480214/… dans une réponse sans l'utilisation deset()
Sebastian Wagner

Réponses:

242

Essaye ça:

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

La stratégie consiste à convertir la liste des dictionnaires en une liste de tuples où les tuples contiennent les éléments du dictionnaire. Puisque les tuples peuvent être hachés, vous pouvez supprimer les doublons en utilisant set(en utilisant une compréhension d'ensemble ici, une alternative plus ancienne à python serait set(tuple(d.items()) for d in l)) et, après cela, recréer les dictionnaires à partir de tuples avecdict .

où:

  • l est la liste originale
  • d est l'un des dictionnaires de la liste
  • t est l'un des tuples créés à partir d'un dictionnaire

Modifier: Si vous souhaitez conserver la commande, le one-liner ci-dessus ne fonctionnera pas car setne le fera pas. Cependant, avec quelques lignes de code, vous pouvez également le faire:

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

Exemple de sortie:

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

Remarque: comme indiqué par @alexis, il peut arriver que deux dictionnaires avec les mêmes clés et valeurs ne donnent pas le même tuple. Cela peut arriver s'ils passent par un autre historique d'ajout / suppression de clés. Si tel est le cas pour votre problème, envisagez de trier d.items()comme il le suggère.

jcollado
la source
35
Belle solution mais elle a un bug: il d.items()n'est pas garanti de renvoyer les éléments dans un ordre particulier. Vous devez faire tuple(sorted(d.items()))pour vous assurer que vous n'obtenez pas différents tuples pour les mêmes paires clé-valeur.
alexis
@alexis J'ai fait quelques tests et vous avez effectivement raison. Si beaucoup de clés sont ajoutées entre les deux et supprimées plus tard, cela pourrait être le cas. Merci beaucoup pour votre commentaire.
jcollado
Cool. J'ai ajouté le correctif à votre réponse pour le bénéfice des futurs lecteurs qui pourraient ne pas lire toute la conversation.
alexis
2
Notez que cela ne fonctionnera pas si vous chargez cette liste de dictionnaires à partir d'un jsonmodule comme je l'ai fait
Dhruv Ghulati
2
C'est une solution valable dans ce cas, mais ne fonctionnera pas en cas de dictionnaires imbriqués
Lorenzo Belli
51

Un autre one-liner basé sur la compréhension de liste:

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

Ici comme on peut utiliser la dictcomparaison, on ne garde que les éléments qui ne sont pas dans le reste de la liste initiale (cette notion n'est accessible que via l'index n, d'où l'utilisation de enumerate).

Emmanuel
la source
2
Cela fonctionne également pour une liste de dictionnaires qui se composent de listes par rapport à la première réponse
gbozee
1
cela fonctionne également lorsque vous pouvez avoir un type nonchalable comme valeur dans vos dictionnaires, contrairement à la première réponse.
Steve Rossiter
1
ici, le but est de supprimer les valeurs en double, pas la clé, voir le code de cette réponse
Jamil Noyda
C'est un code très inefficace. if i not in d[n + 1:]itère sur toute la liste des dictionnaires (à partir de nmais cela ne fait que diviser par deux le nombre total d'opérations) et vous effectuez cette vérification pour chaque élément de votre dictionnaire, donc ce code est une complexité temporelle O (n ^ 2)
Boris
ne fonctionne pas pour les dictionnaires avec des dictionnaires comme valeurs
Roko Mijic
22

D'autres réponses ne fonctionneraient pas si vous utilisez des dictionnaires imbriqués tels que des objets JSON désérialisés. Pour ce cas, vous pouvez utiliser:

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]
stpk
la source
1
Génial! l'astuce est que l'objet dict ne peut pas être directement ajouté à un ensemble, il doit être converti en objet json par dump ().
Reihan_amn
19

Si l'utilisation d'un package tiers vous convient, vous pouvez utiliser 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}]

Il préserve l'ordre de la liste d'origine et ut peut également gérer les éléments non phasables comme les dictionnaires en recourant à un algorithme plus lent ( O(n*m)nsont les éléments de la liste d'origine et mles éléments uniques de la liste d'origine au lieu de O(n)). Dans le cas où les clés et les valeurs sont hachables, vous pouvez utiliser l' keyargument de cette fonction pour créer des éléments hachables pour le "test d'unicité" (afin qu'il fonctionne O(n)).

Dans le cas d'un dictionnaire (qui compare indépendamment de l'ordre), vous devez le mapper à une autre structure de données qui compare comme ça, par exemple frozenset:

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

Notez que vous ne devez pas utiliser une tupleapproche simple (sans tri) car les dictionnaires égaux n'ont pas nécessairement le même ordre (même en Python 3.7 où l' ordre d'insertion - et non l'ordre absolu - est garanti):

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

Et même le tri du tuple peut ne pas fonctionner si les clés ne peuvent pas être triées:

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

Référence

J'ai pensé qu'il pourrait être utile de voir comment les performances de ces approches se comparent, alors j'ai fait un petit benchmark. Les graphiques de référence sont le temps par rapport à la taille de la liste sur la base d'une liste ne contenant aucun doublon (qui a été choisi arbitrairement, le temps d'exécution ne change pas de manière significative si j'ajoute certains ou beaucoup de doublons). C'est un tracé log-log donc la gamme complète est couverte.

Les temps absolus:

entrez la description de l'image ici

Les horaires relatifs à l'approche la plus rapide:

entrez la description de l'image ici

La deuxième approche de thefourtheye est la plus rapide ici. L' unique_everseenapproche avec la keyfonction est à la deuxième place, mais c'est l'approche la plus rapide qui préserve l'ordre. Les autres approches de jcollado et thefourtheye sont presque aussi rapides. L'approche utilisant unique_everseensans clé et les solutions d' Emmanuel et Scorpil sont très lentes pour les listes plus longues et se comportent bien plus mal O(n*n)au lieu de O(n). L' approche de stpk avec jsonn'est pas, O(n*n)mais elle est beaucoup plus lente que les O(n)approches similaires .

Le code pour reproduire les benchmarks:

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)

Par souci d'exhaustivité, voici le timing d'une liste contenant uniquement des doublons:

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

entrez la description de l'image ici

Les horaires ne changent pas de manière significative, sauf unique_everseensans keyfonction, ce qui dans ce cas est la solution la plus rapide. Cependant, ce n'est que le meilleur cas (donc non représentatif) pour cette fonction avec des valeurs non phasables car son exécution dépend de la quantité de valeurs uniques dans la liste: O(n*m)qui dans ce cas est juste 1 et donc elle s'exécute O(n).


Avertissement: je suis l'auteur de iteration_utilities.

MSeifert
la source
15

Parfois, les boucles à l'ancienne sont toujours utiles. Ce code est un peu plus long que celui de jcollado, mais très facile à lire:

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])
Scorpil
la source
L' 0entrée range(0, len(a))n'est pas nécessaire.
Juan Antonio
12

Si vous souhaitez conserver la commande, vous pouvez faire

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

Si l'ordre n'a pas d'importance, vous pouvez le faire

print {frozenset(item.items()):item for item in data}.values()
# [{'a': 3222, 'b': 1234}, {'a': 123, 'b': 1234}]
thefourtheye
la source
Remarque: en python 3, votre deuxième approche donne une dict_valuessortie non sérialisable au lieu d'une liste. Vous devez à nouveau lancer le tout dans une liste. list(frozen.....)
saran3h
12

Si vous utilisez Pandas dans votre flux de travail, une option consiste à fournir une liste de dictionnaires directement au pd.DataFrameconstructeur. Ensuite, utilisez drop_duplicateset to_dictméthodes pour obtenir le résultat souhaité.

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}]
jpp
la source
3

Ce n'est pas une réponse universelle , mais si votre liste est triée par une clé, comme ceci:

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

alors la solution est aussi simple que:

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

Résultat:

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

Fonctionne avec des dictionnaires imbriqués et préserve (évidemment) l'ordre.

Highstaker
la source
1

Vous pouvez utiliser un ensemble, mais vous devez transformer les dictionnaires en un type hachable.

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)

Unique est maintenant égal

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

Pour récupérer les dicts:

[dict(x) for x in unique]
Matimus
la source
L'ordre de d.iteritems()n'est pas garanti - vous pouvez donc vous retrouver avec des «doublons» dans unique.
danodonovan
-1

Voici une solution rapide en une ligne avec une compréhension de liste doublement imbriquée (basée sur la solution de @Emmanuel).

Cela utilise une seule clé (par exemple, a) dans chaque dict comme clé primaire, plutôt que de vérifier si tout le dict correspond

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

Ce n'est pas ce que OP a demandé, mais c'est ce qui m'a amené à ce fil, alors j'ai pensé que je publierais la solution avec laquelle je me suis retrouvé

Alec
la source
-1

Pas si court mais facile à lire:

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)

Maintenant, la liste list_of_data_uniqaura des dictionnaires uniques.

utilisateur1723157
la source