0. はじめに
みなさん、こんにちは。競技プログラミングを楽しんでいますか？
私は主にAtCoderで遊んでいて、使用言語はPythonです。
Pythonといえば、近年、機械学習関連の機運が高まったことにより注目されている言語であり、AtCoderでも競技プログラミングの主要言語であるC++に次いで人気の高い言語となっています。
しかし、一方でPythonはインタープリタ言語であり、「実行速度の遅い言語の代表格」として語られることも多いです。
競技プログラミングでは問題毎に決められた実行時間制限を満たすために、計算量がオーダーレベルで改善される効率的なアルゴリズムを考えることが主なタスクとなることが多いですが、Pythonでは良いアルゴリズムを考えても、その書き方が AC (正解)と TLE (実行時間超過) の分かれ目となる場合もあります。いわゆる定数倍高速化もPythonで競技プログラミングをやる場合には重要になります。そのため、インターネットで検索するとPythonの定数倍高速化について書かれた記事もいくつか出てきます。
- Pythonの知っておくと良い細かい処理速度の違い8個
- 実例から学ぶ Python競技プログラミングの定数倍高速化シリーズ1：徒競走
- 競技プログラミングにおけるPython定数倍高速化Tips
- Pythonで競プロをしよう！〜入門者が知っておくべきTips〜
- PythonでTLE, MLEが出たときに試すといいこと
- Pythonを高速にするTips集
本記事では、数あるPython高速化Tips記事にも登場しないであろう定数倍高速化 を紹介します。
本記事を読んで高速化テクニックを身につけ、「定数倍でTLE」とはおさらばしましょう！！
※注意
この記事はネタ記事です。本記事を読んで得られる情報が全くないということはないとは思いますが、「定数倍でTLEをしないために高速化テクニックを身につけたい」という目的を達成するためにはあまり役に立たないかもしれません。このような目的のためには上で紹介したような記事を読むことをお勧めします。
本記事での実行時間の計測にはAtCoderのコードテストPython(3.8.2)を使用しています。
1. 値のswap, rotate
１つ目は、値のswap, rotateです。
多くのプログラミング言語では、２つの変数の値を交換(swap)するためには、一時的な変数を用意しそこに片方の値を保存するという手続きを記述することになります。
a = 1
b = 2
print(a, b) # 1 2
# swap
tmp = a
a = b
b = tmp
print(a, b) # 2 1
しかし、Pythonでは一時的な変数を用意することなくswapを記述できます。
a = 1
b = 2
print(a, b) # 1 2
# swap
a, b = b, a
print(a, b) # 2 1
このような変数の値の交換は２つの変数だけではなく、３つ以上の変数についても同様に行うことができます。
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を使う場合と使わない場合で実行時間を計測しました。
例えば変数が４個の場合のコードは以下の通りです。
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モジュールを使ってPython内部の動きを見てみます。
まずは、２変数の場合です。以下のコードを実行し、tmpなしでswapする場合の内部の挙動を可視化します。
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に適した命令コードが存在したからです。
次に３変数の場合もみていきましょう。先ほどと同様に以下のコードを実行します。
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を用いない方が高速に実行されたわけです。
では、４変数の場合はどうでしょうか。
以下のコードを実行します。
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を用いた場合には
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 回書いた手続きだと思います）
ベースとなるコードは以下のものです。
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を使わない方法です。
交換の操作は
a, b, c, d, e, f, g, h, i, j \
= b, c, d, e, f, g, h, i, j, a
で、実行時間は $834 \;\rm{ms}$ でした。
次に、tmpを使う方法です。
「９変数の交換」を「３変数の交換を３回」に分割します。
交換の操作は
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に分割」をすると交換の操作は
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未満」と等価なので多くのプログラミング言語では
a <= b and b < c
のように書くと思います。
Pythonではより直感的に
a <= b < c
と書くこともでき、非常に便利です。
ですが、これもまた落とし穴になっています。それぞれの実行時間を次のコードで計測してみます。
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の場合です。
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
となります。
この手続きを日本語で書いてみると以下のようになります。
-
aへの参照を取得 -
bへの参照を取得 - 直近２つの取得された値を
<=で比較 -
Falseなら指定位置(手続き8)までジャンプしTrueなら結果を破棄 (andの部分) -
bへの参照を取得 -
cへの参照を取得 - 直近２つの取得された値を
<で比較 - 結果を破棄(今回の場合は条件判定をするだけなので)
予想通りというか、実際にコーディングした通りの挙動をしていますね。
次はa <= b < cの場合です。
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
となります。
こちらも日本語で手続きを記述してみましょう。
-
aへの参照を取得 -
bへの参照を取得 - 直近の取得した参照(
b)を複製 - 直近３つを順番をrotate(これで直近２つは
aとbになる) - 直近２つの取得された値を
<=で比較 -
Falseなら指定位置(手続き8)までジャンプしTrueなら結果を破棄 (andに相当) -
cへの参照を取得 - 直近２つの取得された値を
<で比較 - 結果を破棄
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 アスタリスク
最後はアスタリスク付きのアンパック代入についてです。
プログラミングをしていると、「リストの先頭の値と二番目以降を分けたい」と思うことが往々にしてあるかもしれません。そんな時にはアスタリスク付きのアンパック代入が使えます。
A = [0, 1, 2, 3]
a, *b = A
print(a) # 0
print(b) # [1, 2, 3]
より一般的には、先頭１つだけでなく、先頭と末尾からいくつかずつとそれ以外を分けることができます。
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
これもまた便利な記法ですが、やはり便利な記法には落とし穴が存在します。
以下のコードで同じ結果をもたらす２つの方法を比較してみます。
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:]の場合です。
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
となります。
手続きを日本語にすると、
-
Aへの参照を取得 -
0(aを得るためのindex)を取得 - 直近２つ(
A,0)からA[0]を取得 -
Aへの参照を取得 -
1とNoneを取得 - 直近２つからスライス
1:Noneを作成 - 直近２つ(
A,1:None)からA[1:]を取得 -
A[0]、A[1:]を適切に並び替えてa、bに代入
となります。
次に、a, *b = Aの場合をみていきます。
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が実行されてしまいます。
実際に試してみます。
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よりも実行速度が遅くなってしまいます。
一応、以下のコードで実行時間を計測してみます。
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. おわりに
いかがだったでしょうか？
最後にもう一度、ポイントをまとめておきます。
- 変数の値の同時交換は３変数までにしましょう
- 条件式の変数は自分の手で複製しましょう
- ３つ以下の変数へのアスタリスク付きのアンパック代入はやめましょう
どのテクニックも、「Pythonらしさ」、「快適さ」を犠牲にすることで驚くほど（わずかな）実行時間の改善ができます。
これらを駆使してぜひよい競プロライフをお過ごしください。
最後まで読んでいただきありがとうございました。おかしなところがありましたらコメント等でお教えください。