str.translate()が速いとは限らない

きっかけ

Kivyのsource codeを眺めていた時の事である。

def escape_markup(text):
    return text.replace('&', '&').replace('[', '&bl;').replace(']', '&br;')

思わず首を傾かしげたくなるようなこのcodeに出会った。これは文字の置き換えを三回に分けて行っていて、そのせいで一時オブジェクトを二回余計に作っているパッと見酷いcodeである。私はstr.translate()で置き換えてやらねばと思い次のような物を用意した。

def new_escape_markup(
        text, *,
        _table=str.maketrans({'&': '&', '[': '&bl;', ']': '&br;', })):
    return text.translate(_table)

文字の置き換えを纏まとめて行っているこっちの方が当然速いだろうと思っていたのですが実際に測ってみると

from timeit import timeit
from kivy.utils import escape_markup

text = 'Sun [1] & Moon [2].'
print('original:', timeit(lambda: escape_markup(text)))
print('modified:', timeit(lambda: new_escape_markup(text)))

original: 3.053685157035943
modified: 4.637238892959431

なんと遅くなってしまった。そして変換前の文字列をもっと長くしてみると

text = 'Sun [1] & Moon [2].' * 100

original: 34.63268039398827
modified: 289.20743604697054

**さらに差が開いてしまった。**どうやら文字を置き換えたいからといって脳死でstr.translate()を使うのはまずそうである。というわけでどういった場面でそれを使うべきなのか調べてみた。

環境

• CPytohn 3.8.1
• Kivy 2.0.0

調査

上の結果を見るに文字の置き換えが起これば起こるほど元の物との差が開いている気がする。そこで試しにmarkupの制御文字を全く含まない文字列を与えてみると

text = 'Sun Moon' * 100

original: 3.905857544974424
modified: 4.276062361954246

それでも遅かった。このままだとstr.translate()の存在理由が分からないので、どうにかして輝く場面を見つけないといけない。

一対一の置き換え

escape_markup()は文字一つを複数の文字に置き換えているため一対多である。これを一対一にしてみるとどうなったかというと

from timeit import timeit

def ver_replace(text):
    return text.replace('a', 'あ').replace('i', 'い').replace('u', 'う')

def ver_translate(
        text, *,
        _table=str.maketrans({'a': 'あ', 'i': 'い', 'u': 'う', })):
    return text.translate(_table)


text = 'abcdefghijklmnopqrstuvwxyz' * 100
print('replace  :', timeit(lambda: ver_replace(text)))
print('translate:', timeit(lambda: ver_translate(text)))

replace  : 9.565487537009176
translate: 255.94812944100704

やはりとんでもなく遅い。

一対零の置き換え

一対零の場合はというと

from timeit import timeit

def ver_replace(text):
    return text.replace('a', '').replace('i', '').replace('u', '')

def ver_translate(
        text, *,
        _table=str.maketrans({'a': None, 'i': None,  'u': None, })):
    return text.translate(_table)


text = 'abcdefghijklmnopqrstuvwxyz' * 100
print('replace  :', timeit(lambda: ver_replace(text)))
print('translate:', timeit(lambda: ver_translate(text)))

replace  : 19.761723625997547
translate: 8.692913369974121

ようやくreplace()に勝てる場面があった！ ただ流石に一種類の文字しか置き換えない場合はreplace()に軍配が上がるようだ。

def ver_replace(text):
    return text.replace('a', '')

def ver_translate(
        text, *,
        _table=str.maketrans({'a': None, })):
    return text.translate(_table)

replace  : 8.296030605968554
translate: 8.77228491101414

もっと多くの種類の文字を置き換える

一対零の置き換えでしか勝てる場面がないなんて流石に酷すぎる、という事で他に何かないか探さないといけない。変換対象の文字を増やすとどうなるだろうか？

from timeit import timeit

lowers = 'abcdefghijklmnopqrstuvwxyz'
uppers = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'

def ver_replace(text):
    for before, after in zip(lowers, uppers):
        text = text.replace(before, after)
    return text

def ver_translate(
        text, *,
        _table=str.maketrans({before: after for before, after in zip(lowers, uppers) })):
    return text.translate(_table)


text = 'Python is Awesome ' * 100
print('replace  :', timeit(lambda: ver_replace(text)))
print('translate:', timeit(lambda: ver_translate(text)))

replace  : 26.42025518801529
translate: 5.544265289965551

なんだ変換対象の文字が多ければtranslate()が圧勝するのか...と思いきやそうとも限らなかった。

text = 'Python is Awesome パイソンは素晴らしい ' * 100

replace  : 40.28116207703715
translate: 273.23075332300505

このように変換元の文字列に変換対象以外の文字がある程度含まれている場合はやはりtranslate()が負けるのだ。

まとめ

str.translate()がstr.replace()に速度で勝つためには変換対象の文字がたくさんあって、なおかつ変換元の文字列に含まれる変換対象の文字の割合が多くないといけないようである。