読者です 読者をやめる 読者になる 読者になる

なにも わからぬ

パソコンとプログラミング関係をメモっていきたい

pythonのリスト操作にかかる時間

Python3

昨日のAtCoderにpython3で参加したものの、B問題でTLE連打し1完という大失態を演じ、さらには終了直後に余裕でACしてしまい悲しみに暮れたのでリスト操作にかかる時間をまとめてみた。

昨日の問題では結論から言うとループ内でlist.count(n)をしていた(リスト内に同じ数字が複数あった場合、まとめて処理すればループ回数が減らせるかなと……)のが敗因で、よくよく考えてみればlist.count(n)は処理の内容上リストを全走査しているのは明白であり、普通の競プロerならば犬のウンコを自然に避けるように判断できるのだろうけど、まだ自分の場合は「わー!なにこれー!?おもしろーい!(ふみふみ」としておきながら「うわくっせ!なんなんだよ汚えー!えーん(泣)」となってしまうレベルなので、実際に確かめてみるの大事。

環境

前提

  • リストの中身は0..n-1([i for i in range(0, n)])
  • for i in range(len(a)): の中に処理内容を入れ、ループ前後でtime.time()を取って計測
  • 少し待って結果が出ないのはクソ遅いとする
  • 最小値付近を適当に記録(省電力機能で結果が暴れるため)

結果

単位は全て秒

ループ内のコード 10^4 10^5 10^7 備考
a[i] 0.0006 0.005 0.49 n=a[i]としてもほぼ同じ
a.append(i) 0.0008 0.009 0.96
a.insert(0, i) 0.09 10.5 先頭に挿入(禁じ手)
a.remove(i) 0.02 2.1
a.pop() 0.001 0.012 1.2
a.pop(0) 0.2 2.1 先頭を削除(禁じ手)
a.index(i) 0.8 クソ遅い
a.count(i) 1.5 クソ遅い
a.sort() 1.5 クソ遅い
sorted(a) 1.9 クソ遅い
len(a) 0.001 0.008 0.8
all(a) 0.001 0.011 1.07
any(a) 0.001 0.012 1.17
sum(a) 0.8 86 コーヒーいれてたら結果出てた
max(a) 2.1 クソ遅い
min(a) 1.8 クソ遅い

リストの先頭への挿入・削除は遅いので、そのような操作を繰り返す必要があるならば先頭でも末尾でも端へのアクセスが早いcollections.dequeの使用を考える。 x1.inkenkun.com

リストでも速い末尾の削除もdequeならさらに少し速いよう。ただし、真ん中あたりへのアクセスにはめっぽう弱いのでなんでもかんでもdeque使えばいいってもんでもない。

10^5 10^6 10^7
a.pop() 0.01 0.12 1.2
q.pop() 0.008 0.08 0.83
a[int(len(a)/2)] 0.03 0.30 3.1
q[int(len(q)/2)] 0.58 110 うんこ

len()にかかる時間はどっちも同じ。


一般的に競プロでは計算量10^8がTLEのボーダーだが定数倍が軽ければ通る、ということになっているようだけど、10^8のループでa[i]をしただけで11秒、1+1passであっても2.5〜3秒もかかってしまう。pythonでは10^8のループを回した時点で死ぬし、10^7でも最適化に努めなければならないということを肝に銘じておく。大きなrangeを扱うのが重いのかな?