Comment dédoubler une liste ou un string ?
Je cherche à dédoubler une liste ou un string
Exemple:
l = [1, 5, 3] => ll = [1, 1, 5, 5, 3, 3]
l = '153' => ll = '115533'
L'objectif étant que ce soit le plus rapide possible (ma liste ou string initiale ayant une taille supérieur à 150000)
Avec une méthode bourrine, je suis à 180ms pour la string et 210 ms pour la liste mais c'est beaucoup trop (il me faudrait ne pas dépasser les 50ms)
Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
## sur une string
toto = 20000 * '1234567890'
res = ''
a = time.clock()
for i in toto: res += i+i
b = time.clock()
print b-a
##sur une liste
toto = 20000 * [1,2,3,4,5,6,7,8,9,0]
res = []
a = time.clock()
for i in toto:
res.append(i)
res.append(i)
b = time.clock()
print b-a |
:merci:
petites optimisations testées avec 2.4
bonsoir tout d'abord deux petites choses :
en ce qui concerne les mesures :
il vaut mieux les effectuer plusieurs fois, on obtient ainsi quelque chose de plus cohérent et beaucoup moins dépendant du reste de l'ordi.
Pour le code :
il n'est pas normal que l'utilisation d'une liste soit plus longue que l'utilisation d'une string.
En effet une string est une sequence immuable, donc le fait de faire s+='new character' entraine obligatoirement la création d'une nouvelle séquence.
Ton souci est au niveau de ton code :
le fait d'écrire res.append à l'intérieur d'une boucle (ici un for) n'est vraiment pas bon pour les performances, car la liste 'res' est réévaluée à chaque itération !
Il faut absolument utiliser un alias tel que alias = res.append et dans ton for
alias(i)
Bon la preuve en image de tout ce que je raconte au dessus :
fichier to_test.py
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
| t_s = 20000 * '1234567890'
t_l = 20000 * [1,2,3,4,5,6,7,8,9,0]
def t_string(seq=t_s):
res = ''
for i in seq:
res += i+i
return res
def t_list_without_alias(seq=t_l):
res = []
for i in seq:
res.append(i)
res.append(i)
return res
def t_list_with_alias(seq=t_l):
res = []
alias=res.append
for i in seq:
alias(i)
alias(i)
return res |
et un petit module testeur.py utilisant le module timit.
Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| import timeit
module='to_test'
f = module + '.t_list_with_alias()'
f1 = module + '.t_string()'
f2 = module + '.t_list_without_alias()'
def footime(s, m=module, n=1):
t = timeit.Timer(s, 'import %s ; reload(%s); gc.enable()' %(m,m))
time = t.timeit(n)
return time
print f, footime(f,n=10)
print f1, footime(f1,n=10)
print f2, footime(f2,n=10) |
Comme tu le vois l'execution de ce module demande d'executer 10 fois chaque fonction afin d'avoir un résultat plus cohérent comme expliqué plus haut.
Voici les résultats d'exécution sur ma machine.
Code:
1
2
3
| to_test.t_list_with_alias() 1.02240005364
to_test.t_string() 1.15563346738
to_test.t_list_without_alias() 1.80934196944 |
Ils confirment les explications données plus haut.
@++
