教科書に載っていないPython定数倍高速化Tips

# 0. はじめに

みなさん、こんにちは。競技プログラミングを楽しんでいますか？
私は主に[AtCoder](https://atcoder.jp/)で遊んでいて、使用言語はPythonです。

Pythonといえば、近年、機械学習関連の機運が高まったことにより注目されている言語であり、AtCoderでも競技プログラミングの主要言語であるC++に次いで人気の高い言語となっています。
しかし、一方でPythonはインタープリタ言語であり、「**実行速度の遅い言語の代表格**」として語られることも多いです。

競技プログラミングでは問題毎に決められた実行時間制限を満たすために、計算量がオーダーレベルで改善される効率的なアルゴリズムを考えることが主なタスクとなることが多いですが、Pythonでは良いアルゴリズムを考えても、その書き方が **AC** (**正解**)と **TLE** (**実行時間超過**) の分かれ目となる場合もあります。いわゆる**定数倍高速化**もPythonで競技プログラミングをやる場合には重要になります。そのため、インターネットで検索するとPythonの定数倍高速化について書かれた記事もいくつか出てきます。


* [Pythonの知っておくと良い細かい処理速度の違い8個](https://www.kumilog.net/entry/python-speed-comp)
* [実例から学ぶ Python競技プログラミングの定数倍高速化シリーズ1：徒競走](https://linus-mk.hatenablog.com/entry/python_competitive_programming_speed_up_1)
* [競技プログラミングにおけるPython定数倍高速化Tips](https://qiita.com/cakesenbei/items/193732fa026b88b9616c)
* [Pythonで競プロをしよう！〜入門者が知っておくべきTips〜](https://medium.com/finatext/lets-do-competitive-programming-with-python-9c8b834769f6)
* [PythonでTLE, MLEが出たときに試すといいこと](https://qiita.com/Ll_e_ki/items/e64cf06705bd5d16a6e9)
* [Pythonを高速にするTips集](https://cafeunder.github.io//rosenblock-chainers-blog/2018/04/24/Python-Tips.html)

本記事では、**数あるPython高速化Tips記事にも登場しないであろう定数倍高速化** を紹介します。
本記事を読んで高速化テクニックを身につけ、「**定数倍でTLE**」とはおさらばしましょう！！



***

**※注意**

この記事は**ネタ記事**です。本記事を読んで得られる情報が全くないということはないとは思いますが、「定数倍でTLEをしないために高速化テクニックを身につけたい」という目的を達成するためにはあまり役に立たないかもしれません。このような目的のためには上で紹介したような記事を読むことをお勧めします。


***

本記事での実行時間の計測にはAtCoderのコードテストPython(3.8.2)を使用しています。


# 1. 値のswap, rotate

１つ目は、値のswap, rotateです。
多くのプログラミング言語では、２つの変数の値を交換(swap)するためには、一時的な変数を用意しそこに片方の値を保存するという手続きを記述することになります。

```python
a = 1
b = 2
print(a, b) # 1 2

# swap
tmp = a
a = b
b = tmp

print(a, b) # 2 1
```

しかし、Pythonでは一時的な変数を用意することなくswapを記述できます。

```python
a = 1
b = 2
print(a, b) # 1 2

# swap
a, b = b, a

print(a, b) # 2 1
```


このような変数の値の交換は２つの変数だけではなく、３つ以上の変数についても同様に行うことができます。


```python
a = 1
b = 2
c = 3
d = 4
e = 5
print(a, b, c, d, e) # 1 2 3 4 5

# 値の交換
a, b, c, d, e = c, e, d, a, b

print(a, b, c, d, e) # 3 5 4 1 2
```


便利ですね！
ですが、ここに落とし穴があります。
変数の数が 2 ~ 4 個の場合について一時変数`tmp`を使う場合と使わない場合で実行時間を計測しました。
例えば変数が４個の場合のコードは以下の通りです。

```python
def main():
    a, b, c, d = 0, 1, 2, 3
    for _ in range(10**7):
        # tmpなし
        a, b, c, d = b, c, d, a

        # tmpあり
        #tmp = a
        #a, b, c = b, c, d
        #d = tmp
      
if __name__ == '__main__':
    main()
```

結果は次の表のようになりました。

|変数の数|tmpなし|tmpあり|
|:-:|:-:|:-:|
|2|$255 \\;\rm{ms}$|$294 \\;\rm{ms}$|
|3|$311 \\;\rm{ms}$|$334 \\;\rm{ms}$|
|4|$534 \\;\rm{ms}$|$376 \\;\rm{ms}$|

変数が２個、３個の時には`tmp`を使わない方が速く、４個の時には`tmp`を使った方が速くなりました。

なぜこのようなことが起こるのでしょうか？これを解明するためにPython標準の[disモジュール](https://docs.python.org/ja/3/library/dis.html)を使ってPython内部の動きを見てみます。

まずは、２変数の場合です。以下のコードを実行し、`tmp`なしでswapする場合の内部の挙動を可視化します。

```python
import dis

def f(a, b):
    a, b = b, a

dis.dis(f)
```

これを実行すると以下のようになると思います。

```
4             0 LOAD_FAST                1 (b)
              2 LOAD_FAST                0 (a)
              4 ROT_TWO
              6 STORE_FAST               0 (a)
              8 STORE_FAST               1 (b)
             10 LOAD_CONST               0 (None)
             12 RETURN_VALUE
```

注目するのは３行目で、`ROT_TWO`という操作が行われています。２変数の場合に一時変数`tmp`を使用しない方が高速だったのは`ROT_TWO`という、２変数のswapに適した命令コードが存在したからです。

次に３変数の場合もみていきましょう。先ほどと同様に以下のコードを実行します。

```python
import dis

def f(a, b, c):
    a, b, c = b, c, a

dis.dis(f)
```

結果は次のようになります。

```
 4            0 LOAD_FAST                1 (b)
              2 LOAD_FAST                2 (c)
              4 LOAD_FAST                0 (a)
              6 ROT_THREE
              8 ROT_TWO
             10 STORE_FAST               0 (a)
             12 STORE_FAST               1 (b)
             14 STORE_FAST               2 (c)
             16 LOAD_CONST               0 (None)
             18 RETURN_VALUE
```

４、５行目で`ROT_THREE`、`ROT_TWO`という操作が行われています。３変数の場合にも値の交換に適した命令コードが存在するので一時変数`tmp`を用いない方が高速に実行されたわけです。

では、４変数の場合はどうでしょうか。
以下のコードを実行します。

```python
import dis

def f(a, b, c, d):
    a, b, c, d = b, c, d, a

dis.dis(f)
```

結果は次のようになります。

```
4             0 LOAD_FAST                1 (b)
              2 LOAD_FAST                2 (c)
              4 LOAD_FAST                3 (d)
              6 LOAD_FAST                0 (a)
              8 BUILD_TUPLE              4
             10 UNPACK_SEQUENCE          4
             12 STORE_FAST               0 (a)
             14 STORE_FAST               1 (b)
             16 STORE_FAST               2 (c)
             18 STORE_FAST               3 (d)
             20 LOAD_CONST               0 (None)
             22 RETURN_VALUE
```

４変数の場合には、`ROT_TWO`や`ROT_THREE`ではなく、`BUILD_TUPLE`、`UNPACK_SEQUENCE`という操作が行われます。
すなわち４変数の場合には「右辺を一度タプルにして、それをアンパックして左辺に代入する」という操作が行われています。
一方、一時変数`tmp`を用いた場合には

```python
def f(a, b, c, d):
    tmp = a
    a, b, c = b, c, d
    d = tmp
```

で、`a, b, c = b, c, d`の部分は３変数の値の交換になるので先ほど見たように命令コード`ROT_TWO`や`ROT_THREE`を用いた操作が行われます。

つまり、４変数の場合には「タプルを作成しそれをアンパックする」という操作が重いため、一時変数`tmp`を用いた場合より用いない場合の方が実行速度が遅くなってしまったわけです。

では、５変数以上の場合にはどうでしょうか？この場合、`tmp`を使っても４変数以上の値の交換になるので、３変数以下の「速い操作」が行われず、さらに`tmp`を用意する手間もかかるので`tmp`を使わない方が速くなります。
しかし、$N$ 変数の値の交換において、`tmp`を使う場合には $N-1$ 変数の交換を同時に行う必要はありません。そこで $N-1$ 変数の交換を **３変数以下の交換に分割**します。すると、「速い操作」が行われるので、`tmp`を使わない場合よりも高速に実行することができます。

実際にこの方法が上手くいくことを確認してみましょう。題材は競技プログラミングでよく現れる「１０変数の交換を $10^7$ 回繰り返す」手続きです。（誰もが INF 回書いた手続きだと思います）


ベースとなるコードは以下のものです。


```python
def main():
    a, b, c, d, e, f, g, h, i, j = list(range(10))
    for _ in range(10**7):
        # ここに交換の操作を書く


if __name__ == '__main__':
    main()
```


まずは`tmp`を使わない方法です。
交換の操作は

```python
a, b, c, d, e, f, g, h, i, j \
    = b, c, d, e, f, g, h, i, j, a
```

で、実行時間は $834 \\;\rm{ms}$ でした。

次に、`tmp`を使う方法です。
「９変数の交換」を「３変数の交換を３回」に分割します。
交換の操作は

```python
tmp = a
a, b, c = b, c, d
d, e, f = e, f, g
g, h, i = h, i, j
j = tmp
```

で、実行時間は $624 \\;\rm{ms}$ となり、なんと $\boldsymbol{200 \\;\rm{ms}}$ **もの改善に成功**しました。

ちなみに、「出来るだけ２変数のswapに分割」をすると交換の操作は

```python
tmp = a
a, b = b, c
c, d = d, e
e, f = f, g
g, h, i = h, i, j
j = tmp
```

で実行時間は $602 \\;\rm{ms}$ となり、さらに高速化できます。


本章で分かったこと：

***

**変数の値の同時交換は３変数までにしましょう**

***





# 2. 条件式

２つ目は条件式についてです。
条件式は、一つの条件からなる単純なものから、複数の条件を複合した複雑なものまで様々なものを書きますが、本章では「３つの数値の比較」に焦点を当ててみます。



具体的には、「３つの数値`a, b, c`について、`b`が半開区間 $[a, c)$ に含まれるかどうか」という条件式を考えます。この条件はもちろん「`b` が `a`以上でかつ`b`が`c`未満」と等価なので多くのプログラミング言語では

```python
a <= b and b < c
```

のように書くと思います。
Pythonではより直感的に

```python
a <= b < c
```

と書くこともでき、非常に便利です。
ですが、これもまた落とし穴になっています。それぞれの実行時間を次のコードで計測してみます。

```python
def main():
    a, b, c = 0, 1, 2
    for _ in range(10**7):
        a <= b and b < c
        
        #a <= b < c
        
if __name__ == '__main__':
    main()
```

結果は下表のようになりました。

|`a <= b and b < c`|`a <= b < c`|
|:-:|:-:|
|$480 \\;\rm{ms}$|$501 \\;\rm{ms}$|


なんと $10^7$ 回の条件判定で $20 \\;\rm{ms}$ もの差がつきました。
なぜこのような結果になったのか、やはり`dis`モジュールを使ってみていきましょう。

まずは`a <= b and b < c`の場合です。

```python
import dis

def f(a, b, c):
    a <= b and b < c

dis.dis(f)
```

を実行すると


```
  4           0 LOAD_FAST                0 (a)
              2 LOAD_FAST                1 (b)
              4 COMPARE_OP               1 (<=)
              6 JUMP_IF_FALSE_OR_POP    14
              8 LOAD_FAST                1 (b)
             10 LOAD_FAST                2 (c)
             12 COMPARE_OP               0 (<)
        >>   14 POP_TOP
             16 LOAD_CONST               0 (None)
             18 RETURN_VALUE
```

となります。
この手続きを日本語で書いてみると以下のようになります。

1. `a`への参照を取得
2. `b`への参照を取得
3. 直近２つの取得された値を `<=` で比較
4. `False`なら指定位置(手続き8)までジャンプし`True`なら結果を破棄 (`and`の部分)
5. `b`への参照を取得
6. `c`への参照を取得
7. 直近２つの取得された値を `<` で比較
8. 結果を破棄(今回の場合は条件判定をするだけなので)

予想通りというか、実際にコーディングした通りの挙動をしていますね。

次は`a <= b < c`の場合です。

```python
import dis

def f(a, b, c):
    a <= b < c

dis.dis(f)
```

を実行すると

```
  4           0 LOAD_FAST                0 (a)
              2 LOAD_FAST                1 (b)
              4 DUP_TOP
              6 ROT_THREE
              8 COMPARE_OP               1 (<=)
             10 JUMP_IF_FALSE_OR_POP    18
             12 LOAD_FAST                2 (c)
             14 COMPARE_OP               0 (<)
             16 JUMP_FORWARD             4 (to 22)
        >>   18 ROT_TWO
             20 POP_TOP
        >>   22 POP_TOP
             24 LOAD_CONST               0 (None)
             26 RETURN_VALUE
```

となります。
こちらも日本語で手続きを記述してみましょう。

1. `a`への参照を取得
2. `b`への参照を取得
3. 直近の取得した参照(`b`)を複製
4. 直近３つを順番をrotate(これで直近２つは`a`と`b`になる)
5. 直近２つの取得された値を `<=` で比較
6. `False`なら指定位置(手続き8)までジャンプし`True`なら結果を破棄 (`and`に相当)
7. `c`への参照を取得
8. 直近２つの取得された値を `<` で比較
9. 結果を破棄

`a <= b and b < c`の場合を比較すると、「`b`への参照を取得」が１回減り、「`b`の複製」と「直近３つを順番をrotate」という操作が新たに加わったことがわかります。つまり、この違いが $20 \\;\rm{ms}$ の差を生み出していたわけです。

$10^7$ 回で $20 \\;\rm{ms}$ ということは１回あたり $2 \times 10^{-6}\\;\rm{ms}$ です。
「`b` を２回書き、間を`and`で繋げる」という手間をかけるだけで１回あたり $2 \times 10^{-6}\\;\rm{ms}$ もの実行時間の短縮ができるわけですから、どちらの記法で書けば良いかは明白ですね！

本章で分かったこと：

***

**条件式の変数は自分の手で複製しましょう**

***



# 3. アンパック代入 with アスタリスク

最後はアスタリスク付きのアンパック代入についてです。
プログラミングをしていると、「リストの先頭の値と二番目以降を分けたい」と思うことが往々にしてあるかもしれません。そんな時にはアスタリスク付きのアンパック代入が使えます。

```python
A = [0, 1, 2, 3]

a, *b = A

print(a) # 0
print(b) # [1, 2, 3]
```

より一般的には、先頭１つだけでなく、先頭と末尾からいくつかずつとそれ以外を分けることができます。

```python
A = [0, 1, 2, 3, 4, 5, 6, 7]

a, b, *c, d, e, f = A

print(a) # 0
print(b) # 1
print(c) # [2, 3, 4]
print(d) # 5
print(e) # 6
print(f) # 7
```

これもまた便利な記法ですが、やはり便利な記法には落とし穴が存在します。

以下のコードで同じ結果をもたらす２つの方法を比較してみます。

```python
def main():
    A = [0, 1, 2, 3, 4]
    for _ in range(10**7):
        a, b = A[0], A[1:]
        
        #a, *b = A
      
if __name__ == '__main__':
    main()
```

結果は下表のようになりました。

|`a, b = A[0], A[1:]`|`a, *b = A`|
|:-:|:-:|
|$921 \\;\rm{ms}$|$1162 \\;\rm{ms}$|


これまでと同様に、なぜこうなったのか内部をみていきましょう。

まず、`a, b = A[0], A[1:]`の場合です。

```python
import dis
A = [0, 1, 2, 3, 4]

def f(A):
    a, b = A[0], A[1:]

dis.dis(f)
```

を実行すると

```
  5           0 LOAD_FAST                0 (A)
              2 LOAD_CONST               1 (0)
              4 BINARY_SUBSCR
              6 LOAD_FAST                0 (A)
              8 LOAD_CONST               2 (1)
             10 LOAD_CONST               0 (None)
             12 BUILD_SLICE              2
             14 BINARY_SUBSCR
             16 ROT_TWO
             18 STORE_FAST               1 (a)
             20 STORE_FAST               2 (b)
             22 LOAD_CONST               0 (None)
             24 RETURN_VALUE
```

となります。
手続きを日本語にすると、

1. `A`への参照を取得
2. `0`(`a`を得るためのindex)を取得
3. 直近２つ(`A`, `0`)から`A[0]`を取得
4. `A`への参照を取得
5. `1`と`None`を取得
6. 直近２つからスライス `1:None`を作成
7. 直近２つ(`A`, `1:None`)から`A[1:]`を取得
8. `A[0]`、`A[1:]`を適切に並び替えて `a`、`b`に代入

となります。

次に、`a, *b = A`の場合をみていきます。

```python
import dis
A = [0, 1, 2, 3, 4]

def f(A):
    a, *b = A

dis.dis(f)
```

を実行すると

```
  5           0 LOAD_GLOBAL              0 (A)
              2 UNPACK_EX                1
              4 STORE_FAST               0 (a)
              6 STORE_FAST               1 (b)
              8 LOAD_CONST               0 (None)
             10 RETURN_VALUE
```

となります。
先ほどは無かった`UNPACK_EX`という命令コードがあり、これが全てを行なっているようです。
つまり、この`UNPACK_EX`が重いため、`a, *b = A`は実行速度が遅くなってしまったわけです。

では、アンパック代入を一切使用しなければ良いかというとそうでもありません。
気付いた方もいるかと思いますが、`a, b = A[0], A[1:]`の場合において`A[0]`と`A[1:]`を取得した後の手続きは、まさに第１章でみた「複数の値の複数の変数への代入」そのものです。つまり、４変数以上になると命令コード`BUILD_TUPLE`、`UNPACK_SEQUENCE`が実行されてしまいます。
実際に試してみます。

```python
import dis
A = [0, 1, 2, 3, 4]

def f(A):
    a, b, c, d = A[0], A[1], A[2], A[3:]

dis.dis(f)
```

を実行すると

```
  5           0 LOAD_FAST                0 (A)
              2 LOAD_CONST               1 (0)
              4 BINARY_SUBSCR
              6 LOAD_FAST                0 (A)
              8 LOAD_CONST               2 (1)
             10 BINARY_SUBSCR
             12 LOAD_FAST                0 (A)
             14 LOAD_CONST               3 (2)
             16 BINARY_SUBSCR
             18 LOAD_FAST                0 (A)
             20 LOAD_CONST               4 (3)
             22 LOAD_CONST               0 (None)
             24 BUILD_SLICE              2
             26 BINARY_SUBSCR
             28 BUILD_TUPLE              4
             30 UNPACK_SEQUENCE          4
             32 STORE_FAST               1 (a)
             34 STORE_FAST               2 (b)
             36 STORE_FAST               3 (c)
             38 STORE_FAST               4 (d)
             40 LOAD_CONST               0 (None)
             42 RETURN_VALUE

```

となり、`28`、`30`の部分で確かに`BUILD_TUPLE`、`UNPACK_SEQUENCE`が実行されていることがわかります。そのため、この方法では`A[0], A[1]...`の取得 + `BUILD_TUPLE`、`UNPACK_SEQUENCE`の手間がかかるので、`UNPACK_EX`のみで完結する`a, b, c, *d = A`よりも実行速度が遅くなってしまいます。
一応、以下のコードで実行時間を計測してみます。

```python
def main():
    A = [0, 1, 2, 3, 4]
    for _ in range(10**7):
      	a, b, c, d = A[0], A[1], A[2], A[3:]
        
        #a, b, c, *d = A
        
      
if __name__ == '__main__':
    main()
```


結果は下表のようになりました。

|`a, b, c, d = A[0], A[1], A[2], A[3:]`|`a, b, c, *d = A`|
|:-:|:-:|
|$1424 \\;\rm{ms}$|$1218 \\;\rm{ms}$|

確かに、アンパック代入を使った方が速くなっていますね！


本章で分かったこと：

***

**３つ以下の変数へのアスタリスク付きのアンパック代入はやめましょう**

***




# 4. おわりに

いかがだったでしょうか？
最後にもう一度、ポイントをまとめておきます。

1. 変数の値の同時交換は３変数までにしましょう
2. 条件式の変数は自分の手で複製しましょう
3. ３つ以下の変数へのアスタリスク付きのアンパック代入はやめましょう

どのテクニックも、**「Pythonらしさ」、「快適さ」を犠牲にすることで驚くほど（~~わずかな~~）実行時間の改善ができます。**

これらを駆使してぜひよい競プロライフをお過ごしください。

最後まで読んでいただきありがとうございました。おかしなところがありましたらコメント等でお教えください。