LoginSignup
0

More than 5 years have passed since last update.

入力の受け取り方次第でTLEが怖いことになるようだった

Last updated at Posted at 2013-12-17

はい。
codeforces
http://codeforces.com/contest/373/problem/C

ネタ元ツイート
https://twitter.com/cocodrips/statuses/412848727175331840
公開してらしたGist
https://gist.github.com/cocodrips/8001370

元々のコードの全文は上記公開先を参照くださいませ。

元々
if __name__ == "__main__":
    num = map(int, raw_input().split())
    num=num[0]
    data = []
    for _ in range(num):
        next=map(int, raw_input().split())
        data.append(next[0])
    solve(data)
私の提案
if __name__ == "__main__":
    num = int(raw_input())
    data = []
    for x in range(num):
        data.append(int(raw_input()))
    solve(data)

テストデータはサンプルケースをてきとーにコピーして1行+20万行のデータを用意。1行目が与えられる予定の行数で、以降の20万行がテキトーにコピーしたデータです。

いちおウチのCPUとメモリ
Processor 2.5 GHz Intel Core i5
Memory 16 GB 1333 MHz DDR3

時間計測は

time
import=time
start=time.clock()
##他実行部分
end=time.clock()
t=end-start
コメントで頂いた方法
if __name__ == "__main__":
    num = int(raw_input())
    data = (int(raw_input()) for _ in xrange(num))
    solve(data)

3回実行して真ん中の値を以下の表に記載

その1:元々のデータ
その2: num = int(raw_input()) の一行目の受け取り方だけ変更
その3:forで回しながらのdata.append(int(raw_input()))受け取り方だけ変更
その4:両方とも変更
その5:コメントで頂いた方法

パターン 処理時間
その1 0.990795秒
その2 0.995793秒
その3 0.661866秒
その4 0.677707秒
その5 0.647318秒

時間差が今回有意であったぽいのは2行目以降の受け取り方で、、、、

1行目のウチでのテストケースは200000、出題の前提条件上で最大値のTLEになってた500000とでは1行6桁の数字を受け取るだけで時間差は感じられませんでした。

その3、4とその5では一見それほど違わないようで0.65秒を切れるかどうかで早さに違いありといって良さそうでした。

オマケで試したものとして
data.append(input())
でintでキャストするのを外したところ数倍の時間がかかるように成ったのではずさない方が良さそうです。

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0