Rubyのプログラムを書くときに
心に留めておくだけで速いコードが書けるかもしれない(?)三つのポイント
注意点
- Ruby1.9での検証。新しいバージョンでは要らなくなってるかも
- 筆者は競プロ勢でもなんでもないただの一般ピーポー
- もっといい書き方があるかも
目次
基本的な考え方
- ブロックを使わない -> { } , do end
- アクセスを減らす -> array[i], instance.some_method
- コピーを減らす
この三つを抑えれば、それなりに速いプログラムが書ける!(多分)
ブロックを使わない
Rubyで単に無限ループを書きたい場合
while true # 処理 end loop do # 処理 end
こんな感じに、まず二通りの書き方ができてしまいます。
「この二つの違いは何なのか?」というと
→whileは制御式、loopはブロック(メソッド)
で動作している、ということでしょうか。
制御式とブロックの挙動の違い
まず、ローカル変数のスコープが変わります。
ループの中でいきなり変数を宣言するような場合、
whileは制御式なので、スコープは一定ですが、
loopはブロックなので、ブロックの中の変数として分けられます。
while true a = 0 break end p a # => 0 loop do b = 0 break end p b # => NameError ブロックの外側ではそんなもんないよとキレられる
そして、制御式とブロックだと、制御式の方が速いです。
require 'benchmark' Benchmark.bm(7) do |r| r.report("while") { i = 0 while true i += 1 break if i > 10_000_000 end } r.report("loop") { i = 0 loop do i += 1 break if i > 10_000_000 end } end # user system total real # while 0.156000 0.000000 0.156000 ( 0.167549) # loop 0.391000 0.000000 0.391000 ( 0.395238)
この二つはほぼ同じ処理をしているのにも関わらず、
二倍以上の時間差が出来てしまう結果となっています。
これは「each」などの配列参照であっても同じです。
require 'benchmark' array = Array.new(1_000_000) Benchmark.bm(7) do |r| r.report("while") { i = 0 s = array.size while i < s array[i] i += 1 end } r.report("each") { array.each { |v| v } } end # user system total real # while 0.031000 0.000000 0.031000 ( 0.027458) # each 0.032000 0.000000 0.032000 ( 0.028579)
僅かながらですがwhileの方が速いです。
総じるとRubyは、「ブロック」というだけで
ちょっとずつ損をしてしまうという悲しい側面があります。*1
見た目やバグを減らすことよりも、
「とにかく速いコードが必要!」という場合は、
whileへの置き換えで速度が上がるか試してみると良いでしょう。
アクセスを減らす
array = Array.new(10_000) { [] } x = 0 y = 0 while x < array.size while y < array.size array[x][y] y += 1 end y = 0 x += 1 end
これは二次元配列の全要素にアクセスする場合の一例です。
このコードには最適化すべき部分が二か所あります。
x < array.size y < array.size
この条件式二つと
array[x][y]
配列へのアクセス部分ですね。
インスタンス内へのアクセスは遅い
- 配列内の要素にアクセスする
- 配列の大きさを調べる
こういったインスタンス内の要素へのアクセスは遅くなりがちです。
そこで、以下のように書き換えました。
x = 0 y = 0 s = array.size # 配列サイズを変数に取る while x < s data = array[x] # 中間にある配列を変数に取る while y < s data[y] y += 1 end y = 0 x += 1 end
配列サイズを変数に格納し、また配列への添え字を付けたアクセスも、
まとめて行わず、一旦変数に格納してから行うことにしました。
すると実行時間はこのように変わります。
require 'benchmark' array = Array.new(10_000) { [] } Benchmark.bm(10) do |r| r.report("before") { x = 0 y = 0 while x < array.size while y < array.size array[x][y] y += 1 end y = 0 x += 1 end } r.report("after") { x = 0 y = 0 s = array.size while x < s data = array[x] while y < s data[y] y += 1 end y = 0 x += 1 end } end # user system total real # before 4.188000 0.000000 4.188000 ( 4.188692) # after 2.937000 0.000000 2.937000 ( 2.932846)
トータルで1秒以上、1.4倍以上の速度アップです。
このように配列、インスタンスの要素へのアクセスを減らすこと。
複数にわたる階層構造で連続してアクセスする場合は、
途中の階層を一旦変数に格納することで、速度の向上が図れます。
あ、でもアクセスを減らすと言っても、私のブログへのアクセスは減らさなくていいですからね?
コピーを減らす
以下は、現在の位置 x と、目標の位置 tx との
距離を計算する感じのテストコードです
x = 10 tx = 20 dx = tx - x
これをメソッド化してみます。
def distance_x(x, tx) tx - x end
速度を比較してみましょう↓
require 'benchmark' Benchmark.bm(6) do |r| r.report("direct") { i = 0 dx = tx - x while (i += 1) < 1_000_000 } r.report("method") { i = 0 dx = distance_x(x, tx) while (i += 1) < 1_000_000 } end # user system total real # direct 0.031000 0.000000 0.031000 ( 0.024096) # method 0.032000 0.000000 0.032000 ( 0.044268)
当然ながらこのような単純な計算式を、
わざわざメソッド化してから呼び出してるがために
圧倒的に遅くなります。(1.8倍くらいかかってる)
しかし、複雑な計算式の使いまわしや、
クラス継承などを意識したプログラム設計をしていると、
メソッドの呼び出しやその引数に伴って、値のコピーが増え、
メモリの消費量も増え、実行時間も増え、白髪も増えます(ォィ)。
こういったメソッド間での引数の渡し方や
そもそも引数を渡さなくてもいい設計をすることで、速度向上が見込めます。
まとめ
ブロックを使わないということは、複雑な計算処理を要さず、
whileで回せるような単純な計算でプログラムが動くということになり
それ自体が高速化になります。
アクセス回数を減らす工夫は、コーディングにかけるひと手間以外にも、
特定のアルゴリズムやデータ構造を用いて、劇的に改善する場合もあります。
データコピーの回数を減らせるかどうかは、クラスの設計によるところが大きいです。
あんまりやり過ぎると可読性が悪化して、読むのも書くのもつらいプログラムになるので
ほどほどにしておきましょう(経験者は語る)
*1:Array.delete_ifなら使ってもいいと思う