18.4. 優化字典查找

18.4. 優化字典查找

Soundex 算法的第二步是依照特定規則將字符轉換為數字。做到這點最好的方法是什么？

最明顯的解決方案是定義一個以單字符為鍵并以所對應數字為值的字典，以字典查找每個字符。這便是 soundex/stage1/soundex1e.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]

你已經為 soundex1e.py 計時，這便是其表現：

C:\samples\soundex\stage1>python soundex1c.py
Woo             W000 13.5069504644
Pilgrim         P426 18.2199394057
Flingjingwaller F452 28.9975225902

這段代碼很直接，但它是最佳解決方案嗎？為每個字符分別調用 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 快，但還沒有最初的代碼快 (soundex1e.py 中一磚一瓦的構建字符串^[15])：

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)

def soundex(source):
    if (not source) or (not source.isalpha()):
        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())

Footnotes

^[15]事實恰好相反，soundex2b.py 在每個點上都快于 soundex1e.py。――譯注

深入 Python :Dive Into Python 中文版