15.4. Postscriptum

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.

#Define exceptions
class RomanError(Exception): pass
class OutOfRangeError(RomanError): pass
class NotIntegerError(RomanError): pass
class InvalidRomanNumeralError(RomanError): pass

#Roman numerals must be less than 5000
MAX_ROMAN_NUMERAL = 4999

#Define digit mapping
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))

#Create tables for fast conversion of roman numerals.
#See fillLookupTables() below.
toRomanTable = [ None ]  # Skip an index since Roman numerals have no zero
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"""
    #Save the values in two global tables to convert to and from integers.
    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 ?