Przejdź do zawartości

Zanurkuj w Pythonie/Optymalizacja operacji na napisach

Z Wikibooks, biblioteki wolnych podręczników.

Ostatnim krokiem algorytmu Soundex jest dopełnienie krótkich napisów wynikowych zerami oraz przycięcie napisów zbyt długich. W jaki sposób można to zrobić najlepiej?

Dotychczasowy kod w programie soundex/stage2/soundex2c.py wygląda następująco:

    digits3 = re.sub('9', '', digits2)
    while len(digits3) < 4:
        digits3 += "0"
    return digits3[:4]

Oto rezultaty pomiarów wydajności w soundex2c.py:

C:\samples\soundex\stage2>python soundex2c.py
Woo             W000 12.6070768771
Pilgrim         P426 14.4033353401
Flingjingwaller F452 19.7774882003

Pierwszą rzeczą, jaką należy rozważyć, jest zastąpienie wyrażenia regularnego pętlą. Oto kod programu soundex/stage4/soundex4a.py:

    digits3 = ''
    for d in digits2:
        if d != '9':
            digits3 += d

Czy soundex4a.py jest szybszy? Oczywiście:

C:\samples\soundex\stage4>python soundex4a.py
Woo             W000 6.62865531792
Pilgrim         P426 9.02247576158
Flingjingwaller F452 13.6328416042

Czekajcie chwilę. Pętla, która usuwa znaki z napisu? Możemy użyć do tego prostej metody z klasy string. Oto soundex/stage4/soundex4b.py:

    digits3 = digits2.replace('9', '')

Czy soundex4b.py jest szybszy? To interesujące pytanie. Zależy to od danych wejściowych:

C:\samples\soundex\stage4>python soundex4b.py
Woo             W000 6.75477414029
Pilgrim         P426 7.56652144337
Flingjingwaller F452 10.8727729362

Dla większości nazw z programu soundex4b.py metoda z klasy string jest szybsza niż pętla, jest jednak odrobinę wolniejsza niż soundex4a.py dla przypadku trywialnego (dla bardzo krótkiej nazwy). Optymalizacje wydajnościowe nie zawsze są jednorodne; poprawki, które sprawią, że w pewnych przypadkach program będzie działał szybciej, mogą sprawić, że w innych przypadkach ten sam program będzie działał wolniej. W naszym programie uzyskujemy poprawę dla większości przypadków, więc zostawimy tę poprawkę, warto jednak na przyszłość mieć tę ważną zasadę na uwadze.

Na koniec, choć to wcale nie jest sprawa najmniejszej wagi, prześledźmy dwa ostatnie kroki algorytmu: uzupełnianie zerami krótkich napisów wynikowych oraz przycinanie napisów zbyt długich do czterech znaków. Kod, który widzicie w soundex4b.py robi dokładnie to, co trzeba, jednak robi to w bardzo niewydajny sposób. Spójrzmy na soundex/stage4/soundex4c.py, aby przekonać się, dlaczego tak się dzieje.

    digits3 += '000'
    return digits3[:4]

Dlaczego potrzebujemy pętli while do wyrównania napisu wynikowego? Wiemy przecież z góry, że zamierzamy obciąć napis do czterech znaków; wiemy również, że mamy juz przynajmniej jeden znak (pierwszą literę zmiennej source, która w wyniku tego algorytmu nie zmienia się). Oznacza to, że możemy po prostu dodać trzy zera do napisu wyjściowego, a następnie go przyciąć. Nie dajcie się nigdy zbić z tropu przez dosłowne sformułowanie problemu; czasami wystarczy spojrzeć na ten problem z trochę innej perspektywy, a już pojawia się prostsze rozwiązanie.

Czy usuwając pętlę while zyskaliśmy na prędkości programu soundex4c.py? Nawet znacznie:

C:\samples\soundex\stage4>python soundex4c.py
Woo             W000 4.89129791636
Pilgrim         P426 7.30642134685
Flingjingwaller F452 10.689832367

Na koniec warto zauważyć, że jest jeszcze jedna rzecz, jaką można zrobić, aby przyspieszyć te trzy linijki kodu: można przekształcić je do jednej linii. Spójrzmy na soundex/stage4/soundex4d.py:

    return (digits2.replace('9', '') + '000')[:4]

Umieszczenie tego kodu w jednej linii sprawiło, że stał się on zaledwie odrobinę szybszy, niż soundex4c.py:

C:\samples\soundex\stage4>python soundex4d.py
Woo             W000 4.93624105857
Pilgrim         P426 7.19747593619
Flingjingwaller F452 10.5490700634

Za cenę tego niewielkiego wzrostu wydajności stał się przy okazji znacznie mniej czytelny. Czy warto było to zrobić? Mam nadzieję, że potraficie to dobrze skomentować. Wydajność to nie wszystko. Wysiłki związane z optymalizacją kodu muszą być zawsze równoważone dążeniem do tego, aby kod był czytelny i łatwy w utrzymaniu.