セグメント木を初めて実装してみてTLEになった。 「何がおかしいのかな、 ACしてる人のコードと大差ないように見えるが…」と思って、その人のコードを手元でline_profiler掛けて比較してみたら、問題は標準入出力だった。
下記はプロファイル結果を整形したもの。数値は実行回数、総実行時間、一回あたりの実行時間(usec)、全体に占めるパーセンテージ。 :
200000 2601965.0 13.0 15.5
C, D = [int(x) for x in input().split()]
いやいや、データ読み込みの1行で15%も時間を使ってるじゃん！
ACの人のコードはどうなってる？ :
200000 374839.0 1.9 1.3
c, d = map(int, input().split())
ええっ、mapかリスト閉包かでそんなに違う？
自分のもmapに書き直してみる。 :
200000 2244127.0 11.2 14.2
C, D = map(int, input().split())
まったく同じコードなのに僕のは11.2usecで、ACの人のは1.9usec、どういうことだ？
ここでピンと来たので出力部分を比較。 僕はループ内で毎回printしていた。ACのはリストにまとめてループが終わってからprintしていた。 真似して修正してみる。この出力部分だけに関しては速くはなってない。むしろわずかに遅くなった。 :
before
200000 383636.0 1.9 2.4
print(segtree_node[1])
after
200000 222367.0 1.1 1.4
answers[t] = segtree_node[1]
1 176312.0 176312.0 1.1
print(*answers, sep="\n")
そしてこの修正の結果、入力部分が11.2usecから5.7usecへと2倍近く高速化した。 :
200000 1135919.0 5.7 7.0
C, D = map(int, input().split())
これで僕のTLEしてたコードはACになった。マジかよ…。
これでもACの人の1.9に比べるとまだ2倍以上遅い。他に何が影響しているのか…。謎だ…
あっ、謎はとけた python
import sys
input = sys.stdin.buffer.readline
Pythonの知っておくと良い細かい処理速度の違い8個 - kumilog.net
驚くべきことに、10倍以上異なります。競技プログラミングでは、実行時間制限が2 secの場合が多く、入力データ数が 106 の場合だと、0.3~0.4 sec の差はかなり大きいものとなります。
:
200000 311399.0 1.6 10.9
C, D = map(int, input().split())
めでたしめでたし
memo
- sys.stdin.buffer.readlineはバイト列として読む
- 行末に改行がつく