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

# きっかけ

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

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

思わず首を<ruby>傾<rt>かし</rt></ruby>げたくなるような[このcode](https://github.com/kivy/kivy/blob/9f74661fe444c1830563f370ac9f26b91ced2425/kivy/utils.py#L467-L478)に出会った。これは文字の置き換えを三回に分けて行っていて、そのせいで一時オブジェクトを二回余計に作っているパッと見酷いcodeである。私は`str.translate()`で置き換えてやらねばと思い次のような物を用意した。

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

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

```python
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
```

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

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

```
original: 34.63268039398827
modified: 289.20743604697054
```

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

# 環境

- CPytohn 3.8.1
- Kivy 2.0.0

# 調査

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

```python
text = 'Sun Moon' * 100
```

```
original: 3.905857544974424
modified: 4.276062361954246
```

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

## 一対一の置き換え

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

```python
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
```

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

## 一対零の置き換え

一対零の場合はというと

```python
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()`に軍配が上がるようだ。

```python
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
```

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

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

```python
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()`が圧勝するのか...と思いきやそうとも限らなかった。

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

```
replace  : 40.28116207703715
translate: 273.23075332300505
```

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

# まとめ

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