Zanurkuj w Pythonie/Optymalizacja przeszukiwania słownika

Kolejnym krokiem w algorytmie Soundex jest przekształcenie znaków w cyfry według pewnego szczególnego wzorca. Jaki jest najlepszy sposób, aby to zrobić?

Najbardziej oczywiste rozwiązanie polega na zdefiniowaniu słownika, w którym poszczególne znaki są kluczami, a wartościami - odpowiadające im cyfry, a następnie przeszukiwaniu słownika dla każdego pojawiającego się znaku. Tak właśnie działa program soundex/stage1/soundex1c.py (który osiąga najlepsze jak do tej pory rezultaty wydajnościowe):

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):
    # ... 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]

Mierzyliśmy już czas wykonania soundex1c.py; oto, jak się przestawiają pomiary:

C:\samples\soundex\stage1>python soundex1c.py
Woo             W000 14.5341678901
Pilgrim         P426 19.2650071448
Flingjingwaller F452 30.1003563302

Powyższy kod jest prosty, ale czy stanowi najlepsze możliwe rozwiązanie? Nieefektywne wydaje się w szczególności wywoływanie na każdym znaku metody upper(); zrobilibyśmy prawdopodobnie lepiej wywołując upper() na całym napisie wejściowym.

Dochodzi do tego kwestia przyrostowego budowania napisu złożonego z cyfr. Takie przyrostowe budowanie napisu jest niezwykle niewydajne; wewnętrznie interpreter języka musi w każdym przebiegu pętli utworzyć nowy napis, a następnie zwolnić stary.

Wiadomo jednak, że Python świetnie sobie radzi z listami. Może automatycznie potraktować napis jako listę znaków. Listę zaś łatwo przekształcić z powrotem do napisu przy użyciu metody join().

Poniżej soundex/stage2/soundex2a.py, który konwertuje litery na cyfry przy użyciu metody join i notacji lambda:

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

Co ciekawe, program soundex2a.py nie jest wcale szybszy:

C:\samples\soundex\stage2>python soundex2a.py
Woo             W000 15.0097526362
Pilgrim         P426 19.254806407
Flingjingwaller F452 29.3790847719

Narzut wprowadzony przez funkcję anonimową utworzoną przy pomocy notacji lambda przekroczył cały zysk wydajności, jaki osiągnęliśmy używając napisu w charakterze listy znaków.

Program soundex/stage2/soundex2b.py w miejsce notacji lambda używa wyrażeń listowych:

    source = source.upper()
    digits = source[0] + "".join([charToSoundex[c] for c in source[1:]])

Użycie wyrażeń listowych w soundex2b.py jest szybsze niż używanie notacji lambda, ale wciąż nie jest szybsze, niż oryginalny kod (soundex1c.py, w którym napis wynikowy jest budowany przyrostowo):

C:\samples\soundex\stage2>python soundex2b.py
Woo             W000 13.4221324219
Pilgrim         P426 16.4901234654
Flingjingwaller F452 25.8186157738

Nadszedł czas na wprowadzenie radykalnej zmiany w naszym podejściu. Przeszukiwanie słownika to narzędzie ogólnego zastosowania. Kluczami w słownikach mogą być napisy dowolnej długości (oraz wiele innych typów danych), jednak w tym przypadku posługiwaliśmy sie jedynie napisami o długości jednego znaku, zarówno w charakterze klucza, jak i wartości. Okazuje się, że język Python posiada specjalizowaną funkcję służącą do obsługi dokładnie tej sytuacji, funkcję o nazwie string.maketrans.

Oto program 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)

Co właściwie się tu dzieje? Funkcja string.maketrans tworzy wektor przekształceń między dwoma napisami: pierwszym i drugim argumentem. W tym przypadku pierwszym argumentem jest napis ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz, a drugim napis 9123912992245591262391929291239129922455912623919292. Rozpoznajecie ten wzorzec? To ten sam, którego używaliśmy w przypadku słownika: A jest przekształcane do 9, B do 1, C do 2 i tak dalej. Nie jest to jednak słownik; to specjalizowana struktura danych, do której mamy dostęp przy użyciu metody translate(), przekształcającej każdy znak argumentu w odpowiadającą mu cyfrę, zgodnie z wektorem przekształceń zdefiniowanym w string.maketrans.

Moduł timeit pokazuje, że program soundex2c.py jest znacznie szybszy niż ten, w którym definiowaliśmy słownik, iterowaliśmy w pętli po napisie wejściowym i budowaliśmy przyrostowo napis wyjściowy:

C:\samples\soundex\stage2>python soundex2c.py
Woo             W000 11.437645008
Pilgrim         P426 13.2825062962
Flingjingwaller F452 18.5570110168

Nie uda się nam osiągnąć o wiele lepszych rezultatów niż pokazany wyżej. Specjalizowana funkcja języka Python robi dokładnie to, czego potrzebujemy; używamy więc jej i idziemy dalej.

Przykład 18.4. Dotychczas najlepszy rezultat: soundex/stage2/soundex2c.py

import string, re

allChar = string.uppercase + string.lowercase
charToSoundex = string.maketrans(allChar, "91239129922455912623919292" * 2)
isOnlyChars = re.compile('^[A-Za-z]+$').search

def soundex(source):
    if not isOnlyChars(source):
        return "0000"
    digits = source[0].upper() + source[1:].translate(charToSoundex)
    digits2 = digits[0]
    for d in digits[1:]:
        if digits2[-1] != d:
            digits2 += d
    <nowiki>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())