Bonjour tout le monde,

J'aurais une question assez simple sur le fond mais qui me gêne assez, j'ai redécouvert le langage python il y a quelques semaines après deux ans d'abandon et certains réflexes me manquent encore. J'ai notamment cherché à réaliser une liste de dictionnaires avec des exemplaires uniques. Pour cela j'ai tenté de faire un set de mes données, en pensant que comme tout est objet en Python, ça marcherait comme sur des roulettes. Cependant j'ai eu l'erreur suivante :

TypeError: unhashable type: 'dict'

Donc voilà, la logique simple serait de vérifier si le dico en question n'est pas déjà dans la liste de dico (avec l'opérateur in peut-être) mais j'ai l'impression que ça va être assez lourd (je me trompe ?), étant donné que je bosse sur des data pouvant excéder facilement les 300k dicos dans une même liste à la fin de la chaîne. Donc je me demande si un plan B ou C existe et auquel je n'aurais pas pensé, peut-être aussi benchmarker ça si nécessaire. Si ça se trouve, je suis aussi juste à coté de la plaque et je m'en excuse d'avance ...

Merci.

+

Avec un type set tu ne peux pas ajouter de dictionnaire pour la raison mentionner dans ton post.

Maintenant, python, reconnaît bien la différence entre dictionnaire...

>>> dico = {'a':4, 'b':8}
>>> dic = {'a':4, 'b':8}
>>> dico == dic
True

Tu pourrais ainsi créer une liste, où tu ajouterais ton dico en vérifiant que le dico n'est pas déjà dans la liste.

if dico not in liste:
    liste.append(dico)

Bonne continuation...

Essaye au moins avec l'opérateur in. Je n'ai plus sa complexité (sur les listes) en mémoire mais je crois me souvenir qu'elle était constante dans le cas amorti (et je n'ai pas de pc sous la main pour faire une recherche).

-
Edité par nohar 5 juillet 2013 à 19:27:48

Bonjour,

Merci de vos réponses, en effet j'avais déjà pensé à l'opérateur in comme indiqué dans mon premier message, je me demandais en fait surtout s'il n'existait pas une autre manière (à votre connaissance) qui est plus rapide ou alors plus esthétique (bien que celle-ci est loin d'être moche je l'avoue). Il faudrait que je me renseigne un peu plus sur ce opérateur, ce ne serait pas d'ailleurs du C ou un langage plus bas niveau qui se cache derrière ce genre d'opérateur ? J'imagine que celui-ci est déjà très performant ...

Bon si tu recherches la vitesse d'exécution, je te conseille d'aller voir du côté du module numpy pour jouer avec ses arrays.

Ça dépend des implémentations, mais dans la distribution standard c'est effectivement du C.

Quelle est le nombre d'éléments dans les dict ? et le nombre d'éléments distincts max entre tous les dict ? et le type des éléments, clé et valeur ?

Si les dict sont courts et tu as peu d'éléments distincts, tu peux utiliser des bitfields.

Si tu as beaucoup d'éléments distincts, et que les valeurs sont des objets eux-même hashables, tu peux représenter chaque dico sous forme d'un tuple (genre : tuple(sorted(dico.items()))). Ces tuples sont hashables, donc ta recherche d'unicité est facile (au pire fourre les tous dans un set). Le sorted() assure que 2 dict ayant le même contenu donnent le même tuple, même si 2 clés différentes ont le même hash.

Si les clés/valeurs sont des nombres tu peux utiliser des array numpy, ça prend moins de RAM.

Si la quantité de données à manipuler dépasse la RAM tu peux aussi utiliser d'autres outils : transformer chaque dico en tuple comme ci-dessus, sérialiser sous forme de strings, et utiliser un outil de tri performant (une BDD SQL, nsort, etc)

Si les données sont de types simples (nombres, etc) et proviennent d'un fichier texte ou d'une base SQL, tu peux d'ailleurs squeezer python complètement...

Etc.

Un exemple en SQL (postgres) qui marche bien pour des dicts courts :

-- créé une table avec 600k paires de clés/valeurs avec 100k dictid distincts

create table dicts( dictid integer not null, 
  k integer not null, 
  v integer not null );

insert into dicts 
SELECT DISTINCT dict, k, (random()*10)::INTEGER FROM (
  select DISTINCT (n/10)::INTEGER dict, 
  (random()*10)::INTEGER k 
  from generate_series(1,1000000) n
) foo;

-- montre quelques dicts (clés et valeurs dans 2 arrays,
-- pour avoir un dict il faudrait zip()per les deux)
SELECT dictid, array_agg( k ) k, array_agg( v ) v FROM (select * from dicts order by dictid,k,v) foo group by dictid LIMIT 10;

 dictid |        k         |         v         
--------+------------------+-------------------
      0 | {3,5,6,7,9}      | {9,6,9,3,2}
      1 | {1,2,3,4,5,6,8}  | {5,10,7,2,2,9,2}
      2 | {1,2,3,4,5,6}    | {10,8,10,10,6,6}
      3 | {2,3,5,7,8,9,10} | {2,6,0,9,0,5,9}
      4 | {1,3,4,5,7,9,10} | {5,4,5,6,7,6,4}
      5 | {2,5,6,8,9,10}   | {8,4,1,2,9,4}
      6 | {1,2,4,5,6,7,8}  | {0,3,1,6,3,1,9}
      7 | {1,2,3,4,5,7}    | {4,6,0,0,1,0}
      8 | {2,3,4,5,6,10}   | {3,2,2,9,3,9}
      9 | {1,3,4,5,6,7,8}  | {5,10,9,6,5,6,10}

-- donne les dicts distincts avec le nombre d'occurences

select *, count(*) from (
  SELECT array_agg( k ) k, array_agg( v ) v FROM (
    select * from dicts order by dictid,k,v) foo 
  group by dictid) foo 
group by k,v

-- Environ 2.5s pour 100k dicts.

Le même truc en python (avec les mêmes dicts) :

import psycopg2, time, random

db=psycopg2.connect('dbname=test')
c = db.cursor()

# construit les dicts (les memes que dans l'exemple precedent)
dicts = {}
c.execute( "SELECT dictid, k, v FROM dicts" )
for dictid,k,v in c:
    d = dicts.setdefault(dictid,{})
    d[k] = v

dicts = dicts.values()
print len(dicts)
print dicts[0]

# unicité : cette ligne prend ~ 0.5s
print len( set( tuple(d.items()) for d in dicts ) )

-
Edité par Lord Casque Noir 8 juillet 2013 à 10:00:19

Ok, merci pour ta réponse, je vais devoir bashoter ça un peu dans mon coin. Pour l'instant je suis passé sur la solution de l'opérateur in, je suis encore en phase de test donc je ne sais pas encore si à plein régime ça ira "assez vite" mais pour l'instant j'ai l'impression que c'est satisfaisant pour mon cas. Pour les clés valeurs, l'ensemble des clés sont des string mais les valeurs varient en fonction de la clé, pour l'instant j'ai 9 clés/valeurs pour chaque dico. Mais faut avouer que la solution du bitfield ne me donne pas spécialement envie aux premiers abords

Encore merci pour ta réponse en tous cas.