Zanurkuj w Pythonie/Optymalizacja szybkości

Optymalizacja szybkości jest niesamowitą sprawą. Tylko dlatego, że Python jest językiem interpretowanym, nie oznacza, że nie powinniśmy martwić się o optymalizację pod kątem szybkości działania. Jednak nie należy się tym aż tak bardzo przejmować.

Nurkujemy

Istnieje sporo pułapek związanych z optymalizacją kodu, ciężko stwierdzić, od czego należałoby zacząć.

Zacznijmy więc tutaj: czy jesteśmy pewni, że w ogóle powinniśmy się do tego zabierać? Czy nasz kod jest rzeczywiście tak kiepski? Czy warto poświęcić na to czas? Ile tak naprawdę czasu podczas działania aplikacji będzie zajmowało wykonywanie kodu, w porównaniu z czasem poświęconym na oczekiwanie na odpowiedź zdalnej bazy danych czy też akcję użytkownika?

Po drugie, czy jesteśmy pewni, że skończyliśmy kodowanie? Przedwczesna optymalizacja jest jak nakładanie lodowej polewy na w pół upieczone ciasto. Poświęcamy godziny czy nawet dni na optymalizację kodu pod kątem wydajności, aby w końcu przekonać się, że nie robi on tego, co byśmy chcieli. Stracony czas, robota wyrzucona w błoto.

Nie chodzi o to, że optymalizacja kodu jest bezwartościowa, raczej powinniśmy spojrzeć z dystansu na cały system aby nabrać przeświadczenia, czy czas przeznaczony na nią jest najlepszą inwestycją. Każda minuta poświęcona na optymalizację kodu jest minutą, której nie poświęcamy na dodawanie nowych funkcjonalności, pisanie dokumentacji, zabawę z naszymi dziećmi czy też pisanie testów jednostkowych.

A no właśnie, testy jednostkowe. Nie powinniśmy nawet zaczynać optymalizacji nie mając pełnego zestawu takich testów. Ostatnią rzeczą jakiej byśmy chcieli to pojawienie się nowego błędu podczas dłubania w algorytmie.

Mając na uwadze powyższe porady, zerknijmy na niektóre techniki optymalizacji kodu Pythona. Nasz kod to implementacja algorytmu Soundex. Soundex był metodą kategoryzowania nazwisk w spisie ludności w Stanach Zjednoczonych na początku 20 wieku. Grupował on podobnie brzmiące słowa, przez co naukowcy mieli szansę na odnalezienie nawet błędnie zapisanych nazwisk. Soundex jest do dziś używany głównie z tego samego powodu, lecz oczywiści w tym celu używane są skomputeryzowane bazy danych. Większość silników baz danych posiada funkcję Soundex.

Istnieje kilka nieco różniących się od siebie wersji algorytmu Soundex. Poniżej znajduje się ta, której używamy w tym rozdziale:

1. Weź pierwszą literę nazwy.
2. Przekształć pozostałe litery na cyfry według poniższej listy:

• B, F, P, oraz V stają się 1.
• C, G, J, K, Q, S, X, oraz Z stają się 2.
• D oraz T stają się 3.
• L staje się 4.
• M oraz N stają się 5.
• R staje się 6.
• Wszystkie pozostałe litery stają się 9.

1. Usuń wszystkie duplikaty.
2. Usuń wszystkie dziewiątki.
3. Jeśli wynik jest krótszy niż cztery znaki (pierwsza litera plus trzy cyfry), dopełnij wynik zerami z prawej strony ciągu do czterech znaków.
4. Jeżeli wynik jest dłuższy niż cztery znaki, pozbądź się wszystkiego po czwartym znaku.

Na przykład, moje nazwisko, Pilgrim, staje się P942695. Nie posiada następujących po sobie duplikatów, więc nic tutaj nie robimy. Następnie usuwamy 9tki pozostawiając P4265. Jednak znaków jest za dużo, więc pomijamy ich nadmiar w wyniku otrzymując P426.

Inny przykład: Woo staje się W99, które staje się W9, które staje się W, które natomiast dopełniamy zerami z prawej strony do czterech znaków aby otrzymać W000.

A oto pierwsze podejście do funkcji Soundex:

Przykład 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())