Pythonを少し高速化するコーディング～内包表記とジェネレータ式とmap～

Pythonで同じ動作を実現させるのに複数通りの書き方が考えられる場合、どれを選ぶかは可読性と速度のバランスを考えて選びたいところ。そこで前から気になっていたコードの速度をいくつか比較してみた。

# 環境
- Google Colaboratory
- model: Intel(R) Xeon(R) CPU @ 2.20GHz (×2)
- Python version: 3.6.9 (default, Nov  7 2019, 10:44:02) 
[GCC 8.3.0]

# 測定方法
`%%timeit`を利用

# 問題1: リスト生成
Pythonで`list.append()`でリストを生成するのは遅いよという有名な話。以降、`N = 1000000`としている。

```Python
a = []
for i in range(N):
    a.append(i)
```
```
10 loops, best of 3: 96.9 ms per loop
```

メソッドの名前解決に地味な時間がかかっているので、変数にメソッドを代入しておくと多少若干速くなる。可読性は悪いが。

```Python
a = []
append = a.append
for i in range(N):
    append(i)
```
```
10 loops, best of 3: 70.2 ms per loop
```

また、`list.append()`は一定のサイズを超えるたびに新たなメモリを確保する(allocate)手間が発生する。そこであらかじめ長さを決めておくと若干速くなる。ただし上の方法よりも必ずしも速くなるとは限らない無い気がする。

```Python
a = [None] * N
for i in range(N):
    a[i] = i
```
```
10 loops, best of 3: 64.3 ms per loop
```

そして速いと評判なのが次のリスト内包表記である。記述も簡単なのでメリットは大きい。

```Python
a = [i for i in range(N)]
```
```
10 loops, best of 3: 58.6 ms per loop
```

もっとも、この例のようなことをやりたければ`list()`を使えば終わってしまうのだが。

```Python
a = list(range(N))
```
```
10 loops, best of 3: 35.9 ms per loop
```

# 問題2: map VS ジェネレータ式
この2つは機能がかなり似ている。ジェネレータ式は全て`map()`か`reduce()`に書き換え可能な気がしている。

言うまでもなく、`map()`とジェネレータ式はどちらもイテレータを生成するのだが、イテレータ生成は一瞬で終わってしまうので、後段の処理も含めて速度を比較する。

## 組み込み関数+リスト生成
組み込み関数`str()`を`range`オブジェクトに適用し、リストを生成する。

まずは素朴に`map`を`list()`で変換する。

```Python
a = list(map(str, range(N)))
```
```
10 loops, best of 3: 184 ms per loop
```

違和感はあるが、リテラルとアンパックを利用する方法もある。速度は変わらなかった。

```Python
a = [*map(str, range(N))]
```
```
10 loops, best of 3: 183 ms per loop
```

次はリスト内包表記との比較。これはジェネレータ式では無い気もするので、強引にジェネレータ式を使った場合も一応やってみた。結果はどちらも`map`より遅い！まさか`map`がリスト内包表記に勝つとは...

内包表記

```Python
a = [str(i) for i in range(N)]
```
```
1 loop, best of 3: 211 ms per loop
```

ジェネレータ式

```Python
a = list(str(i) for i in range(N))
```
```
1 loop, best of 3: 233 ms per loop
```

## 組み込み関数 + join()
続いてはイテレータを'str.join()'メソッドに渡す場合で測定。

map

```Python
a = ''.join(map(str, range(N)))
```
```
1 loop, best of 3: 201 ms per loop
```

ジェネレータ式

```Python
a = ''.join(str(i) for i in range(N))
```
```
1 loop, best of 3: 262 ms per loop
```

やはり、`map()`の勝利...。ちなみに、`join()`の引数をリストにしてみると面白い結果になる。通常、イテレータで済むところをわざわざリストに変換して関数に渡すと遅くなるはずである。しかし一部の関数については謎の最適化が発動し、リストを渡す方が速くなったりするのだ。

map

```Python
a = ''.join(list(map(str, range(N))))
```
```
1 loop, best of 3: 199 ms per loop
```

リスト内包表記

```Python
a = ''.join([str(i) for i in range(N)])
```
```
1 loop, best of 3: 242 ms per loop
```

なんと、`map()`の場合は全然変わらない！ジェネレータ式→リスト内包表記の場合は私の予想通り若干速くなった。`list()`にかかる時間が`join()`の僅かな高速化を打ち消したとでも言うのだろうか？一体何が起こっているPython...

## 自作関数 + join()
組み込み関数を次のように定義しなおしてどの程度遅くなるか調べる。

```Python
def tostr(x):
    return str(x)
```

map

```Python
a = ''.join(map(tostr, range(N)))
```
```
1 loop, best of 3: 277 ms per loop
```

ラムダ式を渡した場合

```Python
a = ''.join(map(lambda x: str(x), range(N)))
```
```
1 loop, best of 3: 292 ms per loop
```

ジェネレータ式

```Python
a = ''.join(tostr(i) for i in range(N))
```
```
1 loop, best of 3: 331 ms per loop
```

どれも順当に遅くなっただけで序列は変わらないすね....。ちなみに、この場合に限り自作関数をジェネレータ関数に書き換えてfor文回す方が、ジェネレータ式よりは速い。自作関数を毎ループ呼び出すよりは最初にジェネレータを生成して回す方が良いということであろう。まぁ、`map()`の方が速いですけどね。

## 演算式 + リスト生成
`map()`は必ず関数を渡さなければならないが、ジェネレータ式はその必要が無い。例えば演算式をそのまま`map()`に渡すことはできない。


```Python
def mod13(x):
    return x % 13
```

無理やりmap

```Python
a = list(map(mod13, range(N)))
```
```
10 loops, best of 3: 95.4 ms per loop
```

リスト内包表記

```Python
a = [x % 13  for x in range(N)]
```
```
10 loops, best of 3: 59.5 ms per loop
```

ジェネレータ式

```Python
a = list(x % 13 for x in range(N))
```
```
10 loops, best of 3: 79.2 ms per loop
```

自作関数 + リスト内包表記

```Python
%%timeit
a = [mod13(x) for x in range(N)]
```
```
10 loops, best of 3: 120 ms per loop
```


## メソッド + リスト生成
この場合も`map()`は自作関数が必要である。次のようにして上の場合と同じような実験を行った。


```Python
lis = list(map(str, range(N)))
def rstrip(x):
    return x.rstrip('0')
```

以降のコードは`range(N)`を`lis`に、`mod13`を`rstrip`に置き換えたものであり、結果は同じ序列になったので省略する。Pythonは自作関数へのアクセスが遅いようである。


# (おまけ) 問題3: print()
文字列のリストの各要素を`print()`するときは、for文を回すよりは'join()'を使う方が圧倒的に速いぞ（当たり前）

```Python
a = list(map(str, range(1000)))
```

```Python
%%time
for x in a:
    print(x, end=' ')
```
```
Wall time: 96.5 ms
```

```Python
%%time
print(' '.join(a), end=' ')
```
```
Wall time: 83.4 µs
```

オプション引数`sep`とアンパックを使う手も一応ある。全要素が文字列になってないときは出番かもしれないが、for文で回すのとあまり変わらない。

```Python
%%time
print(*a, sep=' ', end=' ')
```
```
Wall time: 94.4 ms
```



# 結論
- 自作関数の呼び出しはとても遅い。メソッド呼び出しもやや遅い。
- 組み込み関数だけで済むときは`map()`
- 自作関数を使わざるを得ないときも`map()`
    - `map()`, `filter()`を組み合わせたような複雑な処理をしたいときはジェネレータ関数
- それ以外はジェネレータ式