Ruby どちらが速い?

※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

Rubyで、何らかの処理を実現するのに、どう書くのがどの程度速いのか?
姑息な最適化、高速化についての話。

注意:実行時間は環境、Rubyのバージョン等によって大幅に変わる可能性があります。


一般論

一度作ったオブジェクトはなるべく捨てずに使い回す。
  • 破壊的メソッドを使う。
  • Array, Hashオブジェクトをclearして再利用することを考える。
C++と異なり、+=演算子は独立した演算子ではなく、 =, + 演算子のシンタックスシュガー。


NArrayオブジェクトに対し複数条件を同時に満たす要素を効率的に得る

複数条件を同時に満たす(つまり、条件1 and 条件2 and 条件3 and ...)要素を効率的に得るためのイディオムは以下の通り。
# NArrayオブジェクトaに対し、
# 複数の条件を同時に満たす要素を得るためのイディオム
# 例: 10以上100未満の3の要素を得る
require "narray"
 
a = NArray.to_na([15, 19, 105, 133, 81, 108, 147, 30, 98, 104, 148, 108, 2])
 
# 条件1
cond = a >= 10
idx = cond.where
 
# 条件2
cond = a[idx] < 100
idx = idx[cond]
 
# 条件3
cond = (a[idx] % 3).eq 0
idx = idx[cond]
 
p a[idx]
計算効率は条件判定の順番に大きく依存する。
真である要素数が最も少ない条件を最初に持ってくるべきである。

大部分の要素が真となる場合、普通にNArray#andメソッドを使ったほうが効率的である。
cond = (a >= 10).and(a < 100).and((a % 3).eq 0)
elem = a[cond.where]

二つの手法の効率の目安を得るため、以下のようなベンチマークを実行してみた。
require "narray"
require 'benchmark'
 
a = NArray.int(50000)
a.random! 100
 
# 条件1
Benchmark.bmbm(10) do |x|
    x.report("methodA") do
        1000.times do
            cond = a >= m
            idx = cond.where
            cond = a[idx] <= 100
            idx = idx[cond]
            elems = a[idx]
        end
    end
    x.report("methodB") do
        1000.times do
            cond = (a >= m).and(a <= 100)
            elems = a[cond]
        end
    end
end
0以上100未満の乱数50000要素から、m以上100未満の要素を抽出する。第二の条件は常に真であることに注意。mを様々に変えて実行した結果は以下のとおり。(数字はreal time)
m = 0
 methodA 1.81
 methodB 0.64
m = 50
 methodA 1.43
 methodB 1.11
m = 70
 methodA 1.06
 methodB 0.98
m = 80
 methodA 0.83
 methodB 0.87
m = 90
 methodA 0.59
 methodB 0.72
第一の条件で約8割以上が偽と判定されるのであればmethodAを使ったほうが速い。
また、条件の数がさらに増えればmethodBの効率的はさらに向上するはずである。


配列による配列のスライス

与えられた配列 arr, idx に対して、
[arr[idx[0]], arr[idx[1]], ...]
が欲しい場合。

考えられる方法としては
  • mapメソッドを使う
  • values_atメソッドを使う
  • (配列がNArrayとして与えられている場合)NArrayでのスライスを使う
が挙げられる。


require 'narray'
require 'benchmark'
 
n = 50000
 
n_arr = 100
n_idx = 1000
 
arr = (1..n_arr).map(&:to_s)
idx = (1..n_idx).map {rand n_arr}
na_arr = NArray.to_na(arr)
na_idx = NArray.to_na(idx)
 
Benchmark.bmbm do |b|
    b.report "map" do
        n.times { idx.map {|i| arr[i]} }
    end
 
    b.report "values_at" do
        n.times { arr.values_at(*idx)}
    end
 
    b.report "narray" do
        n.times { na_arr[na_idx] }
    end
end
 

結果

(Core i7 950 @ 3.07GHz)
ruby 1.8.7 (2008-08-11 patchlevel 72) [i386-cygwin]
Rehearsal --------------------------------------------
map       12.246000   0.046000  12.292000 ( 12.297000)
values_at  0.858000   0.016000   0.874000 (  0.867000)
narray     0.702000   0.016000   0.718000 (  0.717000)
---------------------------------- total: 13.884000sec

               user     system      total        real
map       11.700000   0.046000  11.746000 ( 11.752000)
values_at  0.858000   0.016000   0.874000 (  0.871000)
narray     0.702000   0.016000   0.718000 (  0.721000)

ruby 1.9.1p378 (2010-01-10 revision 26273) [i386-cygwin]
Rehearsal --------------------------------------------
map        5.398000   0.000000   5.398000 (  5.412000)
value_at   1.217000   0.000000   1.217000 (  1.205000)
narray     0.561000   0.000000   0.561000 (  0.560000)
----------------------------------- total: 7.176000sec

               user     system      total        real
map        5.414000   0.000000   5.414000 (  5.414000)
values_at  1.201000   0.000000   1.201000 (  1.205000)
narray     0.561000   0.000000   0.561000 (  0.559000)

やはりNArrayが速い。
Arrayオブジェクトに対してはvalues_atが速い。
1.9ではかなり改善されているようだが、ブロック呼び出しのためか、mapはかなり遅い。


いくらNArrayが速いからといっても、
NArray.to_na(arr)[idx]
のように、わざわざNArrayオブジェクトを作ってスライスするとvalues_atよりも遅くなるので注意。


ツールボックス

下から選んでください:

新しいページを作成する
ヘルプ / FAQ もご覧ください。