概要
配列の特定要素のみを抽出し、それに対し一律で同じ処理を適用した配列を取得したい場面というのは、割りとあるかと思います。
そんなとき、array.select { |x| hoge }.map { |x| hogehoge }と書いたり。array.map { |x| hogehoge if hoge }.compactと書くことが多いと思います。
しかし、どちらも 2度ループが回ってしまいます。2回ループが回っても所詮 O(n) ではあるため気にする必要はないかもしれませんが、可読性が大して変わらないなら少しでも早い処理を選びたくなるのが人情……！
というわけで、4種類の実装でベンチマークを取ってみました。
実装
偶数のみを2乗して返す処理を4種類実装してみました。
ary.select { |a| a.even? }.map { |e| e ** 2 }
ary.map { |a| a ** 2 if a.even? }.compact
ary.compact_map { |a| a ** 2 if a.even? } # Array 拡張
ary.reduce([]) { |a, e| e.even? ? a << e ** 2 : a }
compact_mapというのは Array 拡張です。後ほど説明します。
select+map
一番純粋な実装な気がします。まず必要な要素だけを select でフィルタリングして、次に map を行います。
Ruby の実装には明るくないので間違ってるかもしれませんが、select で新しい配列を作って、その配列に対して map して最終的な配列を生成して返すという処理に見えるので、少し重そうです。
とてもシンプル。
map+compact
map に渡すブロック中に条件を書いておき、最後に compact で不要な nil を全て除去します。そこそこ直感的な実装な気がします。
map で新しい配列が作られ、そのリストを線形探索して nil を捨てていっているような気がします。多分。あくまで多分。
なんとなく select+map よりコストが低そうです。
compact_map (Array拡張)
Array の拡張です。ループ1回で map+compact と同じ処理が行えます。
class Array
def compact_map
self.class.new.tap do |a|
each do |e|
value = yield e
next unless value
a << value
end
end
end
end
新しいリストを作成し、ブロックの評価が nil でなければ、その新しい配列に次々に要素を入れていくという処理を行っています。
なんとなく一番無駄がないように見えます。もしかしたら配列への要素追加処理のコストが重いかもしれないです。良い感じにしてくれてると信じましょう。
普通、配列への要素追加削除処理は O(n) の計算量となります。リストへは O(1) ですね。でも、多分配列の末尾への要素追加ならもっと高速な気がします。Ruby の配列は使い勝手的にも、実態はベクターに近い何かではないかと思ったり思わなかったりします。
その場合、計算量的には O(1) ですが、どちらにしろデータ挿入処理は少しだけ重そうに見えます。
ループ回数と可読性、どちらも良いですが、Array 拡張はできるだけしたくないです。
reduce([])
Array 拡張なしでループ1回で同じ処理を実現しています。
先ほど紹介した compact_map に近い処理です。
配列への要素追加処理のコストが気になるところです。
ループ回数は良いですが、可読性に少し難があります。
ベンチマーク
以上の4実装で、実際にベンチマークを取ります。
1から10の7乗までを順番に並べたリストに対し、それぞれの処理を5回適用し、その平均時間を出力してみます。
require 'benchmark'
class Array
def compact_map
self.class.new.tap do |a|
each do |e|
value = yield e
next unless value
a << value
end
end
end
end
A_NAME = 'select+map'
B_NAME = 'map+compact'
C_NAME = 'compact_map'
D_NAME = 'reduce([])'
Benchmark.bm(16, "avg(#{A_NAME})", "avg(#{B_NAME})", "avg(#{C_NAME})", "avg(#{D_NAME})") do |x|
BENCH_COUNT = 5
ary = (1..10 ** 7).to_a
# 4 pattern implementations
f_a = -> (a) { a.select { |a| a.even? }.map { |e| e ** 2 } }
f_b = -> (a) { a.map { |a| a ** 2 if a.even? }.compact }
f_c = -> (a) { a.compact_map { |a| a ** 2 if a.even? } }
f_d = -> (a) { a.reduce([]) { |a, e| e.even? ? a << e ** 2 : a } }
# Check all results are equal
fail unless [f_a, f_b, f_c, f_d].map { |f| f.call((0..99).to_a) }.uniq.size == 1
# For benchmark
exec_bench = -> (target_ary, title, &func) do
BENCH_COUNT.times.reduce([]) do |results, i|
results << x.report("#{title}(#{i + 1})") do
func.call(target_ary)
end
end
end
# Execute benchmark
results_a = exec_bench.call(ary, A_NAME, &f_a)
results_b = exec_bench.call(ary, B_NAME, &f_b)
results_c = exec_bench.call(ary, C_NAME, &f_c)
results_d = exec_bench.call(ary, D_NAME, &f_d)
puts '--------------------------------------------------'
[results_a, results_b, results_c, results_d]. map do |p|
p.reduce(:+) / BENCH_COUNT
end
end
念のため、全ての処理が同じ結果を返しているかを確認する処理も行っています。
ベンチマーク結果
実行してみます！どーん！
$ ruby bench_select_map.rb
user system total real
select+map(1) 1.640000 0.030000 1.670000 ( 1.704434)
select+map(2) 1.650000 0.040000 1.690000 ( 1.706711)
select+map(3) 1.530000 0.010000 1.540000 ( 1.549202)
select+map(4) 1.540000 0.020000 1.560000 ( 1.549829)
select+map(5) 1.540000 0.020000 1.560000 ( 1.563497)
map+compact(1) 1.370000 0.050000 1.420000 ( 1.441505)
map+compact(2) 1.370000 0.070000 1.440000 ( 1.454244)
map+compact(3) 1.330000 0.030000 1.360000 ( 1.355571)
map+compact(4) 1.320000 0.030000 1.350000 ( 1.353625)
map+compact(5) 1.360000 0.030000 1.390000 ( 1.391250)
compact_map(1) 1.800000 0.020000 1.820000 ( 1.850432)
compact_map(2) 1.810000 0.020000 1.830000 ( 1.838847)
compact_map(3) 1.820000 0.020000 1.840000 ( 1.851395)
compact_map(4) 1.800000 0.020000 1.820000 ( 1.834059)
compact_map(5) 1.780000 0.010000 1.790000 ( 1.801491)
reduce([])(1) 1.570000 0.010000 1.580000 ( 1.597857)
reduce([])(2) 1.590000 0.020000 1.610000 ( 1.617606)
reduce([])(3) 1.610000 0.020000 1.630000 ( 1.636748)
reduce([])(4) 1.600000 0.020000 1.620000 ( 1.630427)
reduce([])(5) 1.620000 0.020000 1.640000 ( 1.655257)
--------------------------------------------------
avg(select+map) 1.580000 0.024000 1.604000 ( 1.614735)
avg(map+compact) 1.350000 0.042000 1.392000 ( 1.399239)
avg(compact_map) 1.802000 0.018000 1.820000 ( 1.835245)
avg(reduce([])) 1.598000 0.018000 1.616000 ( 1.627579)
なんと！map+compact が最速でした！
考察
それぞれについて、きちんと考察してみます。
map+compact
ループは2回走るが、新しい配列を作成する処理が1度しか走らないため、コストが少ないのではないでしょうか。
O(n) の処理が2回と、重そうな配列生成が1回走っています。
具体的に配列の長さを n とすると、n + n = 2n 回計算が走っている事になります。ただ、compact の処理が結構軽そうに見えるので、そのへんが有利に働いたのかもしれません。
select+map
こちらは配列を作成する処理が2度走ってしまっています。
O(n) の処理と配列生成がどちらも2回行われています。
map+compact と同じように、n + n/2 = 3/2 * n 回の計算が行われていると思います。
reduce([])
ループ回数も配列を作成する処理も1回のみですが、やはり配列への追加操作が重そうです。
先程述べたように、素の配列への追加処理は通常 O(n) ですので、n + 1 + 2 + ... + ((n - 1) / 2) = n + 1/2 ((n - 1) / 2)(1 + (n - 1) / 2) = n ^ 2 / 8 + n - 1 / 8 回の計算が……ってこれ本当に計算あってる！？
ベンチ結果を見た感じ、 O(n^2) のはずはないので、使い勝手から分かる通り Ruby の配列は単なる配列ではないと思います。そりゃそうだ。
というわけで、多分追加処理の計算量は O(1)で、少し計算自体のコストが掛かるようなタイプだと思うので、計算回数的には n + 1 * n/2 = 3/2 * n 回あたりが妥当だと重います。
compact_map
reduce([]) とほぼ条件は同じなんですが、圧倒的にこいつが遅かったです。実際にこのプログラムを書いたベトナム人エンジニア曰く、「こいつだけ Ruby のコードで処理を拡張してる。他は全部 Ruby に元からあるメソッドでの処理で、たぶん直接 C のコードが実行されている。そこら辺の差が実行速度に現れたんだと思う」とのことです。たぶん。
英語力低すぎて聞き取れてたか不安です。
でも確かに、そうであれば reduce([]) とやってることがほとんど変わらないのに明らかに遅い理由がわかります。
そして計算回数はこいつも 3/2 * n 回ですね。
まとめ
1位の map+compact がざっくりですが出した計算回数的には、もしかしたら1番多いという結果に……！
ただ、基本的に計算回数は似たり寄ったりですね。あってるのかなこれ。
しかし、配列へのデータ追加など、少し重そうな処理を使っているとやはり少しだけ遅くなっています。
また、同条件のときは Ruby 拡張は遅くなってしまうと判明しました。
一番早いのは map+compact となりましたが、全て所詮 O(n) であるので、最もシンプルで、可読性が高い処理を採用するのがよいかもしれません。
結論としては、同じオーダーの処理であれば、シンプルさと可読性で選べば良い、ということだと思います。
余談
ハノイでベトナム人エンジニアと働いてる際に、「"select+map"を何度か使ってて、そこのループ回数を減らして高速化したいから Array 拡張してみていい？」って言われたのがきっかけでした。
今回の場合は拡張すると遅くなってしまいましたが、ちゃんと計算量について考えながらコーディングしていて良いなーって思いました。
超おまけ
リストに対する高階関数とかみると関数型言語を書きたくなりますね。
xs = [1..10 ^ 7]
map (^ 2) . filter even $ xs
関数を渡せて綺麗！
超おまけ
Haskell の内包表記で書くと超綺麗にかけます。
xs = [1..10 ^ 7]
[x ^ 2 | x <- xs, even x]
最高にわかりやすい！！