Ruby: Enumerableのパフォーマンスを測定する（1）（翻訳）
前回の記事では、Cassidy Williamsが出題したodd_sum問題の私の回答例と、XavierとAlexがSNS上で教えてくれたよりシンプルな回答例を紹介しました。
ここでふと興味が湧いたのですが、奇数偶数を計算でチェックする方法を避けると、パフォーマンスは本当に向上するのでしょうか？
そこで、それぞれの解法についてベンチマークを取ることにしました。
require 'benchmark/ips'
n = 10
a = Array.new(n) { |i| rand(1_000_000) }
b = Array.new(n) { |i| rand(1_000_000) }
Benchmark.ips do |x|
# 私の解法: 偶数奇数をフィルタしてから積を計算する
x.report('odd & even check') do
(a.select(&:odd?).product(b.select(&:even?)) +
b.select(&:odd?).product(a.select(&:even?)))
.uniq
end
# 別解: すべての積を計算してから和をフィルタする
x.report('full product, +') do
a.product(b).select { (_1 + _2).odd? }.uniq
end
x.report('full product, sum') do
a.product(b).select { _1.sum.odd? }.uniq
end
x.compare!
end
テストスクリプトでは、生成される配列のサイズを表す変数（n）を設定しています。サイズの小さな配列ではほとんど違いはなく、配列のサイズが大きくなるにつれて違いが顕著になるだろうと予想しました。直感的には、中間配列のメモリ使用量が大幅に大きくなるため、すべての積を求めるアプローチではパフォーマンスが落ちるだろうと予測していました。
以下はn = 10の場合です。
Warming up --------------------------------------
odd & even check 9.686k i/100ms
full product, + 7.030k i/100ms
full product, sum 6.911k i/100ms
Calculating -------------------------------------
odd & even check 97.138k (± 0.7%) i/s (10.29 μs/i) - 493.986k in 5.085694s
full product, + 74.138k (± 1.8%) i/s (13.49 μs/i) - 372.590k in 5.027459s
full product, sum 69.031k (± 0.9%) i/s (14.49 μs/i) - 345.550k in 5.006096s
Comparison:
odd & even check: 97137.7 i/s
full product, +: 74137.7 i/s - 1.31x slower
full product, sum: 69031.3 i/s - 1.41x slower
配列のサイズが小さい場合は、驚くほどパフォーマンスに差が出ますが、実際には個別の実行時間は極めて短く、マイクロ秒単位の差しかありません。
続いてn = 1_000の場合です。
Warming up --------------------------------------
odd & even check 1.000 i/100ms
full product, + 1.000 i/100ms
full product, sum 1.000 i/100ms
Calculating -------------------------------------
odd & even check 12.568 (± 8.0%) i/s (79.57 ms/i) - 63.000 in 5.023134s
full product, + 6.891 (± 0.0%) i/s (145.12 ms/i) - 35.000 in 5.091415s
full product, sum 6.369 (± 0.0%) i/s (157.00 ms/i) - 32.000 in 5.029184s
Comparison:
odd & even check: 12.6 i/s
full product, +: 6.9 i/s - 1.82x slower
full product, sum: 6.4 i/s - 1.97x slower
続いてn = 10_000の場合です。
Warming up --------------------------------------
odd & even check 1.000 i/100ms
full product, + 1.000 i/100ms
full product, sum 1.000 i/100ms
Calculating -------------------------------------
odd & even check 0.054 (± 0.0%) i/s (18.57 s/i) - 1.000 in 18.574282s
full product, + 0.021 (± 0.0%) i/s (46.66 s/i) - 1.000 in 46.663944s
full product, sum 0.022 (± 0.0%) i/s (45.83 s/i) - 1.000 in 45.833142s
Comparison:
odd & even check: 0.1 i/s
full product, sum: 0.0 i/s - 2.47x slower
full product, +: 0.0 i/s - 2.51x slower
ここで驚いたのは、当初は予測していなかったのですが、配列のサイズが大きくなると、どの方式であってもパフォーマンスが急速に悪化するということです。
しかし考えてみれば、どの解法においても計算量はO(n²)（またはほぼ同等）のオーダーになるので、この結果は自然です。
配列の要素が1000個の場合、評価すべき組み合わせは1000x1000で100万通りになりますし、配列の要素が10000個になれば組み合わせが10000x10000通りで1億個、つまり100倍増加します。
.productを使うと最終的に巨大な中間配列が作成され、それに伴ってメモリ使用量も増加します。
しかし実際には、元の出題のように配列のサイズが小さい場合ならパフォーマンスの違いは無視できます。であれば、重要なのは「最も読みやすい解法」を選ぶことです。
どの解法を使ったとしても、配列のサイズが数千個以上になれば、典型的なWebリクエストとして実行した場合にまともにスケールしません。
本当に巨大なデータセットを相手にする場合は、「ストリーミング」「遅延評価」「パラレル化」などを検討する必要があるでしょうが、そうなるとこのコードゴルフの範疇を超えます。
概要
元サイトの許諾を得て翻訳・公開いたします。
日本語タイトルは内容に即したものにしました。