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