Zanurkuj w Pythonie/Optymalizacja wyrażeń regularnych

Pierwszą rzeczą, jaką musi sprawdzić funkcja Soundex, jest to, czy na wejściu znajduje się niepusty ciąg znaków. Jak można to najlepiej zrobić?

Jeśli odpowiedzieliście: "używając wyrażeń regularnych", to idziecie do kąta i kontemplujecie tam swoje złe instynkty. "Wyrażenia regularne" prawie nigdy nie stanowią dobrej odpowiedzi; jeśli to możliwe, należy ich raczej unikać. Nie tylko ze względu na wydajność, lecz także z tego prostego powodu, że są one niezwykle trudne w debugowaniu i w dalszym utrzymaniu. Ale również ze względu na wydajność.

Poniższy fragment kodu pochodzi z programu soundex/stage1/soundex1a.py i sprawdza, czy zmienna source będąca argumentem funkcji jest napisem zbudowanym wyłącznie z liter, przy czym zawiera co najmniej jedną literę (nie jest pustym napisem):

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

Czy soundex1a.py to wydajny program? Dla ułatwienia, w sekcji __main__ skryptu znajduje się poniższy kod, który wywołuje moduł timeit, konstruuje test do pomiaru złożony z trzech różnych napisów, testuje każdy napis trzy razy i dla każdego z napisów wyświetla minimalny czas:

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

A więc czy soundex1a.py używający wyrażeń regularnych jest wydajny?

C:\samples\soundex\stage1>python soundex1a.py
Woo             W000 19.3356647283
Pilgrim         P426 24.0772053431
Flingjingwaller F452 35.0463220884

Możemy się spodziewać, algorytm ten będzie działał znacznie dłużej, jeśli zostanie on wywołany ze znacznie dłuższymi napisami. Możemy zrobić wiele, aby zmniejszyć tę szczelinę (sprawić, że funkcja będzie potrzebowała względnie mniej czasu dla dłuższych danych wejściowych), jednak natura tego algorytmu wskazuje na to, że nie będzie on nigdy działał w stałym czasie.

Warto mieć na uwadze, że testujemy reprezentatywną próbkę imion. Woo to przypadek trywialny; to imię zostanie skrócone do jednej litery i uzupełnione zerami. Pilgrim to średnio złożony przypadek, posiadający średnią długość i zawierający zarówno litery znaczące, jak i te, które zostaną zignorowane. Flingjingwaller zaś to wyjątkowo długie imię zawierające następujące po sobie powtórzenia. Inne testy mogłyby również być przydatne, jednak te trzy pokrywają duży zakres przypadków.

Co zatem z wyrażeniem regularnym? Cóż, okazało się ono nieefektywne. Ponieważ wyrażenie sprawdza zakresy znaków (duże litery A-Z oraz małe a-z), możemy użyć skróconej składni wyrażeń regularnych. Poniżej soundex/stage1/soundex1b.py:

    if not re.search('^[A-Za-z]+$', source):
        return "0000"

Moduł timeit mówi, że soundex1b.py jest odrobinę szybszy, niż soundex1a.py, nie ma w tym jednak nic, czym można by się ekscytować:

C:\samples\soundex\stage1>python soundex1b.py
Woo             W000 17.1361133887
Pilgrim         P426 21.8201693232
Flingjingwaller F452 32.7262294509

Jak widzieliśmy w podrozdziale 15.3 [Python/Refaktoryzacja], wyrażenia regularne mogą zostać skompilowane i użyte powtórnie, dzięki czemu osiąga się lepsze rezultaty. Ze względu na to, że nasze wyrażenie regularne nie zmienia się między wywołaniami, kompilujemy je i używamy wersji skompilowanej. Poniżej znajduje się fragment soundex/stage1/soundex1c.py:

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

Użycie skompilowanej wersji wyrażenia regularnego jest już znacznie szybsze:

C:\samples\soundex\stage1>python soundex1c.py
Woo             W000 14.5348347346
Pilgrim         P426 19.2784703084
Flingjingwaller F452 30.0893873383

Ale czy to nie jest przypadkiem błędna ścieżka? Logika jest przecież prosta: napis wejściowy nie może być pusty i musi być cały złożony z liter. Czy nie byłoby szybciej, gdybyśmy pozbyli się wyrażenia regularnego i zapisali pętlę, która sprawdza każdy znak?

Poniżej 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"

Okazuje się, że ta technika w soundex1d.py nie jest szybsza, niż użycie skompilowanego wyrażenia regularnego (ale jest szybsza, niż użycie nieskompilowanego wyrażenia regularnego):

C:\samples\soundex\stage1>python soundex1d.py
Woo             W000 15.4065058548
Pilgrim         P426 22.2753567842
Flingjingwaller F452 37.5845122774

Dlaczego soundex1d.py nie jest szybszy? Odpowiedź leży w naturze języka Python, który jest językiem interpretowanym. Silnik wyrażeń regularnych napisany jest w C i skompilowany odpowiednio do architektury waszego komputera. Z drugiej strony, pętla napisana jest w języku Python i jest uruchamiana przez interpreter języka Python. Choć pętla jest stosunkowo prosta, jej prostota nie wystarcza, aby pozbyć się narzutu związanego z tym, że jest ona interpretowana. Wyrażenia regularne nigdy nie są dobrym rozwiązaniem... chyba, że akurat są.

Okazuje się, że Python posiada pewną starą metodę w klasie string. Jesteście całkowicie usprawiedliwieni, jeśli o niej nie wiedzieliście, bowiem nie wspominałem jeszcze o niej w tej książce. Metoda nazywa się isalpha() i sprawdza, czy napis składa się wyłącznie z liter.

Oto soundex/stage1/soundex1e.py:

    if (not source) and (not source.isalpha()):
        return "0000"

Czy zyskaliśmy coś używając tej specyficznej metody w soundex1e.py? Trochę zyskaliśmy.

C:\samples\soundex\stage1>python soundex1e.py
Woo             W000 13.5069504644
Pilgrim         P426 18.2199394057
Flingjingwaller F452 28.9975225902

Przykład 18.3. Dotychczas najlepszy rezultat: 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())