Supprimer les dictées en double dans une liste en Python

Question

J'ai une liste de dicts, et je voudrais enlever les dicts avec des paires de clés et de valeurs identiques.

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

J'aimerais rendre ça : [{'a': 123}, {'b': 123}]

Un autre exemple :

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

J'aimerais rendre ça : [{'a': 123, 'b': 1234}, {'a': 3222, 'b': 1234}]

Answer 1

Essayez ç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. Comme les tuples peuvent être hachés, vous pouvez supprimer les doublons à l'aide de la fonction set (en utilisant un compréhension du jeu ici, une alternative plus ancienne en python serait set(tuple(d.items()) for d in l) ) et, après cela, recréer les dictionnaires à partir de tuples avec dict .

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

Edit : Si vous voulez préserver l'ordre, la phrase ci-dessus ne fonctionnera pas car set ne le fera pas. Cependant, avec quelques lignes de code, vous pouvez aussi 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}]

Note : Comme l'a fait remarquer @alexis, il se peut que deux dictionnaires ayant les mêmes clés et valeurs ne donnent pas le même tuple. Cela peut arriver s'ils passent par une histoire différente d'ajout/suppression de clés. Si c'est le cas pour votre problème, alors envisagez de trier d.items() comme il le suggère.

Answer 2

Un autre one-liner basé sur les compréhensions de listes :

>>> 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, puisque nous pouvons utiliser dict on ne garde que les éléments qui ne sont pas dans le reste de la liste initiale (cette notion n'est accessible que par l'indice n d'où l'utilisation de enumerate ).

Answer 3

Si l'utilisation d'un paquet tiers est acceptable, vous pouvez alors 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 peut également traiter des éléments non hachables comme les dictionnaires en recourant à un algorithme plus lent ( O(n*m) donde n sont les éléments de la liste originale et m les éléments uniques de la liste originale au lieu de O(n) ). Si les clés et les valeurs sont toutes deux hachables, vous pouvez utiliser la fonction key de cette fonction afin de créer des éléments hachables pour le "test d'unicité" (de manière à ce qu'il fonctionne en mode O(n) ).

Dans le cas d'un dictionnaire (qui compare indépendamment de l'ordre), vous devez le faire correspondre à une autre structure de données qui compare de la même manière, par exemple frozenset :

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

Notez que vous ne devriez pas utiliser un simple tuple (sans tri) car des dictionnaires égaux n'ont pas forcément le même ordre (même dans Python 3.7 où ordre d'insertion - pas 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 sont pas triables :

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

Point de repère

J'ai pensé qu'il pourrait être utile de voir comment les performances de ces approches se comparent, donc j'ai fait un petit benchmark. Les graphiques de référence représentent le temps en fonction de la taille de la liste, sur la base d'une liste ne contenant aucun doublon (choisie arbitrairement, le temps d'exécution ne change pas de manière significative si j'ajoute quelques ou beaucoup de doublons). Il s'agit d'un graphique log-log, ce qui permet de couvrir toute la gamme.

Les temps absolus :

Les temps relatifs à l'approche la plus rapide :

La deuxième approche de thefourtheye est le plus rapide ici. Le site unique_everseen avec l'approche key La fonction est en deuxième position, mais c'est l'approche la plus rapide qui préserve l'ordre. Les autres approches de jcollado y thefourtheye sont presque aussi rapides. L'approche utilisant unique_everseen sans clé et les solutions de Emmanuel y Scorpil sont très lents pour les longues listes et se comportent beaucoup plus mal. O(n*n) au lieu de O(n) . stpk avec l'approche de json n'est pas O(n*n) mais il est beaucoup plus lent que le similaire O(n) approches.

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)

Pour être complet, voici le timing pour une liste ne contenant que 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)}

Les horaires ne changent pas de façon significative sauf pour unique_everseen sans key 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 hachables car son temps d'exécution dépend de la quantité de valeurs uniques dans la liste : O(n*m) qui, dans ce cas, n'est que de 1, et qui s'exécute donc en O(n) .

---

Disclaimer : Je suis l'auteur de iteration_utilities .

Answer 4

Les autres réponses ne fonctionneraient pas si vous opérez sur des dictionnaires imbriqués tels que des objets JSON désérialisés. Dans ce cas, vous pourriez 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]

Answer 5

Parfois, les boucles à l'ancienne sont encore 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])