18.5. 優化列表操作

18.5. 優化列表操作

Soundex 算法的第三步是去除連續重復字符。怎樣做是最佳方法？

這里是我們目前在 soundex/stage2/soundex2c.py 中的代碼：

    digits2 = digits[0]
    for d in digits[1:]:
        if digits2[-1] != d:
            digits2 += d

這里是 soundex2c.py 的性能表現：

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

第一件事是考慮，考察在循環的每一輪都檢查 digits[-1] 是否有效率。列表索引代價大嗎？如果把上一個數字存在另外的變量中以便檢查是否會獲益？

這里的 soundex/stage3/soundex3a.py 將回答這個問題：

    digits2 = ''
    last_digit = ''
    for d in digits:
        if d != last_digit:
            digits2 += d
            last_digit = d

soundex3a.py 并不比 soundex2c.py 運行得快多少，而且甚至可能更會慢些 (差異還沒有大到可以確信這一點)：

C:\samples\soundex\stage3>python soundex3a.py
Woo             W000 11.5346048171
Pilgrim         P426 13.3950636184
Flingjingwaller F452 18.6108927252

為什么 soundex3a.py 不更快呢？其實 Python 的索引功能恰恰很有效。重復使用 digits2[-1] 根本沒什么問題。另一方面，手工保留上一個數字意味著我們每存儲一個數字都要為兩個變量賦值，這便抹殺了我們避開索引查找所帶來的微小好處。

讓我們從本質上不同的方法來思考。如果可以把字符串當作字符列表來對待，那么使用列表遍歷遍尋列表便成為可能。問題是代碼需要使用列表中的上一個字符，而且使用列表遍歷做到這一點并不容易。

但是，使用內建的 range() 函數創建一個索引數字構成的列表是可以的。使用這些索引數字一步步搜索列表并拿出與前面不同的字符。這樣將使你得到一個字符串列表，使用字符串方法 join() 便可重建字符串。

這便是 soundex/stage3/soundex3b.py：

    digits2 = "".join([digits[i] for i in range(len(digits))
                       if i == 0 or digits[i-1] != digits[i]])

這樣快了嗎？一個字，否。

C:\samples\soundex\stage3>python soundex3b.py
Woo             W000 14.2245271396
Pilgrim         P426 17.8337165757
Flingjingwaller F452 25.9954005327

有可能因為目前的這些方法都是 “字符串中心化” 的。Python 可以通過一個命令把一個字符串轉化為一個字符列表：list('abc') 返回 ['a', 'b', 'c']。更進一步，列表可以被很快地就地改變。與其一磚一瓦地建造一個新的列表 (或者字符串)，為什么不選擇操作列表的元素呢？

這便是 soundex/stage3/soundex3c.py，就地修改列表去除連續重復元素：

    digits = list(source[0].upper() + source[1:].translate(charToSoundex))
    i=0
    for item in digits:
        if item==digits[i]: continue
        i+=1
        digits[i]=item
    del digits[i+1:]
    digits2 = "".join(digits)

這比 soundex3a.py 或 soundex3b.py 快嗎？不，實際上這是目前最慢的一種方法^[16]：

C:\samples\soundex\stage3>python soundex3c.py
Woo             W000 14.1662554878
Pilgrim         P426 16.0397885765
Flingjingwaller F452 22.1789341942

我們在這兒除了試用了幾種 “聰明” 的技術，根本沒有什么進步。到目前為止最快的方法就是最直接的原始方法 (soundex2c.py)。有時候聰明未必有回報。

例 18.5. 目前的最佳結果：`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

^[16]soundex3c.py 比 soundex3b.py 快。――譯注

深入 Python :Dive Into Python 中文版