18.3. 優化正則表達式

18.3. 優化正則表達式

Soundex 函數的第一件事是檢查輸入是否是一個空字符串。怎樣做是最好的方法？

如果你回答 “正則表達式”，坐在角落里反省你糟糕的直覺。正則表達式幾乎永遠不是最好的答案，而且應該被盡可能避開。這不僅僅是基于性能考慮，而是因為調試和維護都很困難，當然性能也是個原因。

這是 soundex/stage1/soundex1a.py 檢查 source 是否全部由字母構成的一段代碼，至少是一個字母 (而不是空字符串)：

    allChars = string.uppercase + string.lowercase
    if not re.search('^[%s]+$' % allChars, source):
        return "0000"

soundex1a.py 表現如何？為了方便，__main__ 部分包含了一段代碼：調用 timeit 模塊，為三個不同名字分別建立測試，依次測試，并顯示每個測試的最短耗時：


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

那么，應用正則表達式的 soundex1a.py 表現如何呢？

C:\samples\soundex\stage1>python soundex1a.py
Woo             W000 19.3356647283
Pilgrim         P426 24.0772053431
Flingjingwaller F452 35.0463220884

正如你預料，名字越長，算法耗時就越長。有幾個工作可以令我們減小這個差距 (使函數對于長輸入花費較短的相對時間) 但是算法的本質決定它不可能每次運行時間都相同。

另一點應銘記于心的是，我們測試的是有代表性的名字樣本。Woo 是個被縮短到單字符并補零的小樣本；Pilgrim 是個夾帶著特別字符和忽略字符的平均長度的正常樣本；Flingjingwaller 是一個包含連續重復字符并且特別長的樣本。其它的測試可能同樣有幫助，但它們已經很好地代表了不同的樣本范圍。

那么那個正則表達式如何呢？嗯，缺乏效率。因為這個表達式測試不止一個范圍的字符 (A-Z 的大寫范圍和 a-z 的小寫字母范圍)，我們可以使用一個正則表達式的縮寫語法。這便是 soundex/stage1/soundex1b.py:

    if not re.search('^[A-Za-z]+$', source):
        return "0000"

timeit 顯示 soundex1b.py 比 soundex1a.py 稍微快一些，但是沒什么令人激動的變化：

C:\samples\soundex\stage1>python soundex1b.py
Woo             W000 17.1361133887
Pilgrim         P426 21.8201693232
Flingjingwaller F452 32.7262294509

在第 15.3 節 “重構” 中我們看到正則表達式可以被編譯并在重用時以更快速度獲得結果。因為這個正則表達式在函數中每次被調用時都不變化，我們可以編譯它一次并使用被編譯的版本。這便是 soundex/stage1/soundex1c.py：

isOnlyChars = re.compile('^[A-Za-z]+$').search
def soundex(source):
    if not isOnlyChars(source):
        return "0000"

soundex1c.py 中使用被編譯的正則表達式產生了顯著的提速：

C:\samples\soundex\stage1>python soundex1c.py
Woo             W000 14.5348347346
Pilgrim         P426 19.2784703084
Flingjingwaller F452 30.0893873383

但是這樣的優化是正路嗎？這里的邏輯很簡單：輸入 source 應該是非空，并且需要完全由字母構成。如果編寫一個循環查看每個字符并且拋棄正則表達式，是否會更快些？

這便是 soundex/stage1/soundex1d.py：

    if not source:
        return "0000"
    for c in source:
        if not ('A' <= c <= 'Z') and not ('a' <= c <= 'z'):
            return "0000"

這個技術在 soundex1d.py 中恰好不及編譯后的正則表達式快 (盡管比使用未編譯的正則表達式快^[14])：

C:\samples\soundex\stage1>python soundex1d.py
Woo             W000 15.4065058548
Pilgrim         P426 22.2753567842
Flingjingwaller F452 37.5845122774

為什么 soundex1d.py 沒能更快？答案來自 Python 的編譯本質。正則表達式引擎以 C 語言編寫，被編譯后則能本能地在你的計算機上運行。另一方面，循環是以 Python 編寫，要通過 Python 解釋器。盡管循環相對簡單，但沒能簡單到補償花在代碼解釋上的時間。正則表達式永遠不是正確答案……但例外還是存在的。

恰巧 Python 提供了一個晦澀的字符串方法。你有理由不了解它，因為本書未曾提到它。這個方法便是 isalpha()，它檢查一個字符串是否只包含字母。

這便是 soundex/stage1/soundex1e.py：

    if (not source) and (not source.isalpha()):
        return "0000"

在 soundex1e.py 中應用這個特殊方法我們能得到多少好處? 很多。

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

例 18.3. 目前為止最好的結果：`soundex/stage1/soundex1e.py`


import string, re

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):
    if (not source) and (not source.isalpha()):
        return "0000"
    source = source[0].upper() + source[1:]
    digits = source[0]
    for s in source[1:]:
        s = s.upper()
        digits += charToSoundex[s]
    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

^[14]注意 soundex1d.py 在后兩個測試點上都比 soundex1b.py 慢，這點與作者所說的矛盾。本章另還有多處出現了正文與測試結果矛盾的地方，每個地方都會用譯注加以說明。這個 bug 將在下個版本中得到修正。――譯注

深入 Python :Dive Into Python 中文版