標準入出力でTLE

セグメント木を初めて実装してみてTLEになった。

「何がおかしいのかな、 ACしてる人のコードと大差ないように見えるが…」と思って、その人のコードを手元でline_profiler掛けて比較してみたら、問題は標準入出力だった。

下記はプロファイル結果を整形したもの。数値は実行回数、総実行時間、一回あたりの実行時間(usec)、全体に占めるパーセンテージ。

code::

200000 2601965.0 13.0 15.5

いやいや、データ読み込みの1行で15%も時間を使ってるじゃん！

ACの人のコードはどうなってる？

code::

200000 374839.0 1.9 1.3

c, d = map(int, input().split())

ええっ、mapかリスト閉包かでそんなに違う？

自分のもmapに書き直してみる。

code::

200000 2244127.0 11.2 14.2

C, D = map(int, input().split())

まったく同じコードなのに僕のは11.2usecで、ACの人のは1.9usec、どういうことだ？

ここでピンと来たので出力部分を比較。

僕はループ内で毎回printしていた。ACのはリストにまとめてループが終わってからprintしていた。

真似して修正してみる。この出力部分だけに関しては速くはなってない。むしろわずかに遅くなった。

code::

before

200000 383636.0 1.9 2.4

print(segtree_node1)

after

200000 222367.0 1.1 1.4

answerst = segtree_node1

1 176312.0 176312.0 1.1

print(*answers, sep="\n")

そしてこの修正の結果、入力部分が11.2usecから5.7usecへと2倍近く高速化した。

code::

200000 1135919.0 5.7 7.0

C, D = map(int, input().split())

これで僕のTLEしてたコードはACになった。マジかよ…。

これでもACの人の1.9に比べるとまだ2倍以上遅い。他に何が影響しているのか…。謎だ…

あっ、謎はとけた

code:python

import sys

input = sys.stdin.buffer.readline

驚くべきことに、10倍以上異なります。競技プログラミングでは、実行時間制限が2 secの場合が多く、入力データ数が 106 の場合だと、0.3~0.4 sec の差はかなり大きいものとなります。

code::

200000 311399.0 1.6 10.9

C, D = map(int, input().split())

めでたしめでたし

memo

sys.stdin.buffer.readlineはバイト列として読む

行末に改行がつく