18.4. 优化字典查找

Soundex 算法的第二步是将字符按特定模式转换为数字。实现此目标的最佳方法是什么？

最明显的解决方案是定义一个字典，其中包含单个字符作为键，其对应的数字作为值，并对每个字符进行字典查找。这就是我们在 soundex/stage1/soundex1c.py（目前为止的最佳结果）中所做的

charToSoundex = {"A": "9",
                 "B": "1",
                 "C": "2",
                 "D": "3",
                 "E": "9",
                 "F": "1",
                 "G": "2",
                 "H": "9",
                 "I": "9",
                 "J": "2",
                 "K": "2",
                 "L": "4",
                 "M": "5",
                 "N": "5",
                 "O": "9",
                 "P": "1",
                 "Q": "2",
                 "R": "6",
                 "S": "2",
                 "T": "3",
                 "U": "9",
                 "V": "1",
                 "W": "9",
                 "X": "2",
                 "Y": "9",
                 "Z": "2"}

def soundex(source):
    # ... input check omitted for brevity ...
    source = source[0].upper() + source[1:]
    digits = source[0]
    for s in source[1:]:
        s = s.upper()
        digits += charToSoundex[s]

您已经对 soundex1c.py 进行了计时；以下是它的性能

C:\samples\soundex\stage1>python soundex1c.py
Woo             W000 14.5341678901
Pilgrim         P426 19.2650071448
Flingjingwaller F452 30.1003563302

这段代码很简单，但它是最佳解决方案吗？对每个字符调用 upper() 似乎效率低下；对整个字符串调用一次 upper() 可能会更好。

然后是增量构建 digits 字符串的问题。像这样增量构建字符串的效率非常低；在内部，Python 解释器需要在每次循环时创建一个新字符串，然后丢弃旧字符串。

不过，Python 擅长处理列表。它可以自动将字符串视为字符列表。并且列表很容易使用字符串方法 join() 再次组合成字符串。

以下是 soundex/stage2/soundex2a.py，它使用 ↦ 和 lambda 将字母转换为数字


def soundex(source):
    # ...
    source = source.upper()
    digits = source[0] + "".join(map(lambda c: charToSoundex[c], source[1:]))

令人惊讶的是，soundex2a.py 并没有更快

C:\samples\soundex\stage2>python soundex2a.py
Woo             W000 15.0097526362
Pilgrim         P426 19.254806407
Flingjingwaller F452 29.3790847719

匿名 lambda 函数的开销抵消了您通过将字符串作为字符列表处理所获得的任何性能提升。

soundex/stage2/soundex2b.py 使用列表推导式而不是 ↦ 和 lambda

    source = source.upper()
    digits = source[0] + "".join([charToSoundex[c] for c in source[1:]])

在 soundex2b.py 中使用列表推导式比在 soundex2a.py 中使用 ↦ 和 lambda 更快，但仍然没有原始代码（在 soundex1c.py 中增量构建字符串）快

C:\samples\soundex\stage2>python soundex2b.py
Woo             W000 13.4221324219
Pilgrim         P426 16.4901234654
Flingjingwaller F452 25.8186157738

是时候采用一种截然不同的方法了。字典查找是一种通用工具。字典键可以是任意长度的字符串（或许多其他数据类型），但在这种情况下，我们只处理单字符键 *和* 单字符值。事实证明，Python 有一个专门用于处理这种情况的函数：string.maketrans 函数。

以下是 soundex/stage2/soundex2c.py

allChar = string.uppercase + string.lowercase
charToSoundex = string.maketrans(allChar, "91239129922455912623919292" * 2)
def soundex(source):
    # ...
    digits = source[0].upper() + source[1:].translate(charToSoundex)

这到底是怎么回事？string.maketrans 在两个字符串之间创建一个转换矩阵：第一个参数和第二个参数。在这种情况下，第一个参数是字符串 ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz，第二个参数是字符串 9123912992245591262391929291239129922455912623919292。看到规律了吗？这与我们使用字典手动设置的转换模式相同。A 映射到 9，B 映射到 1，C 映射到 2，依此类推。但它不是字典；它是一种特殊的数据结构，您可以使用字符串方法 translate 访问它，该方法根据 string.maketrans 定义的矩阵将每个字符转换为相应的数字。

timeit 显示，soundex2c.py 比定义字典、循环遍历输入和增量构建输出要快得多

C:\samples\soundex\stage2>python soundex2c.py
Woo             W000 11.437645008
Pilgrim         P426 13.2825062962
Flingjingwaller F452 18.5570110168

你不可能做得更好了。Python 有一个专门的函数可以完成您想做的事情；使用它并继续前进。

示例 18.4. 目前为止的最佳结果：`soundex/stage2/soundex2c.py`


import string, re

allChar = string.uppercase + string.lowercase
charToSoundex = string.maketrans(allChar, "91239129922455912623919292" * 2)
isOnlyChars = re.compile('^[A-Za-z]+$').search

def soundex(source):
    if not isOnlyChars(source):
        return "0000"
    digits = source[0].upper() + source[1:].translate(charToSoundex)
    digits2 = digits[0]
    for d in digits[1:]:
        if digits2[-1] != d:
            digits2 += d
    digits3 = re.sub('9', '', digits2)
    while len(digits3) < 4:
        digits3 += "0"
    return digits3[:4]

if __name__ == '__main__':
    from timeit import Timer
    names = ('Woo', 'Pilgrim', 'Flingjingwaller')
    for name in names:
        statement = "soundex('%s')" % name
        t = Timer(statement, "from __main__ import soundex")
        print name.ljust(15), soundex(name), min(t.repeat())

深入 Python

18.4. 优化字典查找

示例 18.4. 目前为止的最佳结果：soundex/stage2/soundex2c.py

示例 18.4. 目前为止的最佳结果：`soundex/stage2/soundex2c.py`