导航:起始页 > Dive Into Python > 性能优化 > 优化列表操作 | << >> | ||||
深入 Python :Dive Into Python 中文版Python 从新手到专家 [Dip_5.4b_CPyUG_Release] |
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)。有时候聪明未必有回报。
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())
[16] soundex3c.py 比 soundex3b.py 快。――译注
<< 优化字典查找 |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
优化字符串操作 >> |