Python 研究(Dive Into Python)

lastwinner

但是，Python 擅长于列表。 可以自动地将字符串作为列表来对待。而且使用 join() 方法可以很容易地将列表合并成字符串。

这便是 soundex/stage2/soundex2a.py，通过 map 和 lambda 把所有字母转换为数字：


[PHP]def soundex(source):
    # ...
    source = source.upper()
    digits = source[0] + "".join(map(lambda c: charToSoundex[c], source[1:]))

[/PHP]

lastwinner

太震惊了， 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:]])

lastwinner

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

lastwinner

这儿在干什么？ 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 有一个特殊函数，通过使用它做到了一个和你的工作差不多的事情。就用它并继续吧！

lastwinner

例 18.4. 目前的最佳结果：soundex/stage2/soundex2c.py
[PHP] 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())
[/PHP]

lastwinner

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

lastwinner

第一件事是考虑，考察在循环的每一轮都检查 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] 根本没什么问题。 另一方面，手工另外保留上一个数字为另外的变量意味着我们存储的每个数字的 两个 变量赋值，这便抹杀了我们避开索引查找所带来的微小好处。

lastwinner

让我们从本质上不同的方法来思考。如果可以把字符串当作字符列表来对待，那么使用列表遍历遍寻列表便成为可能。问题是代码需要使用列表中的上一个字符，而且使用列表遍历做到这一点并不容易。

但是，使用内建的 range() 函数创建一个索引数字构成的列表是可以的。 使用这些索引数字一步步搜索列表并拿出与前面不同的字符。 这样将使你得到一个字符串列表，使用字符串方法 join() 便可重建字符串。

这便是 soundex/stage3/soundex3b.py：

    digits2 = "".join([digits for i in range(len(digits))
                       if i == 0 or digits[i-1] != digits])
这样快了吗？ 一个字，否。

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']。 更进一步，列表可以被很快地 就地 改变。 与其一砖一瓦地建造一个新的列表（或者字符串），为什么不在一个列表中移动元素？

lastwinner

这便是 soundex/stage3/soundex3c.py， 就地修改列表去除连续重复元素：

    digits = list(source[0].upper() + source[1:].translate(charToSoundex))
    i=0
    for item in digits:
        if item==digits: continue
        i+=1
        digits=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
我们在这儿除了试用了几种 “clever” 的技术，根本没有什么进步。 到目前为止最快的方法就是最直接的原始方法（soundex2c.py）。 有时候聪明未必有回报。

lastwinner

例 18.5. 目前的最佳结果： soundex/stage2/soundex2c.py
[PHP] 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())

[/PHP]