Warum ist str.translate in Python 3.5 viel schneller als in Python 3.4?

116

Ich habe versucht, unerwünschte Zeichen mit text.translate()Python 3.4 aus einer bestimmten Zeichenfolge zu entfernen .

Der minimale Code lautet:

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

Es funktioniert wie erwartet. Das gleiche Programm, wenn es in Python 3.4 und Python 3.5 ausgeführt wird, macht jedoch einen großen Unterschied.

Der Code zur Berechnung der Timings lautet

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

Das Python 3.4-Programm benötigt 1,3 ms, während das gleiche Programm in Python 3.5 nur 26,4 μs benötigt .

Was hat sich in Python 3.5 verbessert, das es im Vergleich zu Python 3.4 schneller macht?

Bhargav Rao
quelle
11
Wäre es nicht besser, Ihren Mapper so zu generieren, während wir über Leistung sprechen : dict.fromkeys(ord(c) for c in '@#$')?
Thomas K
1
@ThomasK Ich fand heraus, dass dies einen signifikanten Unterschied machte. Ja, dein Weg ist besser.
Bhargav Rao
Meinten Sie 50x schneller?
Assylias
@assylias Ich habe 1300 - 26.4 gemacht und dann durch 1300 geteilt. Ich habe fast 95% bekommen, also habe ich geschrieben :) Es ist tatsächlich mehr als 50x schneller ... Aber ist meine Berechnung falsch? Ich bin ein bisschen schwach in Mathe. Ich werde bald Mathe lernen. :)
Bhargav Rao
3
Sie sollten es umgekehrt machen: 26/1300 = 2%, damit die schnellere Version nur 2% der Zeit benötigt, die die langsamere Version benötigt => sie ist 50x schneller.
Assylias

Antworten:

148

TL; DR - AUSGABE 21118


Die lange Geschichte

Josh Rosenberg fand heraus, dass die str.translate()Funktion im Vergleich zu sehr langsam bytes.translateist. Er warf ein Problem auf und erklärte:

In Python 3 str.translate()handelt es sich normalerweise um eine Leistungspessimierung, nicht um eine Optimierung.

Warum war str.translate()langsam?

Der Hauptgrund dafür str.translate(), sehr langsam zu sein, war, dass sich die Suche früher in einem Python-Wörterbuch befand.

Die Verwendung von maketransmachte dieses Problem noch schlimmer. Bei einem ähnlichen Ansatz wird bytesein C-Array mit 256 Elementen erstellt, um eine schnelle Tabellensuche zu ermöglichen. Daher macht die Verwendung von höherstufigem Python dictdas str.translate()in Python 3.4 sehr langsam.

Was ist gerade passiert?

Der erste Ansatz bestand darin, einen kleinen Patch, translate_writer , hinzuzufügen. Die Geschwindigkeitssteigerung war jedoch nicht so erfreulich. Bald wurde ein weiterer Patch fast_translate getestet, der sehr gute Ergebnisse mit einer Beschleunigung von bis zu 55% lieferte.

Die wichtigste Änderung, die aus der Datei hervorgeht, besteht darin, dass die Python-Wörterbuchsuche in eine C-Level-Suche geändert wird.

Die Geschwindigkeiten sind jetzt fast die gleichen wie bytes

                                unpatched           patched

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

Eine kleine Anmerkung hier ist, dass die Leistungsverbesserung nur in ASCII-Zeichenfolgen prominent ist.

Wie JFSebastian in einem Kommentar unten erwähnt, funktioniert Übersetzen vor 3.5 in ASCII- und Nicht-ASCII-Fällen auf dieselbe Weise. Ab 3.5 ASCII ist der Fall jedoch viel schneller.

Früher waren ASCII und Nicht-ASCII fast gleich, jetzt können wir jedoch eine große Veränderung in der Leistung feststellen.

Dies kann eine Verbesserung von 71,6 μs auf 2,33 μs sein, wie in dieser Antwort gezeigt .

Der folgende Code demonstriert dies

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

Tabelle der Ergebnisse:

         Python 3.4    Python 3.5  
Ascii     91.2          2.3 
Unicode   101           117
Bhargav Rao
quelle
13
Dies ist eine der
Verpflichtungen
Hinweis: ASCII- und Nicht-ASCII-Fälle können sich in der Leistung erheblich unterscheiden. Es geht nicht um 55%: Wie Ihre Antwort zeigt, kann die Beschleunigung 1000s% betragen .
JFS
Vergleiche: 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)"(Nicht-ASCII). Letzteres ist viel (10x) langsamer.
JFS
@JF Oh, ich habe es jetzt verstanden. Ich habe Ihren Code für 3.4 und 3.5 ausgeführt. Ich bekomme Py3.4 schneller für Nicht-ASCII-Sachen. Ist es Zufall? Die Ergebnisse dpaste.com/15FKSDQ
Bhargav Rao
Vor 3.5 sind sowohl Ascii- als auch Nicht-Ascii-Fälle für Unicode wahrscheinlich gleich, .translate()dh, Ascii -Fälle sind nur in Python 3.5 viel schneller (Sie benötigen dort keine bytes.translate()Leistung).
JFS