18.4. 优化字典查找

优质

小牛编辑

122浏览

2023-12-01

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，通过 map 和 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 使用了一个列表遍历来替代 map 和 lambda：

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

在 soundex2b.py 中使用列表遍历比 soundex2a.py 中使用 map 和 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())