標準入出力でTLE
セグメント木を初めて実装してみてTLEになった。
下記はプロファイル結果を整形したもの。数値は実行回数、総実行時間、一回あたりの実行時間(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倍以上遅い。他に何が影響しているのか…。謎だ…
あっ、謎はとけた
pythonimport sys
input = sys.stdin.buffer.readline>驚くべきことに、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はバイト列として読む
行末に改行がつく
"Engineer's way of creating knowledge" the English version of my book is now available on [Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from [Scrapbox] at [Edit]