Zanurkuj w Pythonie/Postscript

Sprytny czytelnik po przeczytaniu poprzedniego podrozdziału byłby w stanie jeszcze bardziej polepszyć kod programu. Największym bowiem problemem (i dziurą (?) wydajnościową) programu w obecnym kształcie jest wyrażenie regularne, wymagane ze względu na to, że nie ma innego sensownego sposobu weryfikacji poprawności liczby w zapisie rzymskim. Tych liczb jest jednak tylko 5000; dlaczego by więc nie zbudować tablicy przeszukiwania tylko raz, a później po prostu z niej korzystać? Ten pomysł wyda się jeszcze lepszy, gdy zdamy sobie sprawę, że w ogóle nie musimy korzystać z wyrażeń regularnych. Skoro można zbudować tablicę przeszukiwań służącą do konwersji wartości liczbowych w ich rzymską reprezentację, to można również zbudować tablicę odwrotną do przekształcania liczb rzymskich w ich wartość liczbową.

Najlepsze zaś jest to, że ów sprytny czytelnik miałby już do swojej dyspozycji pełen zestaw testów jednostkowych. Choć zmodyfikowałby połowę kodu w module, to testy pozostałyby takie same, a więc mógłby on udowodnić, że kod po zmianach działa tak samo, jak wcześniej.

Przykład 15.17. roman9.py

Plik jest dostępny w katalogu in py/roman/stage9/ wewnątrz katalogu examples.

Jeśli jeszcze tego nie zrobiliście, możecie pobrać ten oraz inne przykłady używane w tej książce stąd.

#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()

A jak szybki jest taki kod?

Przykład 15.18. Wyjście programu romantest9.py testującego roman9.py

.............
----------------------------------------------------------------------
Ran 13 tests in 0.791s

OK

Pamiętajmy, że najlepszym wynikiem, jaki udało nam się do tej pory uzyskać, był czas 3.315 sekund dla 13 testów. Oczywiście, to porównanie nie jest zbyt uczciwe, ponieważ w tej wersji moduł będzie się dłużej importował (będą generowane tablice przeszukiwań). Jednak ze względu na to, ze importowanie modułu odbywa się jednokrotnie, czas, jaki ono zajmuje, można uznać za pomijalny.

Morał z tej historii?

• Prostota jest cnotą.
• Szczególnie wtedy, gdy chodzi o wyrażenia regularne.
• A testy jednostkowe dają nam pewność i odwagę do refaktoryzacji w dużej skali... nawet, jeśli to nie my pisaliśmy oryginalny kod.