ActiveSupport の Range#sum は超速い #Ruby

以下の記事を見ました。

そのto_a、必要?

要約すると

Array と Range は多くの共通メソッドを持つ
わざわざ to_a しなくてもよいケースでしてしまってるのは可読性上無駄
Array でなく Range を使った方がメモリ効率的にも良い
とはいえ効率を求めるならそもそも Ruby を選ぶ必要性はないので、特に可読性が大事

これは僕も完全に同意です。
特に Web アプリケーションにおいては、Ruby よりは DB やネットワークの方がネックになりやすいので、処理効率はある程度脇において考えてもよいケースは多いと思います。

ですが、ここでは「適切なデータ構造を選択することで処理効率を圧倒的に改善できる例」として ActiveSupport の Range#sum を紹介したいと思います。

1 から 10000000 までの整数を全て足し合わせた数を求める

まずは Array#sum (というか Enumerable#sum)

事前に gem i activesupport しておく必要があります。

$ ruby -r active_support/core_ext/enumerable -r benchmark -e 'nums = (1..10000000).to_a; Benchmark.bm {|bm| bm.report { puts "result = %d" % nums.sum } }'
       user     system      total        real
 result = 50000005000000
  0.640000   0.000000   0.640000 (  0.642010)

0.6 秒以上かかりました。

Range#sum

$ ruby -r active_support/core_ext/enumerable -r benchmark -e 'nums = (1..10000000); Benchmark.bm {|bm| bm.report { puts "result = %d" % nums.sum } }'
       user     system      total        real
 result = 50000005000000
  0.000000   0.000000   0.000000 (  0.000036)

一瞬で終わりました!
もちろん計算結果は一致します。

Range#sum は何故速いか

実装を見てみれば割とすぐにわかると思います。
https://github.com/rails/rails/blob/a476020567a47f5fbec3629707d5bf31b400a284/activesupport/lib/active_support/core_ext/enumerable.rb#L68

  def sum(identity = 0)
    if block_given? || !(first.is_a?(Integer) && last.is_a?(Integer))
      super
    else
      actual_last = exclude_end? ? (last - 1) : last
      if actual_last >= first
        (actual_last - first + 1) * (actual_last + first) / 2
      else
        identity
      end
    end
  end

ブロック引数が渡されていたり、最初・最後の値の少なくともいずれかが Integer でない場合などは、スーパーメソッドの Enumerable#sum が呼ばれるので、Range#sum の良さを享受できません。

大事なのはこの部分です。

        (actual_last - first + 1) * (actual_last + first) / 2

これはつまり、1 から 10 までの数を全て足すのに
1 + 2 + 3 + ... + 10 = 55
とするのではなく、
(1 + 10) * (10 / 2) = 11 * 5 = 55
とするやり方ですね。
(式の順序が元のコードと違うのは私自身のメンタルモデルを反映しているだけで宗教的な意味はありません)

元々 Scala 2.10 のリリースノートにあった Range#sum is now O(1) というのを見て、これはどういうことだと読んでみたら、小中学生でもわかりそうなアルゴリズムでおもしろかった、ということで Ruby にも実装してやろう、と思ったら ActiveSupport が既に実装していた、という感じです。

まとめ

Range#sum が最適化されていることで高速化した Web アプリケーションを作ったことは無い。