[Python]Suppresion de doublons dans une liste

Suppresion de doublons dans une liste [Python] - Python - Programmation

Marsh Posté le 29-04-2007 à 06:17:34    

Bonjour,
 
Je me souviens d'une astuce assez compliquée (conversion de la liste en dictionnaire, puis retour en liste) pour supprimer les doublons d'une liste, y'aurait-il plus simple?


Message édité par chaica le 29-04-2007 à 06:17:55
Reply

Marsh Posté le 29-04-2007 à 06:17:34   

Reply

Marsh Posté le 29-04-2007 à 09:27:16    

Salut, tu peux utiliser set, cf http://docs.python.org/lib/module-sets.html.

Code :
  1. >>> liste = ["tutu", "toto", "titi", "tutu", "toto", "tata", "toto"]
  2. >>> set(liste)
  3. set(['toto', 'titi', 'tutu', 'tata'])
  4. >>> list(set(liste))
  5. ['toto', 'titi', 'tutu', 'tata']

avec les dictionnaires, ca donne:

Code :
  1. >>> liste = ["tutu", "toto", "titi", "tutu", "toto", "tata", "toto"]
  2. >>> dic = {}
  3. >>> [dic.setdefault(item, 0) for item in liste]
  4. [0, 0, 0, 0, 0, 0, 0]
  5. >>> dic.keys()
  6. ['toto', 'titi', 'tutu', 'tata']

Message cité 1 fois
Message édité par elpacificator le 29-04-2007 à 09:51:14
Reply

Marsh Posté le 29-04-2007 à 09:50:09    

Merci! Je regarde ça.

Reply

Marsh Posté le 29-04-2007 à 14:01:56    

elpacificator a écrit :

Salut, tu peux utiliser set, cf http://docs.python.org/lib/module-sets.html.

Code :
  1. >>> liste = ["tutu", "toto", "titi", "tutu", "toto", "tata", "toto"]
  2. >>> set(liste)
  3. set(['toto', 'titi', 'tutu', 'tata'])
  4. >>> list(set(liste))
  5. ['toto', 'titi', 'tutu', 'tata']

avec les dictionnaires, ca donne:

Code :
  1. >>> liste = ["tutu", "toto", "titi", "tutu", "toto", "tata", "toto"]
  2. >>> dic = {}
  3. >>> [dic.setdefault(item, 0) for item in liste]
  4. [0, 0, 0, 0, 0, 0, 0]
  5. >>> dic.keys()
  6. ['toto', 'titi', 'tutu', 'tata']



Ouais mais en faisant ça tu perds l'ordre de ta liste :o

Code :
  1. >>> l = ["tutu", "toto", "titi", "tutu", "toto", "tata", "toto"]
  2. >>> def nub(inpt):
  3.     seen = set()
  4.     out = []
  5.     for item in inpt:
  6.         if item not in seen:
  7.             seen.add(item)
  8.             out.append(item)
  9.     return out
  10.  
  11. >>> nub(l)
  12. ['tutu', 'toto', 'titi', 'tata']


Par contre ça ne fonctionne que si les objets contenus dans la liste sont hashables


---------------
Stick a parrot in a Call of Duty lobby, and you're gonna get a racist parrot. — Cody
Reply

Marsh Posté le 29-04-2007 à 20:01:17    

Code :
  1. >>> liste = ["tutu", "toto", "titi", "tutu", "toto", "tata", "toto"]
  2. >>> nv = []
  3. >>> [nv.append(item) for item in liste if not item in nv]
  4. [None, None, None, None]
  5. >>> nv
  6. ['tutu', 'toto', 'titi', 'tata']

Message cité 1 fois
Message édité par elpacificator le 29-04-2007 à 20:01:49
Reply

Marsh Posté le 29-04-2007 à 20:15:31    

elpacificator a écrit :

Code :
  1. >>> liste = ["tutu", "toto", "titi", "tutu", "toto", "tata", "toto"]
  2. >>> nv = []
  3. >>> [nv.append(item) for item in liste if not item in nv]
  4. [None, None, None, None]
  5. >>> nv
  6. ['tutu', 'toto', 'titi', 'tata']



On peut aussi faire comme ça, mais le lookup dans une liste (le "not in", donc) se fait en O(n) alors que dans un set c'est en O(1), donc sur une grosse liste le ralentissement va être sensible, surtout si il y a un grand nombre de redondances (donc un faible nombre d'insertions par rapport au nombre de lookups, puisque je suis obligé de faire un `append` et un `add` pour chaque insertion alors que tu ne fais qu'un `append`) ;)

 

Je me suis complètement planté dans mon analyse du "worst-case", apparement l'insertion dans un set a un coût extrèmement faible, donc en réalité le "worst case" de la méthode d'elpacificator c'est quand on a très peu de redondances, donc que la liste dans laquelle on fait les insertions augmente très vite, donc qu'il y a un très très grand nombre de valeurs dans le lookup. Parce que avec un maximum de redondances, la liste ne dépasse pas 1 élément, donc le lookup se fait en temps constant en permanence, donc ma méthode "perd" du fait de l'initialisation de 2 conteneurs + 2 inserts de l'unique valeur à insérer :D


Message édité par masklinn le 29-04-2007 à 20:52:39

---------------
Stick a parrot in a Call of Duty lobby, and you're gonna get a racist parrot. — Cody
Reply

Marsh Posté le 29-04-2007 à 20:23:08    

Masklinn, toujours à la pointe de l'optimisation ;)
En fonction de la taille de la liste, je preferais ta solution.
Bien joué.

Message cité 1 fois
Message édité par elpacificator le 29-04-2007 à 20:23:35
Reply

Marsh Posté le 29-04-2007 à 20:45:53    

elpacificator a écrit :

Masklinn, toujours à la pointe de l'optimisation ;)
En fonction de la taille de la liste, je preferais ta solution.
Bien joué.


J'ai fait un test, parce qu'en fait j'avais peur de passer pour un con (l'overhead du maintient de deux conteneurs et des insertions doublées pouvait être beaucoup plus coûteux que prévu quand on a beaucoup de redondances)...

 

Au final ça donne ça (nub1 est ta méthode placée dans une fonction, nub2 est ma méthode, le code est après si tu veux tester sur ta machine)

no redundancy (range(10000))
        nub1: 191.579228366 s
        nub2: 0.709584598042 s

 

100 rendundancies (randint on 100 values for a list of 10000)
        nub1: 2.20832061058 s
        nub2: 0.168822853184 s

 

1000 rendundancies (randint on 10 values for a list of 10000)
        nub1: 0.333726772537 s
        nub2: 0.161845988806 s

 

only redundancies (list of 10000 '1's)
        nub1: 0.146482863045 s
        nub2: 0.163449544565 s


À part avec un maximum de redondance, nub1 a des performances inférieures à nub2, et en fait en dessous de 10% de redondances il a des perfs complètement catastrophiques [:pingouino]

 

Voilà le code de test, si j'ai fait une connerie (pas la peine de me dire que j'aurais pu factoriser les 4 tests en une seule fonction, c'était pas l'intérêt du truc :o)

 
Code :
  1. from random import randint
  2. from timeit import Timer
  3.  
  4. ITERATIONS = 100
  5.  
  6. def nub2(inpt):
  7.     seen = set()
  8.     out = []
  9.     for item in inpt:
  10.         if item not in seen:
  11.             seen.add(item)
  12.             out.append(item)
  13.     return out
  14.  
  15. def nub1(inpt):
  16.     nv = []
  17.     [nv.append(item) for item in inpt if not item in nv]
  18.     return nv
  19.  
  20. # no redundancy
  21. l1 = range(10000)
  22.  
  23. t11 = Timer('nub1(l1)', 'from __main__ import nub1, l1')
  24. t12 = Timer('nub2(l1)', 'from __main__ import nub2, l1')
  25.  
  26. print "no redundancy (range(10000))"
  27. print "\tnub1:", min(t11.repeat(3,ITERATIONS)), "s"
  28. print "\tnub2:", min(t12.repeat(3,ITERATIONS)), "s"
  29. print
  30.  
  31. # average 100 rendundancies
  32. l2 = [randint(1, 100) for i in range(10000)]
  33.  
  34. t21 = Timer('nub1(l2)', 'from __main__ import nub1, l2')
  35. t22 = Timer('nub2(l2)', 'from __main__ import nub2, l2')
  36.  
  37. print "100 rendundancies (randint on 100 values for a list of 10000)"
  38. print "\tnub1:", min(t21.repeat(3,ITERATIONS)), "s"
  39. print "\tnub2:", min(t22.repeat(3,ITERATIONS)), "s"
  40. print
  41.  
  42. # average 1000 redundancies
  43. l4 = [randint(1, 10) for i in range(10000)]
  44.  
  45. t41 = Timer('nub1(l4)', 'from __main__ import nub1, l4')
  46. t42 = Timer('nub2(l4)', 'from __main__ import nub2, l4')
  47.  
  48. print "1000 rendundancies (randint on 10 values for a list of 10000)"
  49. print "\tnub1:", min(t41.repeat(3,ITERATIONS)), "s"
  50. print "\tnub2:", min(t42.repeat(3,ITERATIONS)), "s"
  51. print
  52.  
  53. # only redundancies
  54. l3 = [1 for i in range(10000)]
  55.  
  56. t31 = Timer('nub1(l3)', 'from __main__ import nub1, l3')
  57. t32 = Timer('nub2(l3)', 'from __main__ import nub2, l3')
  58.  
  59. print "only redundancies (list of 10000 '1's)"
  60. print "\tnub1:", min(t31.repeat(3,ITERATIONS)), "s"
  61. print "\tnub2:", min(t32.repeat(3,ITERATIONS)), "s"
  62. print


edit: testé sur un A64 4400+, donc cadencé à 2.2GHz, changez le paramètre ITERATIONS si votre CPU est moins véloce parce que 3mn20s ça fait déjà beaucoup [:pingouino]


Message édité par masklinn le 29-04-2007 à 20:48:58

---------------
Stick a parrot in a Call of Duty lobby, and you're gonna get a racist parrot. — Cody
Reply

Marsh Posté le 29-04-2007 à 21:33:51    

Code :
  1. no redundancy (range(10000))
  2.         nub1: 184.481250269 s
  3.         nub2: 0.865348730397 s
  5. 100 rendundancies (randint on 100 values for a list of 10000)
  6.         nub1: 2.13636449559 s
  7.         nub2: 0.419321081109 s
  9. 1000 rendundancies (randint on 10 values for a list of 10000)
  10.         nub1: 0.298846549728 s
  11.         nub2: 0.404840663949 s
  13. only redundancies (list of 10000 '1's)
  14.         nub1: 0.101266828052 s
  15.         nub2: 0.403219947266 s

sur un P4 3.06GHz HT.


Message édité par elpacificator le 29-04-2007 à 21:36:33
Reply

Marsh Posté le 29-04-2007 à 22:07:03    

[:mlc]

 

Whoa, nub2 tourne vachement moins bien sur un P4 (alors que nub1 tourne sensiblement de la même manière, on voit juste une différence ce fréquence) [:pingouino]

 

J'me demande à quoi c'est dû [:gratgrat]

 

Le cache ptet [:gratgrat]

 

En tout cas, on voit bien qu'aux constantes près le comportement est le même, nub2 est beaucoup plus régulier dans toutes les situations et n'a pas d'explosion du temps de calcul :o


Message édité par masklinn le 29-04-2007 à 22:07:19

---------------
Stick a parrot in a Call of Duty lobby, and you're gonna get a racist parrot. — Cody
Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed