Zanurkuj w Pythonie/Optymalizacja operacji na listach

Optymalizacja operacji na listach

Trzecim krokiem algorytmu soundex jest eliminacja kolejnych powtarzających się cyfr. Jak najlepiej to zrobić?

Taki kod otrzymaliśmy dotąd, znajduje się on w soundex/stage2/soundex2c.py:

    digits2 = digits[0]
    for d in digits[1:]:
        if digits2[-1] != d:
            digits2 += d

Takie wyniki wydajnościowe otrzymujemy dla soundex2c.py:

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

Pierwszą rzeczą do rozważenia jest efektywność wywołań digits[-1] w każdej iteracji pętli. Czy indeksowanie listy jest kosztowne? A może lepiej przechowywać ostatnią cyfrę w oddzielnej zmiennej i sprawdzać nią zamiast listy?

Odpowiedź na to pytanie pomoże nam znaleźć soundex/stage3/soundex3a.py:

digits2 = ''
    last_digit = ''
    for d in digits:
        if d != last_digit:
            digits2 += d
            last_digit = d

soundex3a.py nie działa ani trochę szybciej niż soundex2c.py, a nawet może być troszeczkę wolniejsze (aczkolwiek jest to za mała różnica, aby coś powiedzieć z całą pewnością):

C:\samples\soundex\stage3>python soundex3a.py
Woo             W000 11.5346048171
Pilgrim         P426 13.3950636184
Flingjingwaller F452 18.6108927252

Dlaczego soundex3a.py nie jest szybsze? Okazuje się, że indeksowanie list w Pythonie jest ekstremalnie efektywne. Powtarzanie dostępu do digits2[-1] nie stanowi w ogóle problemu. Z drugiej strony, kiedy manualnie zarządzamy ostatnią cyfrą w oddzielnej zmiennej, korzystamy z dwóch przypisań do zmiennych dla każdej przechowywanej cyfry, a te operacje zastępują mały koszt związany z korzystania z listy.

Spróbujemy teraz czegoś radykalnie innego. Jest możliwe, aby traktować dany napis jako listę znaków, zatem można byłoby wykorzystać wyrażenie listowe, aby przeiterować listę znaków. Jednak występuje problem związany z tym, że potrzebujemy dostępu do poprzedniego znaku w liście, a to nie jest łatwe w przypadku prostych wyrażeń listowych.

Jakkolwiek jest możliwe tworzenie listy liczbowych indeksów za pomocą wbudowanej funkcji range(), aby następnie wykorzystać te indeksy do stopniowego przeszukiwania listy i wybierania każdego znaku różnego od znaku poprzedzającego. Dzięki temu otrzymamy listę znaków, a następnie możemy wykorzystać metodę łańcucha znaków join(), aby zrekonstruować z tego listę.

Poniżej mamy soundex/stage3/soundex3b.py:

    digits2 = "".join([digits[i] for i in range(len(digits))
                       if i == 0 or digits[i-1] != digits[i]])

Czy jest to szybsze? Jednym słowem, nie.

C:\samples\soundex\stage3>python soundex3b.py
Woo             W000 14.2245271396
Pilgrim         P426 17.8337165757
Flingjingwaller F452 25.9954005327

Być może szybkie techniki powinny się skupiać wokół łańcuchów znaków. Python może konwertować łańcuch znaków na listę znaków za pomocą jednego polecenia: list('abc'), które zwróci ['a', 'b', 'c']. Ponadto listy mogą być bardzo szybko modyfikowane w miejscu. Zamiast zwiększać liczbę tworzonych nowych list (lub łańcuchów znaków) z naszego początkowego łańcucha, dlaczego nie przenieść wszystkich elementów do pojedynczej listy?

Poniżej przedstawiono soundex/stage3/soundex3c.py, który modyfikuje listę w miejscu i usuwa kolejno powtarzające się elementy:

    digits = list(source[0].upper() + source[1:].translate(charToSoundex))
    i=0
    for item in digits:
        if item==digits[i]: continue
        i+=1
        digits[i]=item
    del digits[i+1:]
    digits2 = "".join(digits)

Czy jest to szybsze od soundex3a.py lub soundex3b.py? Nie, w rzeczywistości działa to jeszcze wolniej:

C:\samples\soundex\stage3>python soundex3c.py
Woo             W000 14.1662554878
Pilgrim         P426 16.0397885765
Flingjingwaller F452 22.1789341942

Ciągle nie wykonaliśmy tutaj żadnego podstępu, z wyjątkiem tego, że wykorzystaliśmy i wypróbowaliśmy kilka "mądrych" technik. Najszybszym kodem, który jak dotąd widzieliśmy, nadal pozostał oryginał, najbardziej prosta metoda (soundex2c.py). Czasami nie popłaca być mądrym.

Przykład. Najlepszy wynik do tej pory: 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
    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())