DiveIntoPython(十七)

DiveIntoPython(十七)

英文书地址：
http://diveintopython.org/toc/index.html

Chapter 18.Performance Tuning
Performance tuning is a many-splendored thing. Just because Python is an interpreted language doesn't mean you shouldn't worry about code optimization. But don't worry about it too much.

18.1.Diving in
Let's start here: are you sure you need to do it at all? Is your code really so bad? Is it worth the time to tune it? Over the lifetime of your application, how much time is going to be spent running that code, compared to the time spent waiting for a remote database server, or waiting for user input?

This is not to say that code optimization is worthless, but you need to look at the whole system and decide whether it's the best use of your time. Every minute you spend optimizing code is a minute you're not spending adding new features, or writing documentation, or playing with your kids, or writing unit tests.

There are several subtle variations of the Soundex algorithm. This is the one used in this chapter:

Keep the first letter of the name as-is.
Convert the remaining letters to digits, according to a specific table:
B, F, P, and V become 1.
C, G, J, K, Q, S, X, and Z become 2.
D and T become 3.
L becomes 4.
M and N become 5.
R becomes 6.
All other letters become 9.
Remove consecutive duplicates.
Remove all 9s altogether.
If the result is shorter than four characters (the first letter plus three digits), pad the result with trailing zeros.
if the result is longer than four characters, discard everything after the fourth character.
For example, my name, Pilgrim, becomes P942695. That has no consecutive duplicates, so nothing to do there. Then you remove the 9s, leaving P4265. That's too long, so you discard the excess character, leaving P426.

Another example: Woo becomes W99, which becomes W9, which becomes W, which gets padded with zeros to become W000.

example 18.1.soundex/stage1/soundex1a.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):
    "convert string to Soundex equivalent"

    # Soundex requirements:
    # source string must be at least 1 character
    # and must consist entirely of letters
    allChars = string.uppercase + string.lowercase
    if not re.search('^[%s]+$' % allChars, source):
        return "0000"

    # Soundex algorithm:
    # 1. make first character uppercase
    source = source[0].upper() + source[1:]
   
    # 2. translate all other characters to Soundex digits
    digits = source[0]
    for s in source[1:]:
        s = s.upper()
        digits += charToSoundex[s]

    # 3. remove consecutive duplicates
    digits2 = digits[0]
    for d in digits[1:]:
        if digits2[-1] != d:
            digits2 += d
       
    # 4. remove all "9"s
    digits3 = re.sub('9', '', digits2)
   
    # 5. pad end with "0"s to 4 characters
    while len(digits3) < 4:
        digits3 += "0"
       
    # 6. return first 4 characters
    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())

18.2.Using the timeit Module

example 18.2.Introducing timeit
>>> import timeit
>>> t = timeit.Timer("soundex.soundex('Pilgrim')","import soundex")
>>> t.timeit()
7.8085661725163389
>>> t.repeat(3,2000000)
[15.873824745882509, 16.936368728427773, 16.090063681277933]

The timeit module defines one class, Timer, which takes two arguments. Both arguments are strings. The first argument is the statement you wish to time; in this case, you are timing a call to the Soundex function within the soundex with an argument of 'Pilgrim'. The second argument to the Timer class is the import statement that sets up the environment for the statement.

Once you have the Timer object, the easiest thing to do is call timeit(), which calls your function 1 million times and returns the number of seconds it took to do it.

The other major method of the Timer object is repeat(), which takes two optional arguments. The first argument is the number of times to repeat the entire test, and the second argument is the number of times to call the timed statement within each test. Both arguments are optional, and they default to 3 and 1000000 respectively. The repeat() method returns a list of the times each test cycle took, in seconds.

Python has a handy min function that takes a list and returns the smallest value:
>>> min(t.repeat(3,1000000))
8.2049416895164313

18.3.Optimizing Regular Expressions

example soundex/stage1/soundex1a.py

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

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

E:\book\opensource\python\diveintopython-5.4\py\soundex\stage1>python soundex1a.py
Woo             W000    21.6845738774
Pilgrim         P426 25.4686735325
Flingjingwaller F452 33.7811945373

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

E:\book\opensource\python\diveintopython-5.4\py\soundex\stage1>python soundex1b.py
Woo             W000 20.6642844272
Pilgrim         P426 24.2337135027
Flingjingwaller F452 32.8864372427

example soundex/stage1/soundex1c.py

isOnlyChars = re.compile('^[A-Za-z]+$').search
def soundex(source):
    if not isOnlyChars(source):
        return "0000"

E:\book\opensource\python\diveintopython-5.4\py\soundex\stage1>python soundex1c.py
Woo             W000 17.2678421419
Pilgrim         P426 20.8697745104
Flingjingwaller F452 29.3527870162

example soundex/stage1/soudex1d.py
if not source:
        return "0000"
    for c in source:
        if not ('A' <= c <= 'Z') and not ('a' <= c <= 'z'):
            return "0000"

It turns out that this technique in soundex1d.py is not faster than using a compiled regular expression (although it is faster than using a non-compiled regular expression):
E:\book\opensource\python\diveintopython-5.4\py\soundex\stage1>python soundex1d.py
Woo             W000 17.5661093798
Pilgrim         P426 23.8642883383
Flingjingwaller F452 35.9031505401

It turns out that Python offers an obscure string method. You can be excused for not knowing about it, since it's never been mentioned in this book. The method is called isalpha(), and it checks whether a string contains only letters.

example soundex/stage1/soudnex1e.py
if (not source) and (not source.isalpha()):
        return "0000"

E:\book\opensource\python\diveintopython-5.4\py\soundex\stage1>python soundex1e.py
Woo             W000 15.3807154261
Pilgrim         P426 19.2102524203
Flingjingwaller F452 27.7341740361

example 18.3.Best Result So Far:soundex/stage1/soundex1e.py

18.4.Optimizing Dictionary Lookups

example soundex/stage1/soundex1c.py
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[s]

example soundex/stage2/soundex2a.py
def soundex(source):
    # ...
    source = source.upper()
    digits = source[0] + "".join(map(lambda c: charToSoundex[c], source[1:]))

Surprisingly, soundex2a.py is not faster:
E:\book\opensource\python\diveintopython-5.4\py\soundex\stage2>python soundex2a.py
Woo             W000 18.0709193487
Pilgrim         P426 21.4308902388
Flingjingwaller F452 28.9357734014

The overhead of the anonymous lambda function kills any performance you gain by dealing with the string as a list of characters.

example soundex/stage2/soundex2b.py uses a list comprehension instead of ↦ and lambda:
source = source.upper()
    digits = source[0] + "".join([charToSoundex[c] for c in source[1:]])
E:\book\opensource\python\diveintopython-5.4\py\soundex\stage2>python soundex2b.py
Woo             W000 14.9096245473
Pilgrim         P426 17.5887675668
Flingjingwaller F452 22.4958635804

It's time for a radically different approach. Dictionary lookups are a general purpose tool. Dictionary keys can be any length string (or many other data types), but in this case we are only dealing with single-character keys and single-character values. It turns out that Python has a specialized function for handling exactly this situation: the string.maketrans function.

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

string.maketrans creates a translation matrix between two strings: the first argument and the second argument. In this case, the first argument is the string ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz, and the second argument is the string 9123912992245591262391929291239129922455912623919292.

It's the same conversion pattern we were setting up longhand with a dictionary. A maps to 9, B maps to 1, C maps to 2, and so forth. But it's not a dictionary; it's a specialized data structure that you can access using the string method translate, which translates each character into the corresponding digit, according to the matrix defined by string.maketrans.

E:\book\opensource\python\diveintopython-5.4\py\soundex\stage2>python soundex2c.py
Woo             W000 13.0717325805
Pilgrim         P426 15.2769533558
Flingjingwaller F452 19.284963033

example 18.4.Best Result So Far: soundex/stage2/soundex2c.py

18.5.Optimizing List Operations
Here's the code we have so far, in soundex/stage2/soundex2c.py:
digits2 = digits[0]
    for d in digits[1:]:
        if digits2[-1] != d:
            digits2 += d

The first thing to consider is whether it's efficient to check digits[-1] each time through the loop. Are list indexes expensive? Would we be better off maintaining the last digit in a separate variable, and checking that instead?

example soundex/stage3/soundex3a.py
digits2 = ''
    last_digit = ''
    for d in digits:
        if d != last_digit:
            digits2 += d
            last_digit = d

soundex3a.py does not run any faster than soundex2c.py, and may even be slightly slower
E:\book\opensource\python\diveintopython-5.4\py\soundex\stage3>python soundex3a.py
Woo             W000 13.0359651855
Pilgrim         P426 14.5332295026
Flingjingwaller F452 18.2346787092

Let's try something radically different. If it's possible to treat a string as a list of characters, it should be possible to use a list comprehension to iterate through the list. The problem is, the code needs access to the previous character in the list, and that's not easy to do with a straightforward list comprehension.

example soundex/stage3/soundex3b.py
digits2 = "".join([digits[i] for i in range(len(digits))
                       if i == 0 or digits[i-1] != digits[i]])

Is this faster? In a word, no.
E:\book\opensource\python\diveintopython-5.4\py\soundex\stage3>python soundex3b.py
Woo             W000 13.821099609
Pilgrim         P426 16.882249839
Flingjingwaller F452 22.9767347526

Python can convert a string into a list of characters with a single command: list('abc') returns ['a', 'b', 'c']. Furthermore, lists can be modified in place very quickly. Instead of incrementally building a new list (or string) out of the source string, why not move elements around within a single list?

example 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)
Is this faster than soundex3a.py or soundex3b.py? No, in fact it's the slowest method yet:
E:\book\opensource\python\diveintopython-5.4\py\soundex\stage3>python soundex3c.py
Woo             W000 16.1901624368
Pilgrim         P426 18.2924290657
Flingjingwaller F452 22.718192396

We haven't made any progress here at all, except to try and rule out several “clever” techniques. The fastest code we've seen so far was the original, most straightforward method (soundex2c.py). Sometimes it doesn't pay to be clever.

example 18.5.Best Result So Far:soundex/stage2/soundex2c.py

18.6.Optimizing String Manipulation
example soundex/stage2/soundex2c.py
    digits3 = re.sub('9', '', digits2)
    while len(digits3) < 4:
        digits3 += "0"
    return digits3[:4]

The first thing to consider is replacing that regular expression with a loop. This code is from soundex/stage4/soundex4a.py:
example soundex/stage4/soundex4a.py
digits3 = ''
    for d in digits2:
        if d != '9':
            digits3 += d
Is soundex4a.py faster? Yes it is:
E:\book\opensource\python\diveintopython-5.4\py\soundex\stage4>python soundex4a.py
Woo             W000 9.3276673432
Pilgrim         P426 11.0247101238
Flingjingwaller F452 15.2871535349

But wait a minute. A loop to remove characters from a string? We can use a simple string method for that. Here's soundex/stage4/soundex4b.py:
digits3 = digits2.replace('9', '')

Is soundex4b.py faster? That's an interesting question. It depends on the input:
E:\book\opensource\python\diveintopython-5.4\py\soundex\stage4>python soundex4b.py
Woo             W000 6.70664232465
Pilgrim         P426 7.46835952614
Flingjingwaller F452 10.2336799789

Performance optimizations aren't always uniform; tuning that makes one case faster can sometimes make other cases slower. In this case, the majority of cases will benefit from the change, so let's leave it at that, but the principle is an important one to remember.

examples:
# 5. pad end with "0"s to 4 characters
while len(digits3) < 4:
        digits3 += "0"
# 6. return first 4 characters
return digits3[:4]

example soundex/stage4/soundex4c.py:
digits3 += '000'
return digits3[:4]
E:\book\opensource\python\diveintopython-5.4\py\soundex\stage4>python soundex4c.py
Woo             W000 5.39382044366
Pilgrim         P426 7.24943058405
Flingjingwaller F452 10.2510975557

example soundex/stage4/soundex4d.py:
return (digits2.replace('9', '') + '000')[:4]
E:\book\opensource\python\diveintopython-5.4\py\soundex\stage4>python soundex4d.py
Woo             W000 5.23971342727
Pilgrim         P426 7.14076314168
Flingjingwaller F452 10.4394474717

It is also significantly less readable, and for not much performance gain. Is that worth it? I hope you have good comments. Performance isn't everything. Your optimization efforts must always be balanced against threats to your program's readability and maintainability.