Python 研究(Dive Into Python)

lastwinner · 发表于 2006-7-20 01:42

18.3. 优化正则表达式
Soundex 函数的第一件事是检查输入是否是一个空字符串。怎样做是最好的方法？

如果你回答 “正则表达式”，坐在角落里反省你糟糕的直觉。正则表达式几乎永远不是最好的答案，而且应该被尽可能避开。这不仅仅是基于性能考虑，而是因为差错和维护都很困难，当然性能也是个原因。

这是 soundex/stage1/soundex1a.py 检查 source 是否全部由字母构成的一段代码，至少是一个字母（而不是空字符串）：

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

lastwinner · 发表于 2006-7-20 01:42

soundex1a.py 表现如何？为了方便，__main__ 部分的代码包含了调用 timeit 模块，建立一个分别测试三个不同名字三次并显示最短耗时的一个计时测试代码：

[PHP]
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]
那么，应用正则表达式的 soundex1a.py 表现如何呢？
[PHP]
C:\samples\soundex\stage1>python soundex1a.py
Woo          W000 19.3356647283
Pilgrim       P426 24.0772053431
Flingjingwaller F452 35.0463220884
.............
[/PHP]

lastwinner · 发表于 2006-7-20 01:43

正如你预料，名字越长，算法耗时就越长。有几个工作可以另我们减小这个差距（使函数对于长输入花费较短的相对时间）但是算法的本质决定它不可能每次运行时间都相同。

另一点应铭记于心的是，我们测试的是有代表性的名字样本。 Woo 是个被缩短到单字符并补零的小样本； Pilgrim 是个夹带着特别字符和忽略字符的平均长度的正常样本； Flingjingwaller 是一个包含连续重复字符并且特别长的样本。其它的测试可能同样有帮助，但它们已经是很好的不同样本范围了。

那么那个正则表达式如何呢？嗯，缺乏效率。因为这个表达式测试不止一个范围的字符（A-Z 的大写范围和 a-z 的小写字母范围），我们可以使用一个正则表达式的缩写语法。这便是 soundex/stage1/soundex1b.py:

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

lastwinner · 发表于 2006-7-20 01:44

timeit 显示 soundex1b.py 比 soundex1a.py 稍微快一些，但是没什么令人激动的变化：
[PHP]
C:\samples\soundex\stage1>python soundex1b.py
Woo W000 17.1361133887
Pilgrim P426 21.8201693232
Flingjingwaller F452 32.7262294509
..............
[/PHP]

lastwinner · 发表于 2006-7-20 01:44

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

lastwinner · 发表于 2006-7-20 01:44

但是这样的优化是正路吗？这里的逻辑很简单：输入 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 中恰好不及编译后的正则表达式快（尽管比使用未编译的正则表达式快）：

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

lastwinner · 发表于 2006-7-20 01:44

为什么 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

lastwinner · 发表于 2006-7-20 01:45

例 18.3. 目前为止最好的结果： soundex/stage1/soundex1e.py

[PHP] 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
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 · 发表于 2006-7-20 01:45

18.4. 优化字典查找
Soundex 算法的第二步是依照特定规则将字符转换为数字。做到这点最好的方法是什么？

最明显的解决方案是定义一个以单字符为键并以所对应数字为值的字典，以字典查找每个字符。这便是 soundex/stage1/soundex1c.py 中使用的方法（目前最好的结果）：
[PHP]
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
~~[/PHP]~~

lastwinner · 发表于 2006-7-20 01:46

你已经为 soundex1c.py 计时，这便是其表现：

[PHP] C:\samples\soundex\stage1>python soundex1c.py
Woo W000 14.5341678901
Pilgrim P426 19.2650071448
Flingjingwaller F452 30.1003563302
...
[/PHP]

这段代码很直接，但它是最佳解决方案吗？为每个字符分别调用 upper() 看起来不是很有效率，为整个字符串调用 upper() 一次可能会好些。

然后是一砖一瓦的建立 digits 字符串。一砖一瓦的建造好像非常欠缺效率。在 Python 内部，解释器需要在循环的每一轮创建一个新的字符串，然后丢弃旧的。

[参考文档] Python 研究(Dive Into Python)