# 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?節 “重構”](../refactoring/refactoring.html "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 將在下個版本中得到修正。――譯注
- 版權信息
- 第?1?章?安裝 Python
- 1.1.?哪一種 Python 適合您?
- 1.2.?Windows 上的 Python
- 1.3.?Mac OS X 上的 Python
- 1.4.?Mac OS 9 上的 Python
- 1.5.?RedHat Linux 上的 Python
- 1.6.?Debian GNU/Linux 上的 Python
- 1.7.?從源代碼安裝 Python
- 1.8.?使用 Python 的交互 Shell
- 1.9.?小結
- 第?2?章?第一個 Python 程序
- 2.1.?概覽
- 2.2.?函數聲明
- 2.3.?文檔化函數
- 2.4.?萬物皆對象
- 2.5.?代碼縮進
- 2.6.?測試模塊
- 第?3?章?內置數據類型
- 3.1.?Dictionary 介紹
- 3.2.?List 介紹
- 3.3.?Tuple 介紹
- 3.4.?變量聲明
- 3.5.?格式化字符串
- 3.6.?映射 list
- 3.7.?連接 list 與分割字符串
- 3.8.?小結
- 第?4?章?自省的威力
- 4.1.?概覽
- 4.2.?使用可選參數和命名參數
- 4.3.?使用 type、str、dir 和其它內置函數
- 4.4.?通過 getattr 獲取對象引用
- 4.5.?過濾列表
- 4.6.?and 和 or 的特殊性質
- 4.7.?使用 lambda 函數
- 4.8.?全部放在一起
- 4.9.?小結
- 第?5?章?對象和面向對象
- 5.1.?概覽
- 5.2.?使用 from _module_ import 導入模塊
- 5.3.?類的定義
- 5.4.?類的實例化
- 5.5.?探索 UserDict:一個封裝類
- 5.6.?專用類方法
- 5.7.?高級專用類方法
- 5.8.?類屬性介紹
- 5.9.?私有函數
- 5.10.?小結
- 第?6?章?異常和文件處理
- 6.1.?異常處理
- 6.2.?與文件對象共事
- 6.3.?for 循環
- 6.4.?使用 `sys.modules`
- 6.5.?與目錄共事
- 6.6.?全部放在一起
- 6.7.?小結
- 第?7?章?正則表達式
- 7.1.?概覽
- 7.2.?個案研究:街道地址
- 7.3.?個案研究:羅馬字母
- 7.4.?使用 {n,m} 語法
- 7.5.?松散正則表達式
- 7.6.?個案研究:解析電話號碼
- 7.7.?小結
- 第?8?章?HTML 處理
- 8.1.?概覽
- 8.2.?sgmllib.py 介紹
- 8.3.?從 HTML 文檔中提取數據
- 8.4.?BaseHTMLProcessor.py 介紹
- 8.5.?locals 和 globals
- 8.6.?基于 dictionary 的字符串格式化
- 8.7.?給屬性值加引號
- 8.8.?dialect.py 介紹
- 8.9.?全部放在一起
- 8.10.?小結
- 第?9?章?XML 處理
- 9.1.?概覽
- 9.2.?包
- 9.3.?XML 解析
- 9.4.?Unicode
- 9.5.?搜索元素
- 9.6.?訪問元素屬性
- 9.7.?Segue [9]
- 第?10?章?腳本和流
- 10.1.?抽象輸入源
- 10.2.?標準輸入、輸出和錯誤
- 10.3.?查詢緩沖節點
- 10.4.?查找節點的直接子節點
- 10.5.?根據節點類型創建不同的處理器
- 10.6.?處理命令行參數
- 10.7.?全部放在一起
- 10.8.?小結
- 第?11?章?HTTP Web 服務
- 11.1.?概覽
- 11.2.?避免通過 HTTP 重復地獲取數據
- 11.3.?HTTP 的特性
- 11.4.?調試 HTTP web 服務
- 11.5.?設置 User-Agent
- 11.6.?處理 Last-Modified 和 ETag
- 11.7.?處理重定向
- 11.8.?處理壓縮數據
- 11.9.?全部放在一起
- 11.10.?小結
- 第?12?章?SOAP Web 服務
- 12.1.?概覽
- 12.2.?安裝 SOAP 庫
- 12.3.?步入 SOAP
- 12.4.? SOAP 網絡服務查錯
- 12.5.?WSDL 介紹
- 12.6.?以 WSDL 進行 SOAP 內省
- 12.7.?搜索 Google
- 12.8.? SOAP 網絡服務故障排除
- 12.9.?小結
- 第?13?章?單元測試
- 13.1.?羅馬數字程序介紹 II
- 13.2.?深入
- 13.3.?romantest.py 介紹
- 13.4.?正面測試 (Testing for success)
- 13.5.?負面測試 (Testing for failure)
- 13.6.?完備性檢測 (Testing for sanity)
- 第?14?章?測試優先編程
- 14.1.?roman.py, 第 1 階段
- 14.2.?roman.py, 第 2 階段
- 14.3.?roman.py, 第 3 階段
- 14.4.?roman.py, 第 4 階段
- 14.5.?roman.py, 第 5 階段
- 第?15?章?重構
- 15.1.?處理 bugs
- 15.2.?應對需求變化
- 15.3.?重構
- 15.4.?后記
- 15.5.?小結
- 第?16?章?函數編程
- 16.1.?概覽
- 16.2.?找到路徑
- 16.3.?重識列表過濾
- 16.4.?重識列表映射
- 16.5.?數據中心思想編程
- 16.6.?動態導入模塊
- 16.7.?全部放在一起
- 16.8.?小結
- 第?17?章?動態函數
- 17.1.?概覽
- 17.2.?plural.py, 第 1 階段
- 17.3.?plural.py, 第 2 階段
- 17.4.?plural.py, 第 3 階段
- 17.5.?plural.py, 第 4 階段
- 17.6.?plural.py, 第 5 階段
- 17.7.?plural.py, 第 6 階段
- 17.8.?小結
- 第?18?章?性能優化
- 18.1.?概覽
- 18.2.?使用 timeit 模塊
- 18.3.?優化正則表達式
- 18.4.?優化字典查找
- 18.5.?優化列表操作
- 18.6.?優化字符串操作
- 18.7.?小結
- 附錄?A.?進一步閱讀
- 附錄?B.?五分鐘回顧
- 附錄?C.?技巧和竅門
- 附錄?D.?示例清單
- 附錄?E.?修訂歷史
- 附錄?F.?關于本書
- 附錄 G. GNU Free Documentation License
- G.0. Preamble
- G.1.?Applicability and definitions
- G.2.?Verbatim copying
- G.3.?Copying in quantity
- G.4.?Modifications
- G.5.?Combining documents
- G.6.?Collections of documents
- G.7.?Aggregation with independent works
- G.8.?Translation
- G.9.?Termination
- G.10.?Future revisions of this license
- G.11.?How to use this License for your documents
- 附錄 H. GNU 自由文檔協議
- H.0. 序
- H.1.?適用范圍和定義
- H.2.?原樣復制
- H.3.?大量復制
- H.4.?修改
- H.5.?合并文檔
- H.6.?文檔合集
- H.7.?獨立著作聚集
- H.8.?翻譯
- H.9.?終止協議
- H.10.?協議將來的修訂
- H.11.?如何為你的文檔使用本協議
- 附錄 I. Python license
- I.A. History of the software
- I.B.?Terms and conditions for accessing or otherwise using Python
- 附錄 J. Python 協議
- J.0. 關于譯文的聲明
- J.A.?軟件的歷史
- J.B.?使用 Python 的條款和條件