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よりも遅くなるので注意。
最終更新:2011年10月19日 09:14