Algorithme de Luhn – Implémentation Python
Pour faire suite à mes posts Algorithme de Luhn – Implémentation C++,
Algorithme de Luhn – Implémentation C# et Algorithme de Luhn – Implémentation C, voici une version de l’agorithme implémenté en Python.
Dans la solution que je propose ci-dessous, je suis arrivé au résultat suivant :
- le code comptabilisé est constitué des 88 caractères significatifs de la suite d’instructions :
s,i=0,16 while i>0: i-=1 v=ord(l[15-i])-48<<i%2 if(v<9): s+=v-9 else: s+=v return s%10<1 - le temps d’exécution mesuré pour 1000000 d’itérations est de 11,58 secondes sur un Intel Core 2 Duo cadencé à 2,13 Ghz sous Ubuntu 9.04.
Comparé à l’implémentation en C, le code comptabilisé augmente de 20 caractères et le temps d’exécution mesuré augmente de 11,42 secondes. Le code a été interprété par Python 2.6.2.
Si vous avez des commentaires, des suggestions ou si vous avez une solution plus compacte ou plus rapide, n’hésitez pas à m’en faire part.
#!/usr/bin/python
# -*- coding: latin-1 -*-
import time
def luhn( l ):
# début du code comptabilisé
s, i = 0, 16
while i > 0:
i -= 1
v = ord( l[ 15 - i ] ) - 48 << i % 2
if ( v > 9 ):
s += v - 9
else:
s += v
return s % 10 < 1
# fin du code comptabilisé
def main():
start = time.time()
# début du temps d'exécution mesuré
l = 1000000L
while l > 0:
l -= 1
luhn( "4970100000300521" )
# fin du temps d'exécution mesuré
end = time.time()
print "Le temps d'exécution de la fonction est de %.2f secondes.\n"%( end - start )
Votre mesure du temps d’execution englobe celui de l’execution d’une boucle, qui peut pénaliser (indument dans ce cas) un langage (semi)interprété.
Pour retablir le sentiment d’avoir été traité avec équité chez tous les utilisateurs de langage interpreté (en tous cas, ceux qui ont besoin d’évaluation des temps) je propose de rajouter une seconde boucle presque vide de meme longueur.
De toutes façon, ça peut être interessant de connaître ce temps et ne remet pas en cause la façon de mesurer le temps d’execution d’un algorithme ….
startvide = time.time()
# début mesure du temps d’exécution d’une boucle vide
nombre = 1000000L # l peut être confondu avec 1 -un-
while nombre >0:
nombre-=1 #la boucle vide, qui peut pénaliser
finbouclevide = time.time()
Par dbrion1 le 18 sept 2009
@dbrion1: Je viens de faire le test en rajoutant le code que vous proposez après la dernière instruction « print » de la fonction « main ».
J’ai également fait l’essai en remplaçant « while l>0: » par « for i in range(1L,1000000L): ».
Le temps d’exécution du code de gestion de la boucle cumulé avec celui de 1000000 décrémentations est respectivement de 0,30 secondes pour la version avec le « while » et de 0,25 secondes avec le « for ».
Dans les deux cas, c’est tout à fait marginal.
Par Bernard le 18 sept 2009
D’accord que c’est marginal, mais c’était
pour la bonne forme (et éviter tout risque de pinaillage).
Et quand “on” a une boucle avec très peu d’instructions dedans, il y a des gens – dont je ne suis pas – qui sont très contents de gagner 10% par ci par là….. ce qui semble réalisable en passant d’une boucle avec while à une boucle dans un intervalle…
Les gains à espèrer viendraient donc d’un appel “à” une dll/so ,( en simplifiant plus qu’hâtivement); ceci est un reflexe que j’espère naturel chez les riens, (chez les perliens, pythoniens , je n’en sais ….rien) : dés que ça devient lent, au point d’être gênant, ils réecrivent les bouts de code (une fois identifiés comme lents…. ce n’est pas un mince problème, sans profileur ou …. sans bon sens) en C, C++, Fortran {dans ce cas -manipulation sur des caractères- et ce contexte (solutions déjà en C et C++ ce serait une erreur), suivant leurs goûts, leurs talents ou la nature du problème….
avec un gain d’un facteur 50…. (je laisse un peu de marge pour l’appel de fonction).
Ceci nécessite de gérer 2 codes dans des sources distincts.
Par dbrion1 le 18 sept 2009