Pythonのリストにappendする物による速さ検証

発端

　Atcoder235では実装したアルゴリズムが解説コードとほぼ同じなのに，TLEになってしまう事態が起きました．解説コードは約100msだったので20倍以上速度に差があることになります．使ったアルゴリズムは同じなので計算量は変わらないはずで，実装方法の違いによる定数時間の差によると考えられます．調べた結果，リストにappendする物の型や形によって実行時間に(思ってた以上に)大きな差が生まれることが分かりました．

問題内容

　この事態が起こった問題はBFSを使う解法でした．値xをキューに入れ，キューからxを取り出しそれに対応する値yを求めます．必要ならxも変形させ，x'としキューに入れ，キューが空になるまで処理を繰り返すといった内容です．
　xとそれに対応する値yをどう管理するかが大きな差になっていました．私の書いたコードではキューに[x, y]をappendしてxとyを管理していました．解説のコードでは別にリストdを用意しておいて，キューに入れるのはxのみ，yはy = d[x]とすることでxとyを管理していました．つまりリストにappendする内容がリストか数字かによって実行時間に20倍以上の差が生まれたということになります．

速さ比べ

　以下のコードを使いました．

from collections import deque
import time
start = time.time()

que = deque([])
loop = 10

for _ in range(loop):
  for i in range(5*10**6):
    que.appendleft(i)
  for _ in range(5*10**6):
    que.popleft()

print((time.time() - start)/loop)

　キューに5*10^6個要素を左からappendし，その後左からpopしています．左からappendやpopしてるのはdeque固有の処理をさせてるだけで深い意味はありません．これを10回繰り返し平均を取ります．10行目のque.appendleft(i)のiを色々変えて速さを比べたいと思います．
　結果が下の表です．

appendする物	時間
i	1.2414920568466186
[i, i+1]	3.463377356529236
[i]	3.0810539722442627
1	1.1279115676879883
[1, 2]	2.857500100135803

　3.46/1.24 = 2.79よりiと[i, i+1]では2.8倍も差があることが分かりました．さらにiではなく定数の1にしたところ時間は短くなり，1と[1, 2]の差も2.5倍に小さくなったことが分かります．このことから，キューにappendする物はint型の方が早く，リストでも要素が少ない方が早いこと，定数だとより早くなることが分かりました．リストの方が遅くなるだろうなーというのは予想が付きますがこれほど差が付くとは実験してみないと分かりませんでした．
　なお，発端の問題に近づけるために，que.appendleft(i)に追加してd= [-1]*5*10**6のリストにd[i] = iという処理も加えて実行してみましたが時間は1.3114513158798218で，0.7秒追加されるだけで済んでいました．同じ処理を[i, j]という形で処理すると2.2秒も追加されてしまうので大きな差だと言えます．

　発端がキューだったのでキューで実験しましたが，より一般的なリストでも実験しようと思います．コードは上のコードとほぼ同じで，appendとpopは右からするようにしています．
　結果が下の表です．

appendする物	時間
i	1.5464110136032105
[i, i+1]	3.754070258140564
[i]	3.3321832180023194
1	1.1446561098098755
[1, 2]	3.1306516408920286
"1"	1.114800477027893
["1", "2"]	3.004545879364014
(1, 2)	1.2075026988983155
(i, i+1)	2.2661147594451903

　全体の傾向はキューと変わらないことがわかります．全体的にキューよりリストの方が遅いのは意外でした．ただキューを使うにはimportが必要なので流石にリストで済むときはリストを使うのが一般的でしょう．他にも値はintとstrではほぼほぼ時間は変わらない事が分かります．
　そして特筆すべきはタプルがすこぶる早いことです．やはり変更不可なのが高速化になっているのでしょう．値単独を入れたときとほとんど変わらないのは驚きでした．

まとめ

　キューでもリストでもappendする物がintとリストでは2~3倍差が付く事が分かりました．対応する値は別途リストを用意しておきそこでテーブル表のように管理するなどして，リストに入れるのは極力単独の値にすると無駄なTLEを出さずに済むと思われます．またどうしてもリストを使いたいとなったとき，それを変更することが無いならタプルを使うと単独の場合とほぼ変わらない速さが実現出来ることも分かりました．