optimisation découpage de chaine

Version imprimable

27/11/2008, 17h48
kazh75

optimisation découpage de chaine
Bonjour,
Je cherche à découper une chaine "5379626173" en une liste
list = [53,79,62,61,73].

Voici le code que j'utilise mais je pense qu'il existe plus simple et/ou plus rapide.
Code:

1 2 3 4 5 6 mystring="5379626173" mylist = [] for i in range(0,len(mystring),2): j = i + 2 mylist.append(mystring[i:j])
Merci d'avance pour votre aide.
27/11/2008, 19h10
tyrtamos
Bonjour,

Il y a peut-être encore plus court, mais commence déjà par ça:
Code:

1 2 mylist = [mystring[i:i+2] for i in range(0,len(mystring),2)]
Tyrtamos

Code:

1
2
3
 
In [9]: re.findall(r'\d{2}', '5379626173')
Out[9]: ['53', '79', '62', '61', '73']

Si la chaine est de longueur invariable

Il faut transférer de l'exécution du programme dans l'écriture du programme une partie du travail qui doit être effectué, et à ce moment là on gagne en vitesse.

Code:

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
rom timeit import Timer
import re
 
c = "5379626173"
repet = 4 # nombre de calculs de temps effectues
ITERATIONS = 1000000 # nombre d'iterations de la fonction pour un calcul de temps
 
def gnuv(c):
    lgnuv = re.findall(r'\d{2}', c)
    return lgnuv
 
def alex(c):
    mylist = []
    for i in range(0,10,2):
        j = i + 2
        mylist.append(c[i:j])
    return mylist
 
def tyrt(string):
    list = [c[i:i+2] for i in range(0,10,2)]
    return list
 
def eyqu(c):
    li = [c[0:2],c[2:4],c[4:6],c[6:8],c[8:10]]
    return li
 
 
 
Timergnuv = Timer('alex(c)','from __main__ import alex, c')
tgnuv = Timergnuv.repeat(repet,ITERATIONS)
tmoy = 0
for i in tgnuv:
    tmoy = tmoy + i
tmoy = tmoy/repet
print "Avec  re.findall(r'\d{2}', c)\n"
for i in [float(str(t)[0:5]) for t in tgnuv]:
    print '\t',i,
print '\n\tmoyenne =',float(str(tmoy)[0:5])
print '\tminimum =',float(str(min(tgnuv))[0:5])
print'\n\n'
 
 
Timeralex = Timer('alex(c)','from __main__ import alex, c')
talex = Timeralex.repeat(repet,ITERATIONS)
tmoy = 0
for i in talex:
    tmoy = tmoy + i
tmoy = tmoy/repet
print 'Avec  mylist.append(c[i:j])\n'
for i in [float(str(t)[0:5]) for t in talex]:
    print '\t',i,
print '\n\tmoyenne =',float(str(tmoy)[0:5])
print '\tminimum =',float(str(min(talex))[0:5])
print'\n\n'
 
Timertyrt = Timer('tyrt(c)','from __main__ import tyrt, c')
ttyrt = Timertyrt.repeat(repet,ITERATIONS)
tmoy = 0
for i in ttyrt:
    tmoy = tmoy + i
tmoy = tmoy/repet
print 'Avec  list = [c[i:i+2] for i in range(0,10,2)]\n'
for i in [float(str(t)[0:5]) for t in ttyrt]:
    print '\t',i,
print '\n\tmoyenne =',float(str(tmoy)[0:5])
print '\tminimum =',float(str(min(ttyrt))[0:5])
print'\n\n'
 
Timereyqu = Timer('eyqu(c)','from __main__ import eyqu, c')
teyqu = Timereyqu.repeat(repet,ITERATIONS)
tmoy = 0
for i in teyqu:
    tmoy = tmoy + i
tmoy = tmoy/repet
print 'Avec  li = [c[0:2],c[2:4],c[4:6],c[6:8],c[8:10]]\n'
for i in [float(str(t)[0:5]) for t in teyqu]:
    print '\t',i,
print '\n\tmoyenne =',float(str(tmoy)[0:5])
print '\tminimum =',float(str(min(teyqu))[0:5])
print'\n\n\n'

Résultat:
il s'agit de temps d'exécution de 1000000 d'itérations de calcul de la liste voulue, en secondes

Code:

1
2
3
4
Avec  re.findall(r'\d{2}', c)
	34.14 	34.32 	32.78 	31.21 
	moyenne = 33.11
	minimum = 31.21

Code:

1
2
3
4
Avec  mylist.append(c[i:j])
	29.37 	34.1 	33.73 	34.12 
	moyenne = 32.83
	minimum = 29.37

Code:

1
2
3
4
Avec  list = [c[i:i+2] for i in range(0,10,2)]
	26.03 	25.6 	25.57 	26.33 
	moyenne = 25.88
	minimum = 25.57

Code:

1
2
3
4
Avec  li = [c[0:2],c[2:4],c[4:6],c[6:8],c[8:10]]
	8.537 	8.469 	8.603 	8.685 
	moyenne = 8.573
	minimum = 8.469

Si la chaine est de longueur variable

Il suffit de créer une fonction du genre:

Code:

1
2
3
4
5
def f(c):
    if len(c)==6:
        return [[c[0:2],c[2:4],c[4:6]]
    if len(c)==8:
        return [[c[0:2],c[2:4],c[4:6],c[6:8]]

28/11/2008, 10h57
kazh75

Réponse impréssionnante !
Merci pour ce travail de recherche et d'analyse que je n'aurai pas pu faire moi même mais que je conserve pour exemple.

Citation:
Envoyé par eyquem
Il suffit de créer une fonction du genre:
Code:

1 2 3 4 5 def f(c): if len(c)==6: return [[c[0:2],c[2:4],c[4:6]] if len(c)==8: return [[c[0:2],c[2:4],c[4:6],c[6:8]]
Pas super si on ne connaît pas les longueurs possible de c

Il y a moyen d'accélérer mon code en pré-compilant l'expression régulière:

Code:

1
2
3
4
5
6
7
8
9
10
 
>>> t1 = timeit.Timer(stmt='re.findall(r"\d{2}", "5379626173")', setup='import re')
 
>>> t2 = timeit.Timer(stmt='r.findall("5379626173")', setup='import re; r = re.compile(r"\d{2}")')
 
>>> t1.timeit()
10.813745021820068
 
>>> t2.timeit()
3.7433810234069824

phosphoration

Ton intéressante remarque, GnuVince, m'a fait réflechir, ce qui m'a permis de comprendre que des tests de vitesse ne sont instructifs que s'ils sont en rapport avec ce qui doit être fait par et dans un programme. Mes tests, ainsi que ta remarque d'ailleurs, enferment des notions sous-entendues qui nécessitent d'être explicitées.

Je ne crois pas qu'il soit exact d'écrire que ton code est accéléré en pré-compilant l'expression régulière. Il me semble qu'en réalité, que ce soit avec re.findall(r"\d{2}", "5379626173")
ou avec r = re.compile(r"\d{2}") suivi de r.findall("5379626173")
il y a toujours une compilation à un moment ou à un autre puisque findall a besoin d'une regex pour fonctionner, et que donc, si tu obtiens un temps d'exécution inférieur avec la deuxième manière, c'est parce que tu as sorti implicitement la compilation de regex de la boucle de mesure du temps de x iterations. :?

Je me suis alors aperçu que j'avais fait l'inverse: j'ai inclus implicitement dans mon test de vitesse la compilation de la regex dans la boucle de mesure puisque j'écris re.findall(r'\d{2}', c) dans def gnuv(c) 8O

En fait, ni l'une ni l'autre manière ne se justifie en elle-même, seul ce qu'on veut faire dans un programme le permet:

- s'il s'agit d'exécuter une seule fois le découpage de chaine = "5379626173" dans un programme, il faut comparer
lgnuv = re.findall(r'\d{2}', c)
et
li = [c[0:2],c[2:4],c[4:6],c[6:8],c[8:10]]

- si on découpe plusieurs fois des chaines selon le même schéma, le programme est effectivement optimisé si on pré-compile une regex avant ses utilisations répétées, et dans ce cas il faut précompiler la regex avant de comparer
lgnuv2 = reg.findall(c)
et
li = [c[0:2],c[2:4],c[4:6],c[6:8],c[8:10]]

Au passage, j'ai compris porquoi il existe deux façons d'utiliser findall, ça dépend du contexte et de ce qu'on veut faire. J'avais encore pas pigé la raison de l'existence de deux findall.

Même dans le deuxième cas avec précompilation, GnuVince, le recours aux regex reste plus long que le découpage "aux ciseaux" c[0:2],c[2:4],etc
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 Avec repeat(4,10000) sur re.findall(r'\d{2}', c) de gnuv TMIN = 0.427 tmoy = 0.43 (tmax-tmin/2)/tmoy = 1.09 % Avec repeat(4,10000) sur REprecompilee.findall(c) de gnuv2 TMIN = 0.264 tmoy = 0.309 (tmax-tmin/2)/tmoy = 14.4 % Avec repeat(4,10000) sur mylist.append(c[i:j] de alex) TMIN = 0.242 tmoy = 0.243 (tmax-tmin/2)/tmoy = 0.32 % Avec repeat(4,10000) sur list = [c[i:i+2] for i in range(0,10,2)] de tyrt TMIN = 0.179 tmoy = 0.18 (tmax-tmin/2)/tmoy = 0.18 % Avec repeat(4,10000) sur li = [c[0:2],c[2:4],c[4:6],c[6:8],c[8:10]] de eyqu TMIN = 0.062 tmoy = 0.063 (tmax-tmin/2)/tmoy = 0.31 %
Des cas que j'ai vus jusqu'à présent en Python, j'ai retiré l'idée qu'aucune méthode ne peut aller aussi vite pour faire un découpage simple de chaine que ce découpage "aux ciseaux".

Quant au premier cas, on me dira, et je serai d'accord, que vue la vitesse que prend d'effectuer une seule exécution d'une des méthodes proposées (entre 6 et 40 millionième de secondes), ça n'est pas la peine de se casser la tête à choisir la meilleure en temps d'éxecution.
À ce moment là, il faut se demander sur quelle raison implicite repose le choix d'une méthode ou d'une autre, puisque ce n'est plus le critère de la rapidité.
Pour ma part je préfère utiliser des outils simples pour des tâches simples. Mais j'adore les list comprehension et les problèmes de regex aussi, c'est plus rigolo que des découpages de chaine aux ciseaux, j'en conviens.

J'ai réécrit mon petit programme de mesure des temps pour prendre en compte la deuxième manière de GnuVince et changer la présentation des résultats.
Code:

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 from timeit import Timer import re chaine = "5379626173" repet = 4 # nombre de calculs de temps effectues ITERATIONS = 10000 # nombre d'iterations de la fonction pour un calcul de temps reg = re.compile(r'\d{2}') def sortie(tliste): tmoy = sum(tliste)/repet print '\tTMIN =',float(str(min(tliste))[0:5]),' tmoy =',float(str(tmoy)[0:5]),' (tmax-tmin/2)/tmoy =',float( str(100*(max(tliste)-min(tliste))/tmoy/2)[0:4]),'%' print def gnuv(c): lgnuv = re.findall(r'\d{2}', c) return lgnuv def gnuv2(c): lgnuv2 = reg.findall(c) return lgnuv2 def alex(c): mylist = [] for i in range(0,10,2): j = i + 2 mylist.append(c[i:j]) return mylist def tyrt(c): list = [c[i:i+2] for i in range(0,10,2)] return list def eyqu(c): li = [c[0:2],c[2:4],c[4:6],c[6:8],c[8:10]] return li tgnuv = Timer('gnuv(chaine)','from __main__ import gnuv, chaine').repeat(repet,ITERATIONS) print 'Avec repeat('+str(repet)+','+str(ITERATIONS)+") sur re.findall(r'\d{2}', c) de gnuv" sortie(tgnuv) tgnuv2 = Timer('gnuv2(chaine)','from __main__ import gnuv2, chaine').repeat(repet,ITERATIONS) print 'Avec repeat('+str(repet)+','+str(ITERATIONS)+") sur REprecompilee.findall(c) de gnuv2" sortie(tgnuv2) talex = Timer('alex(chaine)','from __main__ import alex, chaine').repeat(repet,ITERATIONS) print 'Avec repeat('+str(repet)+','+str(ITERATIONS)+") sur mylist.append(c[i:j] de alex)" sortie(talex) ttyrt = Timer('tyrt(chaine)','from __main__ import tyrt, chaine').repeat(repet,ITERATIONS) print 'Avec repeat('+str(repet)+','+str(ITERATIONS)+") sur list = [c[i:i+2] for i in range(0,10,2)] de tyrt" sortie(ttyrt) teyqu = Timer('eyqu(chaine)','from __main__ import eyqu, chaine').repeat(repet,ITERATIONS) print 'Avec repeat('+str(repet)+','+str(ITERATIONS)+") sur li = [c[0:2],c[2:4],c[4:6],c[6:8],c[8:10]] de eyqu" sortie(teyqu)