競技プログラミングを解くときにsplitやchompを削ると実行時間が速くなる

今日、やっとAtCoder Beginners Selectionの問題を全部解き終えた。感想はACになったときにアドレナリンが出るということと、人の解法が勉強になるということだった。

だいたいこんな感じ、各問題の初回のACは実力で、2回目以降は他の人の解法を眺めながらやった。そこでコード量はたいして変わらないのに、実行時間が違うんだーということがあった。見つけたのはこの問題を解いているときであった。

最初の僕のコードはこちら。

Submission #7131569 - AtCoder Beginners Selection

def init
  $n = $stdin.gets.chomp.split(" ").map(&:to_i)
  $line = %w()
  while line = gets
    $line.push(line.chomp.split(' ').map(&:to_i))
  end
end

init

def plan
  $line.each do |l|
    return if l[0] < l[1] + l[2] 
    return unless ((l[0] - (l[1] + l[2])) % 2).zero?
  end
  true
end

puts plan ? 'Yes' : 'No'

結構速い実行時間のでは？とか思っていたけど 210 ms で、あれ？意外と遅くない？とか思った。ただRubyに限定した話をすれば最速は 154 ms であった。(他人のコードなので、このブログには転載しない、またRuby言語以外だと20ms台の実行時間もあるので、Ruby自体がこの問題では僕が想像していた速いタイムにはならない。)

Submission #6047015 - AtCoder Beginners Selection

なるほどーgetsをしながらループをすれば読み込みと実際の処理を一緒にできて速くなるなーと思い真似してみた。すると 172 ms になり、速くはなったが150ms台にならない。なぜだろうと思った。

n = gets.chomp.to_i
n.times do
  t, x, y = gets.chomp.split(' ').map(&:to_i)
  distance = x + y
  if t < distance || (distance - t).odd?
    puts 'No'
    exit
  end
end

puts 'Yes'

見比べてみると、Ruby最速コードにはsplitは引数を与えないと空白文字で分割してくれる。早速試してみるとわずかだが速くなり170 ms になった。

split (String) - Rubyリファレンス

Submission #7132131 - AtCoder Beginners Selection

さらに見ていくとchompメソッドもない。あれ？改行マーク取り除かなくても大丈夫？と思ったがto_iでNumericに変換しているので改行マークは外れるようだ。chmodメソッドを削除してみると152 ms になり満足する結果になった。

Submission #7132148 - AtCoder Beginners Selection

n = gets.to_i
n.times do
  t, x, y = gets.split.map(&:to_i)
  distance = x + y
  if t < distance || (distance - t).odd?
    puts 'No'
    exit
  end
end

puts 'Yes'

なるほどーchmopもsplitも何回も繰り返すと実行時間が延びるので、入力を読む時点で実行時間を気にして書けばいいのかーと勉強になった。結構前のコードのコピペになりやすいのでこういう発見ができてよかった。