[Python]Suppresion de doublons dans une liste

Recherche :

Mot : Pseudo : Filtrer
Bas de page
Auteur	Sujet : [Python]Suppresion de doublons dans une liste

chaica

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

Publicité

elpacificator

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

Code :

>>> liste = ["tutu", "toto", "titi", "tutu", "toto", "tata", "toto"]
>>> set(liste)
set(['toto', 'titi', 'tutu', 'tata'])
>>> list(set(liste))
['toto', 'titi', 'tutu', 'tata']

avec les dictionnaires, ca donne:

Code :

>>> liste = ["tutu", "toto", "titi", "tutu", "toto", "tata", "toto"]
>>> dic = {}
>>> [dic.setdefault(item, 0) for item in liste]
[0, 0, 0, 0, 0, 0, 0]
>>> dic.keys()
['toto', 'titi', 'tutu', 'tata']

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

chaica

Merci! Je regarde ça.

masklinn

í dag viðrar vel til loftárása

elpacificator a écrit :

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

Code :

>>> liste = ["tutu", "toto", "titi", "tutu", "toto", "tata", "toto"]
>>> set(liste)
set(['toto', 'titi', 'tutu', 'tata'])
>>> list(set(liste))
['toto', 'titi', 'tutu', 'tata']

avec les dictionnaires, ca donne:

Code :

>>> liste = ["tutu", "toto", "titi", "tutu", "toto", "tata", "toto"]
>>> dic = {}
>>> [dic.setdefault(item, 0) for item in liste]
[0, 0, 0, 0, 0, 0, 0]
>>> dic.keys()
['toto', 'titi', 'tutu', 'tata']

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

Code :

>>> l = ["tutu", "toto", "titi", "tutu", "toto", "tata", "toto"]
>>> def nub(inpt):
    seen = set()
    out = []
    for item in inpt:
        if item not in seen:
            seen.add(item)
            out.append(item)
    return out
 
>>> nub(l)
['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

elpacificator

Code :

>>> liste = ["tutu", "toto", "titi", "tutu", "toto", "tata", "toto"]
>>> nv = []
>>> [nv.append(item) for item in liste if not item in nv]
[None, None, None, None]
>>> nv
['tutu', 'toto', 'titi', 'tata']

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

masklinn

í dag viðrar vel til loftárása

elpacificator a écrit :

Code :

>>> liste = ["tutu", "toto", "titi", "tutu", "toto", "tata", "toto"]
>>> nv = []
>>> [nv.append(item) for item in liste if not item in nv]
[None, None, None, None]
>>> nv
['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

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

elpacificator

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

masklinn

í dag viðrar vel til loftárása

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 )

Code :

from random import randint
from timeit import Timer
 
ITERATIONS = 100
 
def nub2(inpt):
    seen = set()
    out = []
    for item in inpt:
        if item not in seen:
            seen.add(item)
            out.append(item)
    return out
 
def nub1(inpt):
    nv = []
    [nv.append(item) for item in inpt if not item in nv]
    return nv
 
# no redundancy
l1 = range(10000)
 
t11 = Timer('nub1(l1)', 'from __main__ import nub1, l1')
t12 = Timer('nub2(l1)', 'from __main__ import nub2, l1')
 
print "no redundancy (range(10000))"
print "\tnub1:", min(t11.repeat(3,ITERATIONS)), "s"
print "\tnub2:", min(t12.repeat(3,ITERATIONS)), "s"
print
 
# average 100 rendundancies
l2 = [randint(1, 100) for i in range(10000)]
 
t21 = Timer('nub1(l2)', 'from __main__ import nub1, l2')
t22 = Timer('nub2(l2)', 'from __main__ import nub2, l2')
 
print "100 rendundancies (randint on 100 values for a list of 10000)"
print "\tnub1:", min(t21.repeat(3,ITERATIONS)), "s"
print "\tnub2:", min(t22.repeat(3,ITERATIONS)), "s"
print
 
# average 1000 redundancies
l4 = [randint(1, 10) for i in range(10000)]
 
t41 = Timer('nub1(l4)', 'from __main__ import nub1, l4')
t42 = Timer('nub2(l4)', 'from __main__ import nub2, l4')
 
print "1000 rendundancies (randint on 10 values for a list of 10000)"
print "\tnub1:", min(t41.repeat(3,ITERATIONS)), "s"
print "\tnub2:", min(t42.repeat(3,ITERATIONS)), "s"
print
 
# only redundancies
l3 = [1 for i in range(10000)]
 
t31 = Timer('nub1(l3)', 'from __main__ import nub1, l3')
t32 = Timer('nub2(l3)', 'from __main__ import nub2, l3')
 
print "only redundancies (list of 10000 '1's)"
print "\tnub1:", min(t31.repeat(3,ITERATIONS)), "s"
print "\tnub2:", min(t32.repeat(3,ITERATIONS)), "s"
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

elpacificator

Code :

no redundancy (range(10000))
nub1: 184.481250269 s
nub2: 0.865348730397 s
100 rendundancies (randint on 100 values for a list of 10000)
nub1: 2.13636449559 s
nub2: 0.419321081109 s
1000 rendundancies (randint on 10 values for a list of 10000)
nub1: 0.298846549728 s
nub2: 0.404840663949 s
only redundancies (list of 10000 '1's)
nub1: 0.101266828052 s
nub2: 0.403219947266 s

sur un P4 3.06GHz HT.

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

masklinn

í dag viðrar vel til loftárása

[: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

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

FORUM HardWare.fr

Programmation

Python

[Python]Suppresion de doublons dans une liste

Sujets relatifs
[Python] Packager un programme	Traitement d'une fonction Ping avec une liste de PC ds un fichier exl
liste déroulante dans sous-formulaire avec access	liste déroulante dans sous formulaire avec access
Affichage d'une cubiquer Python/Qt4	python et l'unicode : -U / python 3000 / repr ... [résolu]
comparer une liste de date sql avec la date today	liste déroulante pour galerie
AJAX:formulaire avec liste déroulante dynamique	[Erreur python]underlying C/C++ object has been deleted [ Résolu ]
Plus de sujets relatifs à : [Python]Suppresion de doublons dans une liste

Page générée en 0.104 secondes