Discussion :

[gingko41]

Bonjour à Tous & Toutes
J'ai une énorme liste de dictionnaire, avec des doublons.
Je n'arrive pas à supprimer ces doublons avec la technique de créér une nouvelle liste et d'ajouter les éléments 1 à 1. Cela ne renvoie pas d'erreurs mais cela tourne sans donner de résultats.
Connaissez-vous une méthode efficace?
Merci

[tyrtamos]

Bonjour,

Il est difficile de proposer quelque chose en en connaissant aussi peu. Donne un petit exemple (même avec des données bidons si c'est confidentiel) de tes données avec les doublons que tu cherches à éliminer. Et montre le code que tu as fait et qui ne marche pas.

[lg_53]

Oui il faut montrer le code, et un exemple de données même petite (et tu nous en donnes la taille après dans ton message). Comme ca ca nous permet déjà de voir si c'est un souci de code ou juste un problème d'optimisation de celui ci, et on peut avoir une base sur laquelle réfléchir de notre côté.

[gingko41]

Bonjour,

merci pour vos réponses, la liste est stockée dans un fichier pickle qui fait 38 Mo et comporte 97000 éléments.
Sa structure ressemble à ça : 3 clés pour le dixtionnaire mais un set de taille indéfininie pour chaque clé:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
[{"k1": {"truc","bidule"}, "k2" : {"machin","blaba"}, "k3" : {'xx',"yyy","zz"}},
{"k1": {"truc2","bidule2"}, "k2" : {"machin2","blaba2"}, "k3" : {'xx2',"yyy2","zz2"}},
{"k1": {"truc","bidule"}, "k2" : {"machin","blaba"}, "k3" : {'xx',"yyy","zz"}},   # doublon à supprimer
]

le code testé :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
new_d = []
for element in old_d:
    if element not in new_d:
        new_d.append(element)

La liste est trop grande donc ça tourne, ça tourne, mais pas de résultat

Merci pour vos idées !

[papajoker]

bonjour

pourquoi ne pas tester ce code que tu nous donnes ???

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
elements = [
    {"k1": {"truc","bidule"}, "k2" : {"machin","blaba"}, "k3" : {'xx',"yyy","zz"}},
    {"k1": {"truc2","bidule2"}, "k2" : {"machin2","blaba2"}, "k3" : {'xx2',"yyy2","zz2"}},
    {"k1": {"truc","bidule"}, "k2" : {"machin","blaba"}, "k3" : {'xx',"yyy","zz"}},   # doublon à supprimer
]
print(elements)
nouveaux = []
for element in elements:
    print("origin", element)
    if element not in nouveaux:
        nouveaux.append(element)
print("")
for element in nouveaux:
    print("nouveau", element)

[gingko41]

j'ai testé hier mais rien de sortait comme résultat donc je ne sais pas combien de temps (d'heures ??) cela va prendre, c'est pour ça que je me suis dit qu'il devait y avoir des méthodes plus efficaces

[wiztricks]

La liste est trop grande donc ça tourne, ça tourne, mais pas de résultat

Ben ouais mais un code qui fonctionne bien pour des listes à quelques items ne sont pas adaptés à toutes tailles... ça dépend de leur complexité algorithmique.

Comme comparer des dictionnaires se réduit à '==' (pas de relation d'ordre...), il va peut être falloir trouver une structure de données intermédiaire pour y arriver... mais le forum algo. est là pour çà.

- W

[papajoker]

Tu peux aussi essayer un dictionnaire ? on passe en index la ligne transformée en chaine (possible d'utiliser autre chose que str()..., c'est l'idée)
cela évite le if element not in, donc on ne parcourt pas une liste dans une boucle

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
defaut = [
    {"k1": {"truc","bidule"}, "k2" : {"machin","blaba"}, "k3" : {'xx',"yyy","zz"}},
    {"k1": {"truc2","bidule2"}, "k2" : {"machin2","blaba2"}, "k3" : {'xx2',"yyy2","zz2"}},
    {"k1": {"truc","bidule"}, "k2" : {"machin","blaba"}, "k3" : {'xx',"yyy","zz"}},   # doublon à supprimer
]
elements = []
for i in range(33000):
    elements.extend(default)
print(len(elements))
 
nouveaux = {}
for element in elements:
    nouveaux[str(element)] = element
 
for element in nouveaux.values():
    print("nouveau", element)

[Sve@r]

Bonjour

J'ai une énorme liste de dictionnaire, avec des doublons.

Déjà il faudrait que tu précises ce que tu entends par "doublon" (surtout entre deux dictionnaires). Ok tu as donné un exemple avec le 3° marqué "doublon" mais un exemple ce n'est pas fait pour remplacer une définition mais pour l'illustrer. Donc même avec exemple, la définition reste impérative.
D'après cet exemple, un doublon c'est "clefs+valeurs identiques" c'est ça ???

Ensuite, tu ne dis pas si tu veux garder l'ordre final identique (sans les doublons) à l'ordre initial, parce que cela a une influence sur l'algo. Si par exemple c'est inutile de garder l'ordre, alors ça devient plus facile

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
pour chaque élément pris dans la liste initiale triée, faire
    si élément identique à élément mémorisé, alors on continue la boucle (on saute la suite du code)
    mémorisation élément en cours
    ajout élément en cours dans la nouvelle liste
fin faire

Ce qui donne en Python

Code python :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
base=[
	{"k1": {"truc","bidule"}, "k2" : {"machin","blaba"}, "k3" : {'xx',"yyy","zz"}},
	{"k1": {"truc2","bidule2"}, "k2" : {"machin2","blaba2"}, "k3" : {'xx2',"yyy2","zz2"}},
	{"k4": {"truc2","bidule2"}, "k2" : {"machin2","blaba2"}, "k3" : {'xx2',"yyy2","zz2"}},
	{"k1": {"truc","bidule"}, "k2" : {"machin","blaba"}, "k3" : {'xx',"yyy","zz"}},   # doublon à supprimer
]
 
res=[]
mem=None
for item in sorted(base, key=lambda x: tuple(x.keys()) + tuple(x for v in x.values() for x in v)):
	if item == mem: continue
	mem=item
	res.append(item)
 
for item in res: print(item)

(ok je l'avoue, j'en ai un peu chié pour trouver le critère de tri, critère que j'ai imaginé finalement comme étant la liste des clefs suivi de la liste de tous les éléments pris à partir des valeurs)

[gingko41]

merci pour vos réponses,

oui je n'avais pas précisé mais en effet l'ordre n'était pas important dans la liste.
J'ai utilisé la méthode de sve@r et j'ai bien mon résultat.

Encore merci à tous et bon we !

[Invité]

En version one-line :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
toto = [{"k1": {"truc","bidule"}, "k2" : {"machin","blaba"}, "k3" : {'xx',"yyy","zz"}},
{"k1": {"truc2","bidule2"}, "k2" : {"machin2","blaba2"}, "k3" : {'xx2',"yyy2","zz2"}},
{"k1": {"truc","bidule"}, "k2" : {"machin","blaba"}, "k3" : {'xx',"yyy","zz"}},   # doublon à supprimer
]
import ast
list(ast.literal_eval(dico) for dico in set([str(dico) for dico in toto]))

PS : Surement pas performant...

[Sve@r]

J'ai mieux réfléchi à ma clef de tri. Je pense que concaténer les clefs puis les valeurs c'est pas super safe (ça donne k1 : {v1}, k2 {v2} identique à k1 : {}, k2 : {v1, v2} ou à k1 : {v1, ,v2}, k2 : {})
Je l'ai donc réécrit ainsi: k1 : {v11, v12}, k2 : {v21, v22} donne (lors du tri) (k1, (v11, v12), k2, (v21, v22)).

Code python :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
for item in sorted(base, key=lambda d: tuple((x[0], tuple(x[1])) for x in d.items())):
	if item == mem: continue
	mem=item
	res.append(item)

(et en plus ça fait moins de manip dans l'expression)

Et question performance de la solution one-line, transformer le dico en string pour ensuite le remettre en dico effectivement ça sent pas super bon. Ceci dit, ma méthode qui trie la liste initiale pour regrouper les éléments identiques c'est pas non plus optimum (le tri a un coût) mais de toute façon la complexité est là donc faut choisir: soit on la reporte sur le tri et ensuite le traitement c'est peanut, soit on la reporte dans le traitement. J'ai choisi le tri, présumant que les fonctions natives de Python feraient mieux qu'un algo qui regarderait à chaque itération si l'élément est/n'est pas déjà présent.

[Invité]

Ta façon de faire est bien plus rapide 3 µsec contre 47 avec la mienne.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
import ast, time
 
toto = [{"k1": {"truc","bidule"}, "k2" : {"machin","blaba"}, "k3" : {'xx',"yyy","zz"}},
{"k1": {"truc2","bidule2"}, "k2" : {"machin2","blaba2"}, "k3" : {'xx2',"yyy2","zz2"}},
{"k1": {"truc","bidule"}, "k2" : {"machin","blaba"}, "k3" : {'xx',"yyy","zz"}},   # doublon à supprimer
]
 
def test1():
 
    st = time.time()
    list(ast.literal_eval(dico) for dico in set([str(dico) for dico in toto]))
    return time.time()-st
 
def test2():
 
    st = time.time()
    mem = None
    res = []
    for item in sorted(toto, key=lambda d: tuple((x[0], tuple(x[1])) for x in d.items())):
        if item == mem: continue
        mem=item
        res.append(item)
    return time.time()-st
 
 
moy1 = int((sum([test1() for _ in range(100000)])/100000)*10**6)
moy2 = int((sum([test2() for _ in range(100000)])/100000)*10**6)
 
print(moy1, moy2)

[Sve@r]

Ta façon de faire est bien plus rapide 3 µsec contre 47 avec la mienne.

Déjà la ligne list(... for dico in set([str(dico) for dico in toto])) n'a pas besoin de convertir l'expression en liste avant de passer cette liste à set(). set() accepte parfaitement une expression en paramètre (dit en plus court: les crochets sont inutiles) => list(... for dico in set(str(dico) for dico in toto).
Ensuite tu peux remplacer ça par map(), qui est plus rapide quand il n'y a pas de lambda dans l'expression => list(... for dico in set(map(str, data))).
(j'adore le map, je le mets chaque fois que je le peux )

Ceci dit, ton idée de passer par un ensemble est à réfléchir. Déjà effectivement on évite le tri. Après est-ce que générer un ensemble est vraiment plus avantageux (chaque "add()" fait un check avant d'ajouter donc ça ressemble à l'idée initiale du PO sauf que comme c'est du natif Python c'est peut-être plus rapide)...

Mais ok, admettons que l'ensemble soit une bonne idée. Juste qu'il faut éviter de foutre ça en string pour retraduire la string en dico (trop hasardeux comme façon de faire que de s'appuyer sur une représentation textuelle d'un truc pour recréer le truc depuis cette représentation). Je comprends ton souci (je l'ai eu aussi): un dico n'est pas hashable (donc pas "setable") donc pour l'ensemble faut pas prendre un dico mais un truc "hashable" représentant le dico. Toi tu as choisi la string, moi je me dis que le tuple pourrait être une solution...

Donc j'ai fait un test qui commence par générer des datas au pif (sans doublon, je m'en assure à la génération !!!), puis qui duplique au pif certaines datas, et enfin qui passe le résultat par ma méthode et la tienne, méthodes qui doivent donner au final un résultat de taille identique à la data générée au départ (data générée avant duplication).

Et là c'est la caca, c'est la cata, c'est la catastrophe. Car sur une très grosse liste, aussi bien ta méthode que la mienne ne donnent pas le bon résultat. On a des résultats tous deux identiques, mais pas identiques à la liste de départ (qui est garantie sans doublons)

Voici mon test

Code python :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#!/usr/bin/env python3
# coding: utf-8
 
import random
import ast
 
base=("truc", "bidule", "machin", "blabla", "xx", "yy", "zz")
keys=("k1", "k2", "k3")
 
# Création des datas (ensemble de tuples)
sz_o=100_000
data=set()
while len(data) != sz_o:
	data.add(
		tuple(
			(k, tuple(random.sample(base, k=random.randint(2, len(base)))))
			for k in random.sample(keys, k=random.randint(2, len(keys)))
		)
	)
# while
 
# On transforme l'ensemble de tuples en liste de dict
data=list(dict((x[0], set(x[1])) for x in d) for d in data)
#for d in data: print(d, type(d))
#exit(0)
 
# Duplication des datas
for d in list(data):
	# Duplication n fois
	for i in range(10):
		# Chaque "i" donnera 1/3 chances de dupliquer la data
		if random.random() <= 1/3: data.append(d)
	# for
# for
sz_d=len(data)
print("taille data: sans duplication: %d, avec duplication: %d" % (sz_o, sz_d))
 
def svear(data):	
	# Conversion liste de dict en ensemble de tuples
	#tmp=set()
	#for d in data:
		#tmp.add(tuple((x[0], tuple(x[1])) for x in d.items()))
 
	# Conversion ensemble de tuples en liste de dict
	#res=list()
	#for t in tmp:
		#res.append(dict((x[0], set(x[1])) for x in t))
	#return res
 
	# One-line (oui, je sais, une fois que ceci est écrit, plus jamais tu peux le relire ou le modifier...)
	return list(
		dict(
			(x[0], set(x[1])) for x in r)
			for r in set((tuple((x[0], tuple(x[1])) for x in d.items())) for d in data)
		)
# svear()
 
def narvalo(data):
	return list(ast.literal_eval(dico) for dico in set(map(str, data)))
 
s=svear(data)
n=narvalo(data)
print("taille svear: %d, taille narvalo: %d" % (len(s), len(n)))
assert sz_o == len(s) == len(n)

Et c'est là que le truc part en couilles. Ok on est d'accord, aussi bien ta méthode que la mienne donne le même résultat. Mais ce résultat ne correspond pas à la liste initiale (celle créée sans duplication) alors que ça devrait être le cas. Généralement j'obtiens 76145 éléments là où je devrais en retrouver 100000...

Après imaginons que ce soit (on ne sait comment) normal, on peut alors tester les vitesses des deux méthodes. Mais faisons ça bien, avec timeit qui est fait pour ça. Déjà on part sur une taille de départ à 1000 (et non plus 100000 car là ça explose les chronos) et on rajoute ceci en fin de code...

Code python :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# Les fonctions à tester
import timeit
from functools import partial
fct={
	"svear" : svear,
	"narvalo" : narvalo,
}
 
# Le nombre de répétitions (les moyennes se feront sur cette valeur)
repeat=20
 
# Appel des fonctions dans un ordre aléatoire et affichage du chrono
print("start=%d, repeat=%d" % (len(data), repeat))
for (k, v) in random.sample(fct.items(), len(fct)):
	t=timeit.Timer(partial(v, data)).repeat(repeat=repeat, number=100)
	print("%s: min=%f, max=%f, avg=%f" % (k, min(t), max(t), sum(t)/len(t)))
# for

Et au résultat

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
taille data: sans duplication: 1000, avec duplication: 4309
start=4309, repeat=20
narvalo: min=3.030894, max=3.272290, avg=3.099943
svear: min=0.538720, max=0.599688, avg=0.558669

Passer par une string n'est vraiment pas une bonne idée (remarque ça se comprend, le ast.litteral_eval() il faut qu'il se sorte les doigts pour te parser la chaine...)

[wiztricks]

Salut,

Je l'ai donc réécrit ainsi: k1 : {v11, v12}, k2 : {v21, v22} donne (lors du tri) (k1, (v11, v12), k2, (v21, v22))

Il serait moins faux de fabriquer le tuple (k_i, v_i) ou v_i sera le tuple trié du set correspondant. Puis on trie sur les (k_i, v_i).

Maintenant, si on reformule, on a 3 colonnes k1, k2, k3... chaque ligne étant composé de 3 set de chaînes de caractères: s1, s2, s3.
Les dictionnaires et les set ne sont pas ordonnés - les dictionnaires préservent l'ordre d'insertion mais on ne sait pas s'ils ont été "bien" construits -.

Normalement si on transforme chaque s_i en tuple trié t_i, le tuple de tuples t1, t2, t3 suffit à détecter les doublons et est ordonné alphabétiquement.

Codé çà donne:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
base=[
	{"k1": {"truc","bidule"}, "k2" : {"machin","blaba"}, "k3" : {'xx',"yyy","zz"}},
	{"k1": {"truc2","bidule2"}, "k2" : {"machin2","blaba2"}, "k3" : {'xx2',"yyy2","zz2"}},
	{"k1": {"truc2","bidule2"}, "k2" : {"machin2","blaba2"}, "k3" : {'xx2',"yyy2","zz2"}},
	{"k1": {"truc","bidule"}, "k2" : {"machin","blaba"}, "k3" : {'xx',"yyy","zz"}},   # doublon à supprimer
]
KEYS = 'k1', 'k2', 'k3',
m = set()
result = []
for d in base:
    v = tuple(tuple(sorted(d[k])) for k in KEYS)
    if v not in m:
        m.add(v)
        result.append(d)
print(m)
print(result)

Après tout lire pour trier pour ensuite retirer les doublons ou tester l'existence de la valeur calculée dans un set avant de... c'est à tester avec de vraies données.

- W