Pythonでの無限大の書き方と速さ検証

　競プロでは値を無限大（とにかく大きな値）にしておいて，更新するときに書き換えるという処理をすることが結構あります．
　いつだったかのAtcoder ABCで無限大の書き方を変えるだけでTLEがACになったのが衝撃的だったので記事に纏めます．

始めに
float("inf")
10**18
1<<60
INF= と代入
速さ比べ
結論

始めに

　Pythonを高速に動かすPyPyでは大きな値として $2^{64}$ を超える値を使うと動作が遅くなるらしいです．https://qiita.com/c-yan/items/dbf2838cdd89864ef5ac#%E7%84%A1%E9%99%90%E5%A4%A7
　大きな値を代入するときはこれに気をつける必要があります．

float("inf")

　”python 無限大”で検索して一番始めに出てくるのがこれだと思います．私も初めはこの方法を使っていました．float("inf")の動作は以下のサイトが詳しいです．https://note.nkmk.me/python-inf-usage/

10**18

　とにかく大きな値ということで分かりやすいのがこれです．18乗で無くてはいけないわけでは無く，問題の制約を見て絶対に取り得ないような大きな値を取るのが大切です．ただ，始めにで述べたように $2^{64}$ を超えない方が良いと思われます．そのため余裕を持って $10^{18} \leq 2^{63} \leq 10^{19}$ が成り立つ18乗を使っています．

10**18 < 2**63 < 10**19
>> True

1<<60

　これもとにかく大きな値です．a << bはaをbビット左シフトします．例えば，1<<2は1を2ビット分左に移動させるので100となり，これを10進法で4となります．始めにで述べたように $2^{64}$ を超えず，加算する可能性も考え1<<60とします．これは $2^{60}$ と同値です．

1<<60 < 2**63
>>True
1<<60 
>> 1152921504606846976

INF= と代入

　無限大を色々な所で使うとき，毎回上3つのどれかを使うのでは無くINFという定数に入れておく事で，毎回無限大を生成する事が無く早くなると思われます．

速さ比べ

　上記の3方法にINFを代入するしないの計6方法に対して速さを計測します．以下のコードを使いました．10**6個無限大を生成し，その値をfor文で書き換えます．これを100回繰り返し，平均を取ります．

import time

sum_time = 0

for i in range(100):
    start = time.time()
    lis = [[10**18] for i in range(10**6)]
    for i in range(10**6):
        lis[i] = i

    this_time = time.time() - start
    sum_time += this_time

print(sum_time/100)

10**18となっているところをfloat("inf")などそれぞれの方法に書き換えます．これはINFで代入しないパターンでINFに代入するパターンは

INF = 10**18
lis = [INF for i in range(10**6)]

と書き換えます．
　結果は下の表になります．

	時間
float("inf") INF代入なし	0.46491264820098877
float("inf") INF代入あり	0.1965283489227295
10**18 INF代入なし	0.1875119090080261
10**18 INF代入あり	0.20195421934127808
1<<60 INF代入なし	0.16852077960968018
1<<60 INF代入あり	0.17458088159561158

　float("inf")の代入なしが飛び抜けて遅いという結果になりました．そして10**18より1<<60の方がわずかに早い傾向にあると思われます．INFの代入については，float("inf")のみ代入ありが早くそれ以外は代入なしの方が早い事が分かりました．ただ，この実行も複数回行うと0.15秒ほどのばらつきを確認出来たのであまり大きな差は無いと言えます．早さではなく可読性の面から見るとINF代入をした方が良いと思われます．

結論

　float("inf")はダントツに遅い．1<<60は10**18よりわずかに早い（誤差？）．INFを代入しないほうがわずかに早い（誤差？）．私は今後，INF = 1<<60を使いたいと思います．

hirohirohirohirosのブログ

地方国立大学に通う情報系学部4年