Dlaczego str.translate jest znacznie szybsze w Pythonie 3.5 w porównaniu z Pythonem 3.4?

116

Próbowałem usunąć niechciane znaki z danego ciągu używając text.translate()w Pythonie 3.4.

Minimalny kod to:

import sys 
s = 'abcde12345@#@$#%$'
mapper = dict.fromkeys(i for i in range(sys.maxunicode) if chr(i) in '@#$')
print(s.translate(mapper))

Działa zgodnie z oczekiwaniami. Jednak ten sam program wykonywany w Pythonie 3.4 i Pythonie 3.5 daje dużą różnicę.

Kod do obliczania czasów to

python3 -m timeit -s "import sys;s = 'abcde12345@#@$#%$'*1000 ; mapper = dict.fromkeys(i for i in range(sys.maxunicode) if chr(i) in '@#$'); "   "s.translate(mapper)"

Program w Pythonie 3.4 zajmuje 1,3 ms, podczas gdy ten sam program w Pythonie 3.5 zajmuje tylko 26,4 μs .

Co poprawiło się w Pythonie 3.5, co sprawia, że ​​jest szybsze w porównaniu z Pythonem 3.4?

Bhargav Rao
źródło
11
Chociaż mówimy o wydajności, nie byłoby lepiej, aby wygenerować mapowania tak: dict.fromkeys(ord(c) for c in '@#$')?
Thomas K
1
@ThomasK Dowiedziałem się, że zrobiło to znaczącą różnicę. Tak, twoja droga jest lepsza.
Bhargav Rao
Czy chodziło Ci o 50x szybciej?
assylias
@assylias Zrobiłem 1300 - 26,4, a potem podzieliłem przez 1300. Uzyskałem prawie 95%, więc napisałem :) W rzeczywistości jest ponad 50x szybciej ... Ale czy moje obliczenia są złe? Jestem trochę słaby z matematyki. Wkrótce nauczę się matematyki. :)
Bhargav Rao
3
powinieneś to zrobić na okrągło: 26/1300 = 2%, więc szybsza wersja zajmuje tylko 2% czasu wolniejszej wersji => jest 50x szybsza.
assylias

Odpowiedzi:

148

TL; DR - WYDANIE 21118


Długa historia

Josh Rosenberg odkrył, że str.translate()funkcja jest bardzo powolna w porównaniu do bytes.translate, podniósł problem , stwierdzając, że:

W Pythonie 3 str.translate()jest to zwykle pesymizacja wydajności, a nie optymalizacja.

Dlaczego był str.translate()wolny?

Głównym powodem, dla którego str.translate()było to bardzo powolne, był fakt, że wyszukiwanie odbywało się w słowniku Pythona.

Użycie maketransgo pogorszyło ten problem. Podobne podejście przy użyciu bytesbuduje tablicę C składającą się z 256 elementów w celu szybkiego wyszukiwania tabeli. Stąd użycie wyższego poziomu Pythona dictpowoduje, że str.translate()w Pythonie 3.4 jest bardzo powolny.

Co się teraz stało?

Pierwszym podejściem było dodanie małej łatki translate_writer , jednak wzrost szybkości nie był tak przyjemny. Wkrótce testowano kolejną łatkę fast_translate, która dała bardzo dobre wyniki, nawet o 55% przyspieszenia.

Główna zmiana, jak widać z pliku, polega na tym, że przeszukiwanie słownika Pythona zostało zmienione na wyszukiwanie na poziomie C.

Prędkości są teraz prawie takie same jak bytes

                                unpatched           patched

str.translate                   4.55125927699919    0.7898181750006188
str.translate from bytes trans  1.8910855210015143  0.779950579000797

Mała uwaga w tym miejscu jest taka, że ​​zwiększenie wydajności jest widoczne tylko w łańcuchach ASCII.

Jak JFSebastian wspomina w komentarzu poniżej, przed 3.5, tłumaczenie działało w ten sam sposób zarówno dla przypadków ASCII, jak i innych niż ASCII. Jednak od 3.5 ASCII sprawa jest znacznie szybsza.

Wcześniej ASCII i inne niż ASCII były prawie takie same, ale teraz widzimy wielką zmianę w wydajności.

Może to być poprawa z 71,6 μs do 2,33 μs, jak widać w tej odpowiedzi .

Poniższy kod demonstruje to

python3.5 -m timeit -s "text = 'mJssissippi'*100; d=dict(J='i')" "text.translate(d)"
100000 loops, best of 3: 2.3 usec per loop
python3.5 -m timeit -s "text = 'm\U0001F602ssissippi'*100; d={'\U0001F602': 'i'}" "text.translate(d)"
10000 loops, best of 3: 117 usec per loop

python3 -m timeit -s "text = 'm\U0001F602ssissippi'*100; d={'\U0001F602': 'i'}" "text.translate(d)"
10000 loops, best of 3: 91.2 usec per loop
python3 -m timeit -s "text = 'mJssissippi'*100; d=dict(J='i')" "text.translate(d)"
10000 loops, best of 3: 101 usec per loop

Tabela wyników:

         Python 3.4    Python 3.5  
Ascii     91.2          2.3 
Unicode   101           117
Bhargav Rao
źródło
13
To jest jedno z zatwierdzeń: github.com/python/cpython/commit/ ...
filmor
uwaga: przypadek ascii vs non-ascii może znacznie różnić się wydajnością. Nie chodzi o 55%: jak pokazuje twoja odpowiedź, przyspieszenie może wynosić 1000s% .
jfs
porównaj: python3.5 -m timeit -s "text = 'mJssissippi'*100; d=dict(J='i')" "text.translate(d)"(ascii) vs. python3.5 -m timeit -s "text = 'm\U0001F602ssissippi'*100; d={'\U0001F602': 'i'}" "text.translate(d)"(non-ascii). Ta ostatnia jest dużo (10x) wolniejsza.
jfs
@JF Och, teraz to zrozumiałem. Uruchomiłem Twój kod dla wersji 3.4 i 3.5. Uzyskuję Py3.4 szybciej dla rzeczy innych niż ASCII. Czy to przypadek? Wyniki dpaste.com/15FKSDQ
Bhargav Rao
Przed wersją 3.5, zarówno przypadki ascii, jak i nie-ascii są prawdopodobnie takie same dla Unicode, .translate()tj. Wielkość liter ascii jest znacznie szybsza tylko w Pythonie 3.5 (nie potrzebujesz bytes.translate()tam wydajności).
jfs