Discussion :

[thepolux]

Bonjour,

Je rencontre un petit problème avec les listes: le tri de doublons (et Google n'a pas su répondre à ma question)

Voici un exemple du genre de listes que j'aurais a traiter:

[(1, 1, 4), (3, 1, 11), (2, 1, 13), (6, 1, 17), (5, 1, 17), (4, 1, 18), (2, 2, 28), (1, 2, 29), (3, 2, 30), (4, 2, 31), (5, 2, 31), (6, 2, 33), (1, 3, 45), (3, 3, 51)] etc..

avec [(identifiant, tour, temps_en_secondes),]

(je ne connais ni le nombre de tours a l'avance ni le nombre d'identifiants)

En fait, j'ai besoin de ne récupérer de cette liste qu'un seul tuple par identifiant - celui du tour le plus élevé pour avoir au final quelque chose qui ressemble a ça:

[(3, 3, 51),
(1, 3, 45),
(6, 2, 33),
(5, 2, 31),
(4, 2, 31),
(3, 2, 30),
(2, 2, 28)]

Seulement je ne vois pas du tout comment m'y prendre, et toutes mes tentatives pour le moment on été infructueuse.

Merci d'avance pour le coup de main !

Adrien.

[eyquem]

Bonsoir,

Bienvenue sur le forum.

Je te suggère de regarder la fonction itemgetter()
http://www.python.org/doc/2.5.2/lib/....html#l2h-1193

Je te laisse réfléchir, et si tu ne vois pas ce qu'on peut en faire, je reviendrai te donner un autre coup de main.



PS

Je viens de m'apercevoir que, même si les identifiants sont listés sans ordre au sein de la liste, il n'en est pas de même pour les tours de chaque identifiant. C'est à dire que les tuples de l'identifiant 1 sont successivement (1, 1, 4), (1, 2, 29), (1, 3, 45),
ceux de l'identifiant 3 sont successivement (3, 1, 11), (3, 2, 30), (3, 3, 51)...

Ce qui simplifie le problème et rend inutile l'emploi de itemgetter().
Mais il n'est pas dit que ce soit toujours le cas.
Comment est obtenue la liste ? Est-elle toujours semi-ordonnée pareillement ?

À l'inverse, que doit on faire s'il y a deux ou + temps pour un même identifiant et un même tour ? Faut il que le temps soit maximal ausi, ou peu importe ?

[thepolux]

Après avoir été aidé et pas mal de réflexion voici trois solutions a ce problème, j'espère que ça pourra aider d'autres personnes dans ma situation:

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
 
>>> l = [(1, 1, 4), (3, 1, 11), (2, 1, 13), (6, 1, 17), (5, 1, 17), (4, 1, 18), (2, 2, 28), (1, 2, 29), (3, 2, 30), (4, 2, 31), (5, 2, 31), (6, 2, 33), (1, 3, 45), (3, 3, 51)]
 
>>> d = {}
>>> for x in l:
...     if x[0] in d:
...             if x[1] > d[x[0]][0]:
...                     d[x[0]] = x[1:]
...     else:
...             d[x[0]] = x[1:]
... 
>>> d.items()
[(1, (3, 45)), (2, (2, 28)), (3, (3, 51)), (4, (2, 31)), (5, (2, 31)), (6, (2, 33))]
 
 
>>> print dict([(x[0], x) for x in sorted(l, key=lambda x: x[1])]).values()
[(1, 3, 45), (2, 2, 28), (3, 3, 51), (4, 2, 31), (5, 2, 31), (6, 2, 33)]
 
>>> import itertools
>>> import operator
>>> print dict((k, max(v, key=operator.itemgetter(1))) for k, v in itertools.groupby(sorted(l), key=operator.itemgetter(0))).values()
[(1, 3, 45), (2, 2, 28), (3, 3, 51), (4, 2, 31), (5, 2, 31), (6, 2, 33)]

Merci NaPs, vrialland et eyquem.

[eyquem]

Impressionante, la dernière solution. Je vois que tu as trouvé comment user de itemgetter() !
Petite info: itemgetter(0) est inutile; li.sort() trie la liste de tuples selon le premier élément de chaque tuple. C'est ce que j'ai utilisé dans les deux codes suivants.


Le premier est ce à quoi je pensais en évoquant itemgetter(). Mais dans la pratique, ça donne un code un peu fouillis.

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
 
li = [(1, 1, 4), (3, 1, 11), (2, 1, 13), (6, 1, 17), (5, 1, 17),
      (4, 1, 18), (2, 2, 28), (1, 2, 29), (3, 2, 30), (4, 2, 31),
      (5, 2, 31), (6, 2, 33), (1, 3, 45), (3, 3, 51)]
li.sort()
lu = []
bloc = [li[0]]
id = li[0][0]
for u in li[1:]:
    if u[0] == id:
        bloc.append(u)
    else:
        lu.append(sorted(bloc,key=itemgetter(1))[-1])
        bloc = [u]
        id = u[0]
lu.append(sorted(bloc,key=itemgetter(1))[-1])
print 'lu =',lu

Le second code est plus clair:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
li = [(1, 1, 4), (3, 1, 11), (2, 1, 13), (6, 1, 17), (5, 1, 17),
      (4, 1, 18), (2, 2, 28), (1, 2, 29), (3, 2, 30), (4, 2, 31),
      (5, 2, 31), (6, 2, 33), (1, 3, 45), (3, 3, 51)]
li.sort()
lu = []
elem = li[0]
for u in li[1:]:
    if u[0]!=elem[0]:
        lu.append(elem)
        elem = u
    elif u[1]>elem[1]:
        elem = u
lu.append(elem)
print lu

Ton avant-derniere solution est la meilleure: claire et condensée.
Nota: key=lambda x: x[1] c'est itemgetter(1)

[tyrtamos]

Bonjour,

Suggestion:

Code :

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

1
2
3
4
5
6
7
8
 
L = [(1, 1, 4), (3, 1, 11), (2, 1, 13), (6, 1, 17), (5, 1, 17),
      (4, 1, 18), (2, 2, 28), (1, 2, 29), (3, 2, 30), (4, 2, 31),
      (5, 2, 31), (6, 2, 33), (1, 3, 45), (3, 3, 51)]
 
L.sort(key=lambda x: x[1], reverse = True)
 
R = [e for i,e in enumerate(L) if e[0] not in [a for a,b,c in L[0:i]]]

Ce qui donne pour R:

Code :

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

[(1, 3, 45), (3, 3, 51), (2, 2, 28), (4, 2, 31), (5, 2, 31), (6, 2, 33)]

Tyrtamos

[eyquem]

Ta solution présente une faiblesse, tyrtamos:
pour chaque élément de L, le programme doit recréer une liste [a for a,b,c in L[0:i]] avant de tester e[0] in [a for a,b,c in L[0:i]].
Plus la liste sera longue, plus cette recréation sera un facteur de lenteur.

Le principe de ton code est de vérifier qu'un identifiant n'a pas été déjà vu avant de retenir le tuple pour constituer R. Je pense que tu l'as écrit ainsi pour pouvoir utiliser une list comprehension.
Mais cela peut se faire plus simplement que ta solution, et plus simplement aussi que mes deux précédentes solutions poussives:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
li = [(1, 1, 4), (3, 1, 11), (2, 1, 13), (6, 1, 17), (5, 1, 17),
      (4, 1, 18), (2, 2, 28), (1, 2, 29), (3, 2, 30), (4, 2, 31),
      (5, 2, 31), (6, 2, 33), (1, 3, 45), (3, 3, 51)]
from operator import itemgetter
lu = []
deja = set([])
for u in sorted(li,key=itemgetter(1),reverse=True).__iter__():
    if u[0] not in deja:
        lu.append(u)
        deja.add(u[0])
print lu

Et en utilisant une astuce, c'est à dire deux instructions formant un tuple pour pouvoir faire deux instructions dans une list comprehension, on peut même mettre ça sous forme de list comprehension !

Code :

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

1
2
3
4
5
6
7
8
li = [(1, 1, 4), (3, 1, 11), (2, 1, 13), (6, 1, 17), (5, 1, 17),
      (4, 1, 18), (2, 2, 28), (1, 2, 29), (3, 2, 30), (4, 2, 31),
      (5, 2, 31), (6, 2, 33), (1, 3, 45), (3, 3, 51)]
from operator import itemgetter
lu = []
deja = set([])
[ (lu.append(u),deja.add(u[0])) for u in sorted(li,key=itemgetter(1),reverse=True).__iter__() if u[0] not in deja]
print lu

Je suis prêt à parier que cette méthode est plus rapide.






Sinon, j'aime bien l'utilisation de dictionnaire que fait thepolux: ça permet de rejeter sur l'ensemble keys() d'un dictionnaire le travail de savoir si un identifiant a été déjà référencé ou non. Si oui l'ancienne valeur d'un identifiant est écrasé.

L'inconvénient de

Code :

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

dict([(x[0], x) for x in sorted(l, key=lambda x: x[1])]).values()

c'est qu'une affectation d[x[0]] = x est effectuée pour chacun des éléments x de la liste: le dictionnaire travaille pour absolument tous ces éléments, sur certains en créant une nouvelle clé, sur tous les autres en écrasant l'ancienne valeur d'une clé préexistante. C'est du boulot superflu. L'ajout d'une condition évite ce travail:

Code :

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

1
2
3
4
5
6
7
8
9
li = [(1, 1, 4), (3, 1, 11), (2, 1, 13), (6, 1, 17), (5, 1, 17),
      (4, 1, 18), (2, 2, 28), (1, 2, 29), (3, 2, 30), (4, 2, 31),
      (5, 2, 31), (6, 2, 33), (1, 3, 45), (3, 3, 51)]
from operator import itemgetter
d = {}
for u in sorted(li,key=itemgetter(1),reverse=True).__iter__():
    if u[0] not in d:
        d[u[0]] = u
print d.values()

Grâce à l'emploi d'un dictionnaire on n'a plus qu'une instruction après le if.


Ce qui donne finalement une list comprehension à la fois compréhensible, condensée et rapide.

Code :

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

1
2
3
4
5
6
7
li = [(1, 1, 4), (3, 1, 11), (2, 1, 13), (6, 1, 17), (5, 1, 17),
      (4, 1, 18), (2, 2, 28), (1, 2, 29), (3, 2, 30), (4, 2, 31),
      (5, 2, 31), (6, 2, 33), (1, 3, 45), (3, 3, 51)]
from operator import itemgetter
d = {}
[d.update(u[0],u) for u in sorted(li,key=itemgetter(1),reverse=True).__iter__() if u[0] not in d]
print d.values()

EDIT

euh.... Je crois que ça ne sert à rien d'écrire

Code :

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

1
2
3
sorted(li,key=itemgetter(1),reverse=True).__iter__()
# plutôt que
sorted(li,key=itemgetter(1),reverse=True)

car la liste sorted(li,key=itemgetter(1),reverse=True) est de toutes façons créée ans les deux cas.

J'aurais aimé mettre un itérateur pour la rapidité. Ou un générateur.
Mais je ne vois pas comment faire.
Quelqu'un peut me dire comment eviter une liste en dur ?