Ruby で 10^7 ループくらいの処理をする時に気をつける事 #Ruby

※ ただしオンラインジャッジに限る

Ruby と競技プログラミング

Ruby は必ずしも競技プログラミングに向いた言語とは言えないかもしれませんが、 combination メソッドや transpose メソッドなど便利に使えるメソッドも多く、楽しく問題を解く事ができます。

ただし、比較的大きな数のループを回す時は注意が必要です。

$N = 10^7$ の時の $O(N)$ な処理を行う、みたいな場合ですね。

大きい方を取る、小さい方を取る

$10^7$ のサイズの数値の配列の、最大値を取る素朴なコードを書いてみましょう。

loop.rb

arr = [*1..(10**7)]
max = -(1.0/0)
arr.each do |e|
  max = [max, e].max
end

単純ですね。
では動かしてみましょう。

$ ruby -v
ruby 2.3.3p222 (2016-11-21 revision 56859) [x86_64-darwin15]
$ time ruby loop.rb
ruby loop.rb  3.84s user 0.15s system 97% cpu 4.094 total

うーん、遅い……。

最適化

単純な処理なのにこの遅さはいけません。
しかしこのコードは、少し工夫するだけで劇的にパフォーマンスが改善します。

loop2.rb

arr = [*1..(10**7)]
max = -(1.0/0)
arr.each do |e|
  max = max > e ? max : e
end

$ time ruby loop2.rb
ruby loop2.rb  0.98s user 0.13s system 95% cpu 1.167 total

[max, e].max という配列の生成とメソッドの呼び出しを、 max > e ? max : e という三項演算子に置き換えるだけで、なんと速度が4倍になりました。

この理由は、おそらく以下の2点ですね。

オブジェクト生成のコストがかかっていた
max メソッドが重かった

オブジェクト生成のコスト

Ruby のオブジェクト生成は、凄く重い処理というわけではないですが、 $10^7$ 回のループの中で軽々しく行っていい処理というわけでもありません。

loop3.rb

arr = [*1..(10**7)]
arr.each do |e|
  Array.new
end

$ time ruby loop3.rb
ruby loop.rb  1.64s user 0.11s system 97% cpu 1.803 total

なので、ループの中でオブジェクトが生成されないようにする事で、速度の改善ができたのですね。

`max` メソッドの重さ

ここでいう max メソッドとは、正確には Enumerable#max メソッドの事です。
Ruby 2.3 系だと、 Array クラスに対する max メソッドはこの Enumerable モジュールの max メソッドを呼び出します。

さて、このメソッドの実体は C で書かれた enum_max 関数なのですが、この関数を見てみると、決して冗長なわけではありませんが、新しいオブジェクトを生成したりソートしたりといった、「 a と b のどちらが大きいか」という事だけを知りたい場合には、重すぎる処理である事がわかります。

loop4.rb

arr = [*1..(10**7)]
ab = [1, 2]
arr.each do |e|
  ab.max
end

$ time ruby loop4.rb
ruby loop.rb  2.66s user 0.12s system 95% cpu 2.897 total

まとめ

そういうわけで、この、

オブジェクトを作る
そのオブジェクトの max メソッドを呼び出す

という重い処理を、単なる三項演算子の呼び出しに置き換える事で、大幅な速度改善になりました。

でも、 [a, b].max や [a, b].min なんてよく使うイディオムですよね？

Ruby 2.4 での改善

この問題、 Ruby 2.4 では改善されています 。

2.4 から Array インスタンス作らないっぽいですねhttps://t.co/p2mKON1rhe https://t.co/FmEWr9k5Nz
— Fumiaki MATSUSHIMA (@mtsmfm) 2018年5月8日

はい、私が今挙げた

オブジェクト生成が重い
max メソッドが遅い

という両方の問題が、 Ruby 2.4 より新しいバージョンでは見事に改善されています。

$ ruby -v
ruby 2.5.1p57 (2018-03-29 revision 63029) [x86_64-darwin16]
$ time ruby loop.rb
ruby loop.rb  0.94s user 0.10s system 86% cpu 1.202 total

高速化されています！

Ruby は素晴らしいですね。

では `[a, b].max` が重い問題は過去の話なのか？

残念ながらそうとは言えないのです。

最初に Ruby と競技プログラミングとの関係について触れましたが、短い時間の中で $10^7$ 回のループを処理しないといけない、といった事態は、競技プログラミングに於いて頻出する事です。

問題を解くだけでも競技プログラミングは楽しめますが、競技プログラミングをやっている方の中にはオンラインジャッジのコンテストに参加していらっしゃる人も多いでしょう。
オンラインジャッジとは、手元でコードを実行するのではなく、コンテスト主催者の用意した環境でコードを実行し、競う形式です。

ではここで、 Ruby が利用できる幾つかのオンラインジャッジで、そのバージョンを見てみましょう。
（2018年5月17日に調査しました。）

AtCoder

Ruby (2.3.3)

Codeforces

Ruby 2.0.0p645

サイト中には書いてないのですが、提出するフォームにありました。

Paiza

ruby 2.3.3

AIZU ONLINE JUDGE

Ruby 2.2.2

Google Code Jam

去年までは手元で実行して結果を送信する形式だった GCJ も、今年はオンラインジャッジになりました。

2.3.3p222 (package: ruby-full)

yukicoder

※ 2018年5月18日追記 @raccy さん、ありがとうございます！

ruby 2.5.0p0

まとめ

おわかりいただけたでしょうか……？

上に挙げた幾つかのオンラインジャッジだと、 Ruby 2.4 以降が使える環境は、なんと ~~1つもありません~~ 1つしかありません。

これらのバージョン 2.4 未満の Ruby しか使えないサイトでコンテストに参加する場合、 Ruby 2.4 で入った [a, b].max みたいな書き方の最適化の恩恵を享ける事は当然できません。

なので、大きめのループの中で軽々しくオブジェクトの生成や重いメソッドの呼び出しが起きないように、注意してコーディングをしてあげる必要があるのですね。

何でオンラインジャッジで Ruby 2.4 以降が使えないの？

色々な理由があると思いますが、長く続いているオンラインジャッジであればあるほど、言語の新しいバージョンが出る度にアップデートをしなければならないという事になります。

皆さんもエンジニアなら、ああいうシステムの利用言語をアップデートするのがどれだけ大変か、何となく解りますよね。

言語アップデートしろって要求がしょっちゅうメールで来るようになってきたけど、待って・・・そんな簡単なものじゃないから色々まって・・・。
— chokudai(高橋直大) (@chokudai) 2018年4月3日

利用できる環境の中で最善を尽くしつつ、気長に待ちましょう。

Ruby で 10^7 ループくらいの処理をする時に気をつける事