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)

[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