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 ?

[alexdevl]

J'essayai, pour ce problème, moi aussi d'utiliser un dico dans une liste compréhension.
Mais cela ne fonctionne pas avec d[u[0]]=u car il n'est pas possible de faire une affectation.

Plutôt pertinent le ''d.update(u[0],u)''

[eyquem]

Oui, très utiles les " non-operator versions " de certaines méthodes. On peut les utiliser dans des list comprehension, alors que leurs version "operateur" on ne peut pas.
Et il y a même des choses pratiques supplémentaires à decouvrir en lisant les notes dans les chapitres 3.7 et 3.8 de la Python Library Reference (de Python 2.5):

Par exemple

«update() accepts either another mapping object or an iterable of key/value pairs (as a tuple or other iterable of length two).»
pour les dictionnaires

«Note, the non-operator versions of union(), intersection(), difference(), and symmetric_difference(), issubset(), and issuperset() methods will accept any iterable as an argument.»
pour les ensembles (set)


Python, c'est génial !

[Zavonen]

L'ennuyeux en utilisant des fonctions 'avancées', c'est qu'en l'absence d'information sur leur implémentation, on peut difficilement évaluer la performance.
L'algo qui suit est à coup sûr en nlog(n):

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
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[0],x[1]))
R=[]
y=L[0]
for x in L:
    if x[0]==y[0]:
        y=x
        continue
    R.append(y)
    y=x
R.append(y)
 
print R

[eyquem]

Je ne connaissais pas le mot-clé 'continue', ce qui n'est pas un gros manque parce qu'on peut très bien se débrouiller à faire pareil avec un else. Mais il semble que l'utilisation de 'continue' rende un tout petit chouya plus rapide l'exécution. Je pense que 'continue' doit être plus essentiellement pratique dans d'autres cas de figure.

Quant à trier la liste non seulement sur le second élément de chaque tuple, mais sur les deux premiers à la fois, c'est malin et ça m'aurait permis de faire un code moins poussif que ceux que j'ai proposés, si j'y avais pensé.



Ma curiosité a été aiguillonée par ton propos général, que je n'ai d'ailleurs pas bien bien compris. Il me semble que tu veux dire que l'utilisation de fonctions "avancées" risque de faire perdre de la performance et que le code que tu proposes a l'avantage de présenter un ordre de vitesse évaluable, ici en nlog(n). Tu sembles sous-entendre que ton code est assurément rapide.

Qu'entends-tu par fonctions "avancées" ? Est-ce que cela implique l'utilisation des list comprehensions ?

Pour ma part, j'ai vu dans la Library Reference qu'il existe pour les ensembles deux versions de certaines méthodes, l'une qualifiée de "version non-opérateur" ( issubset() , union() , intersection() ... ) , l'autre étant dite "basée sur opérateur" ( s <= t , s | t , s & t etc) .
Pour les dictionnaires, on peut considérer que d[x] = y et d.update([(x,y)]) sont aussi deux versions d'une même action, ainsi que d = {} et d.clear().
Cependant update() pour dictionnaire fait plus que d[x] = y; et d.clear() ne fait pas exactement la même chose que d = {} , il fait plutôt l'analogue de del li[:] pour les listes.

Donc en fait, il n'y a deux versions que pour certaines méthodes des ensembles. Et dans les codes ci-dessus, il est surtout question de dictionnaires.




Il est tout à fait possible d'évaluer la performance de n'importe quelle fonction ou bout de code, si tu entends bien performance=vitesse.
J'ai fait les quelques tests suivants qui montrent que les méthodes d'ensembles sont plutôt performantes par rapport aux codes "à la main" équivalents.

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
from timeit import Timer
repet = 5
iterat = 1000
 
def affich(ch,ts):
    print ch.rjust(30)+' :  ','min',str(min(ts))[0:7],'    moy',str(sum(ts)/repet)[0:7],'    max',str(max(ts))[0:7]
 
 
 
ch = 'jhgufwkjdhfferutbjshvipodqferitlkhsd'
 
def fait_set(x):
    return set(x)
print fait_set(ch)
tfait_set = Timer('fait_set(ch)','from __main__ import fait_set,ch').repeat(repet,iterat)
affich('fait_set',tfait_set)
 
 
def fait_add(x):
    e  =  set([])
    for x in ch:
        e.add(x)
    return e
print fait_add(ch)
tfait_add = Timer('fait_add(ch)','from __main__ import fait_add,ch').repeat(repet,iterat)
affich('fait_add',tfait_add)
 
 
def update_set(x):
    f = set([])
    f.update(ch)
    return f
print update_set(ch)
tupdate_set = Timer('update_set(ch)','from __main__ import update_set,ch').repeat(repet,iterat)
affich('update_set',tupdate_set)
 
print '---------------------------------------------------------'
A = set('abcdefghijklmnopq')
B = set('bxgrlwojqzdytu')
 
def intersecte(A,B):
    I = set([])
    for x in A:
        if x in B:
            I.add(x)
    return I
print intersecte(A,B)
tintersecte = Timer('intersecte(A,B)','from __main__ import intersecte,A,B').repeat(repet,iterat)
affich('intersecte',tintersecte)
 
 
def intersect_update(A,B):
    A.intersection_update(B)
    return A
print intersect_update(A,B)
tintersect_update = Timer('intersect_update(A,B)','from __main__ import intersect_update,A,B').repeat(repet,iterat)
affich('intersect_update',tintersect_update)
 
print '-------------------------------------------------------------'
 
 
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),
     (2,4,98), (1,2,45), (6,23,98), (6,36,23), (6,34,12), (3,9,21), (6,4,100),
     (5,7,8), (2,9,4), (5,3,8), (1,4,9), (1,7,3), (4,7,345), (5,6,76), (6,88,45),
     (6,17,23), (1,4,23), (6,5,122), (3,4,7), (2,4,66), (5,34,22), (6,45,3), (0,65,9),
     (3,5,8), (2,12,1), (5,50,5), (0,45,2), (3,21,9), (4,5,85), (4,87,3), (4,7,0),
     (4,12,8), (2,9,21), (6,9,12), (2,6,34), (5,95,3), (1,6,4), (1,7,45), (2,25,44),
     (4,68,3), (2,13,57), (2,64,0), (4,85,9), (3,4,11), (1,45,2), (2,73,8), (5,32,9),
     (6,6,4), (6,7,3), (4,7,67), (3,123,9), (3,5,6), (6,32,10), (2,8,67), (6,47,2),
     (5,95,23), (1,43,7), (6,94,23), (0,6,45), (5,7,5), (3,9,6), (4,65,3), (4,23,12)]
 
def dico_operator(L):
    d = {}
    for x in L:
        d[x[0]] = x
    return d
print dico_operator(L)
tdico_operator = Timer('dico_operator(L)','from __main__ import dico_operator,L').repeat(repet,iterat)
affich('dico_operator',tdico_operator)
 
 
def dico_update_sequence(L):
    LL = [ (x[0],x) for x in L ]
    dic = {}
    dic.update(LL)
    return dic
print dico_update_sequence(L)
tdico_update_sequence = Timer('dico_update_sequence(L)','from __main__ import dico_update_sequence,L').repeat(repet,iterat)
affich('dico_update_sequence',tdico_update_sequence)
 
 
def dico_update_elements(L):
    dic = {}
    [dic.update([(x[0],x)]) for x in L]
    return dic
print dico_update_elements(L)
tdico_update_elements = Timer('dico_update_elements(L)','from __main__ import dico_update_elements,L').repeat(repet,iterat)
affich('dico_update_elements',tdico_update_elements)

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
set(['b', 'e', 'd', 'g', 'f', 'i', 'h', 'k', 'j', 'l', 'o', 'q', 'p', 's', 'r', 'u', 't', 'w', 'v'])
                      fait_set :   min 0.02792     moy 0.02857     max 0.02980
set(['b', 'e', 'd', 'g', 'f', 'i', 'h', 'k', 'j', 'l', 'o', 'q', 'p', 's', 'r', 'u', 't', 'w', 'v'])
                      fait_add :   min 0.07657     moy 0.07728     max 0.07794
set(['b', 'e', 'd', 'g', 'f', 'i', 'h', 'k', 'j', 'l', 'o', 'q', 'p', 's', 'r', 'u', 't', 'w', 'v'])
                    update_set :   min 0.03243     moy 0.03306     max 0.03340
---------------------------------------------------------
set(['b', 'd', 'g', 'j', 'l', 'o', 'q'])
                    intersecte :   min 0.03289     moy 0.03449     max 0.03678
set(['b', 'd', 'g', 'j', 'l', 'o', 'q'])
              intersect_update :   min 0.00871     moy 0.00896     max 0.00943
-------------------------------------------------------------
{0: (0, 6, 45), 1: (1, 43, 7), 2: (2, 8, 67), 3: (3, 9, 6), 4: (4, 23, 12), 5: (5, 7, 5), 6: (6, 94, 23)}
                 dico_operator :   min 0.09273     moy 0.09416     max 0.09528
{0: (0, 6, 45), 1: (1, 43, 7), 2: (2, 8, 67), 3: (3, 9, 6), 4: (4, 23, 12), 5: (5, 7, 5), 6: (6, 94, 23)}
          dico_update_sequence :   min 0.17973     moy 0.19839     max 0.24329
{0: (0, 6, 45), 1: (1, 43, 7), 2: (2, 8, 67), 3: (3, 9, 6), 4: (4, 23, 12), 5: (5, 7, 5), 6: (6, 94, 23)}
          dico_update_elements :   min 1.22742     moy 1.27251     max 1.41039

Par contre il est vrai que ces tests montrent que la méthode update() pour dictionnaire est plus lente (pas énormément: 25% de temps en plus) qu'une itération d[x] = y et que j'ai raconté une grosse bêtise dans le message #4 en disant que la list comprehension que je proposais à la fin était rapide, sous-entendu plus rapide que la version itérative n'utilisant pas update():

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
from operator import itemgetter
 
def affich(ch,ts):
    print ch.rjust(30)+' :  ','min',str(min(ts))[0:7],'    moy',str(sum(ts)/repet)[0:7],'    max',str(max(ts))[0: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)]
 
def iterante(li):
    d = {}
    for u in sorted(li,key=itemgetter(1),reverse=True).__iter__():
        if u[0] not in d:
            d[u[0]] = u
    return d.values()
print iterante(li)
titerante = Timer('iterante(L)','from __main__ import iterante,L').repeat(repet,iterat)
affich('iterante',titerante) 
 
 
def updt(li):
    d = {}
    [d.update([(u[0],u)]) for u in sorted(li,key=itemgetter(1),reverse=True).__iter__() if u[0] not in d]
    return d.values()
print updt(li)
tupdt = Timer('updt(L)','from __main__ import updt,L').repeat(repet,iterat)
affich('updt',tupdt)

Code :

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

1
2
3
4
[(1, 3, 45), (2, 2, 28), (3, 3, 51), (4, 2, 31), (5, 2, 31), (6, 2, 33)]
                      iterante :   min 0.35284     moy 0.39011     max 0.44499
[(1, 3, 45), (2, 2, 28), (3, 3, 51), (4, 2, 31), (5, 2, 31), (6, 2, 33)]
                          updt :   min 0.46525     moy 0.50243     max 0.58590

Ça montre aussi qu'il ne doit pas y avoir grand monde qui regarde en détail les codes parce que personne n'a signalé, ou pris la peine de signaler, que je m'étais trompé dans le code avec list comprehension de la fin du message #4:

Code :

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

d.update(u[0],u) for u in ... etc

ne marche pas.
Il faut écrire

Code :

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

d.update([(u[0],u)]) for u in.....

ce qui est plutôt lourdingue.
Je me demande comment j'ai réussi à mettre mettre un code faux alors que je les fais toujours tourner avant.

L'update() de dictionnaire n'étant pas beaucoup plus lente qu'une méthode à la main, elle reste intéressante à garder sous le coude pour l'utiliser dans certains cas où la vitesse n'est pas primordiale et où son usage donne de la concision au code.

[Zavonen]

Tu sembles sous-entendre que ton code est assurément rapide.

Je ne dis rien de plus que ce que je dis. Il est en O(nlog(n)). Pour peu que le 'sort' integré soit un quicksort (le contraire m'étonnerait). Je ne pense pas qu'on puisse faire mieux mais je n'en suis pas sûr du tout, en tout cas je ne saurais le démontrer. Cela dit, tous lesO( nlog(n)) sont équivalents entre eux mais il y en a qui sont plus équivalents que d'autres (comme dirait Orwell).
En effet il y a un tri suivi d'un balayage simple donc nlog(n)+n équivalent à nlog(n).
Dans les algos que j'ai lus (un peu vite il faut dire) il m'a semblé que certains étaient en n².

Qu'entends-tu par fonctions "avancées" ? Est-ce que cela implique l'utilisation des list comprehensions ?

Entre autres, mais aussi toutes les primitives de manipulation de dictionnaires.

Je ne connaissais pas le mot-clé 'continue'

Python ayant 'emprunté 'break' à C, il y avait des chances qu'il ait fait de même pour son cousin.

[dapounet]

Bonjour,

Je ne dis rien de plus que ce que je dis. Il est en O(nlog(n)). Pour peu que le 'sort' integré soit un quicksort (le contraire m'étonnerait).

C'est le timsort, inventé pour l'occasion.

[Zavonen]

J'aurai aussi appris quelque chose. Je croyais qu'on n'avait rien inventé depuis Hoare.

C'est le timsort, inventé pour l'occasion.

Par la formule de Stirling log(n!) est équivalent à nlog(n) (nlog(n)+klog(n)-n).