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 12.6070768771
Pilgrim         P426 14.4033353401
Flingjingwaller F452 19.7774882003

首先要考虑的是，每次循环都检查 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 快吗？不，事实上，这是迄今为止最慢的方法

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)
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.5. 优化列表操作

示例 18.5. 迄今为止的最佳结果：soundex/stage2/soundex2c.py

示例 18.5. 迄今为止的最佳结果：`soundex/stage2/soundex2c.py`