15.4. 后记

聪明的读者在学习前一节时想得会更深入一层。现在写的这个程序中最令人头痛的性能负担是正则表达式,但它是必需的,因为没有其它方法来识别罗马数字。但是,它们只有 5000 个,为什么不一次性地构建一个查询表来读取?不必用正则表达式凸现了这个主意的好处。你建立了整数到罗马数字查询表的时候,罗马数字到整数的逆向查询表也构建了。

更大的好处在于,你已经拥有一整套完全的单元测试。你修改了多半的代码,但单元测试还是一样的,因此你可以确定你的新代码与来的代码一样可以正常工作。

例 15.17. roman9.py

这个文件可以在例子目录下的 py/roman/stage9/ 目录中找到。

如果您还没有下载本书附带的样例程序, 可以 下载本程序和其他样例程序

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

这样有多快呢?

例 15.18. 用 romantest9.py 测试 roman9.py 的结果


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

OK

还记得吗?你原有版本的最快速度是 13 个测试耗时 3.315 秒。当然,这样的比较不完全公平,因为这个新版本需要更长的时间来导入 (当它填充查询表时)。但是导入只需一次,在运行过程中可以忽略。

这个重构的故事的寓意是什么?