Un lecteur astucieux a lu la section précédente et l’a amené au
niveau supérieur. Le point le plus compliqué (et pesant le plus sur
les performances) du programme tel qu’il est écrit actuellement est
l’expression régulière, qui est nécessaire puisque nous n’avons pas
d’autre moyen de subdiviser un nombre romain. Mais il n’y a que 5000
nombres romains, pourquoi ne pas construire une table de référence une
fois, puis simplement la lire ? Cette idée est encore meilleure quand
on réalise qu’il n’y a pas besoin d’utiliser les expressions régulière
du tout. Au fur et à mesure que l’on construit la table de référence
pour convertir les entiers en nombres romains, on peut construire la
table de référence inverse pour convertir les nombres romains en
entiers.
Et le meilleur de tout, c’est que nous avons déjà un jeu complet
de tests unitaires. Le lecteur a modifié la moitié du code du module,
mais les tests unitaires sont restés les mêmes, ce qui lui a permis de
prouver que son code fonctionnait tout aussi bien que l’original.
Exemple 15.17. roman9.py
Ce fichier est disponible dans le sous-répertoire py/roman/stage9/ du répertoire des exemples.
Si vous ne l’avez pas déjà fait, vous pouvez télécharger cet exemple ainsi que les autres exemples du livre.
class RomanError(Exception): pass
class OutOfRangeError(RomanError): pass
class NotIntegerError(RomanError): pass
class InvalidRomanNumeralError(RomanError): pass
MAX_ROMAN_NUMERAL = 4999
romanNumeralMap = (('M', 1000),
('CM', 900),
('D', 500),
('CD', 400),
('C', 100),
('XC', 90),
('L', 50),
('XL', 40),
('X', 10),
('IX', 9),
('V', 5),
('IV', 4),
('I', 1))
toRomanTable = [ None ]
fromRomanTable = {}
def toRoman(n):
"""convert integer to Roman numeral"""
if not (0 < n <= MAX_ROMAN_NUMERAL):
raise OutOfRangeError, "number out of range (must be 1..%s)" % MAX_ROMAN_NUMERAL
if int(n) <> n:
raise NotIntegerError, "non-integers can not be converted"
return toRomanTable[n]
def fromRoman(s):
"""convert Roman numeral to integer"""
if not s:
raise InvalidRomanNumeralError, "Input can not be blank"
if not fromRomanTable.has_key(s):
raise InvalidRomanNumeralError, "Invalid Roman numeral: %s" % s
return fromRomanTable[s]
def toRomanDynamic(n):
"""convert integer to Roman numeral using dynamic programming"""
result = ""
for numeral, integer in romanNumeralMap:
if n >= integer:
result = numeral
n -= integer
break
if n > 0:
result += toRomanTable[n]
return result
def fillLookupTables():
"""compute all the possible roman numerals"""
for integer in range(1, MAX_ROMAN_NUMERAL + 1):
romanNumber = toRomanDynamic(integer)
toRomanTable.append(romanNumber)
fromRomanTable[romanNumber] = integer
fillLookupTables()
Alors, est-ce que c’est rapide ?
Exemple 15.18. Sortie de romantest9.py avec roman9.py
.............
----------------------------------------------------------------------
Ran 13 tests in 0.791s
OK
Rappelez-vous que la meilleure performance que nous avons obtenu
dans la version originale était 13 tests en 3,315 secondes. Bien sûr, ce
n’est pas une comparaison entièrement juste, puisque cette version
prendra plus de temps à importer (lorsqu’elle remplit les tables de
référence). Mais comme l’importation n’est faite qu’une seule fois, c'est
négligeable au bout du compte.
La morale de l’histoire ?
- La simplicité est une vertu.
- Particulièrement avec les expressions régulières.
- Les tests unitaires vous donnent la confiance de conduire des
refactorisations à grande échelle... même si vous n’avez pas écrit
le code originel.
