質問

Ruby 2.4.0 でいくつかのベンチマークを実行していて、以下のことに気づきました。

(1...1000000000000000000000000000000).sum

はすぐに計算するのに対し

(1...1000000000000000000000000000000).inject(:+)

はあまりに時間がかかるので、操作を中断してしまいました。という印象を持ちました。 Range#sum のエイリアスだと思い込んでいました。 Range#inject(:+) の別名でしたが、そうではなさそうです。では、どのようにして sum はどのように動作するのでしょうか、そしてなぜ inject(:+) ?

N.B. のドキュメントは Enumerable#sum (実装されているのは Range によって実装されています) は、遅延評価やその線上にある何かについて何も言いません。

どのように解決するのですか？

短い答え

整数の範囲について:

• Enumerable#sum リターン (range.max-range.min+1)*(range.max+range.min)/2
• Enumerable#inject(:+) は全ての要素に対して繰り返し処理を行います。

理論編

から1までの整数の和は n と呼ばれます。 三角数 と等しく、また n*(n+1)/2 .

の間の整数の和は n と m の三角数である。 m の三角数を差し引いたものである。 n-1 に等しく、これは m*(m+1)/2-n*(n-1)/2 と同じで、次のように書けます。 (m-n+1)*(m+n)/2 .

Ruby 2.4のEnumerable#sumについて

このプロパティは Enumerable#sum で整数の範囲に使用されます。

if (RTEST(rb_range_values(obj, &beg, &end, &excl))) {
    if (!memo.block_given && !memo.float_value &&
            (FIXNUM_P(beg) || RB_TYPE_P(beg, T_BIGNUM)) &&
            (FIXNUM_P(end) || RB_TYPE_P(end, T_BIGNUM))) { 
        return int_range_sum(beg, end, excl, memo.v);
    } 
}

int_range_sum はこのようになります。

VALUE a;
a = rb_int_plus(rb_int_minus(end, beg), LONG2FIX(1));
a = rb_int_mul(a, rb_int_plus(end, beg));
a = rb_int_idiv(a, LONG2FIX(2));
return rb_int_plus(init, a);

と等価である。

(range.max-range.min+1)*(range.max+range.min)/2

前述したように

複雑さ

このパートを担当してくれた @k_g と @Hynek-Pichi-Vychodil に感謝します!

サム

(1...1000000000000000000000000000000).sum は、3つの足し算、掛け算、引き算、割り算を必要とします。

定数演算ですが、乗算はO((log n)²)なので Enumerable#sum は整数の範囲でO((log n)²)です。

インジェクト

(1...1000000000000000000000000000000).inject(:+)

は999999999999999998の追加を必要とします!

加算はO(log n)なので Enumerable#inject はO(n log n)です。

とは 1E30 を入力として inject は決して戻ってきません。太陽はとっくに爆発しています!

テスト

Ruby Integerが追加されているかどうかを簡単に確認できます。

module AdditionInspector
  def +(b)
    puts "Calculating #{self}+#{b}"
    super
  end
end

class Integer
  prepend AdditionInspector
end

puts (1..5).sum
#=> 15

puts (1..5).inject(:+)
# Calculating 1+2
# Calculating 3+3
# Calculating 6+4
# Calculating 10+5
#=> 15

確かに enum.c のコメントがあります。

Enumerable#sum のメソッド再定義を尊重しないかもしれません。 "+" のようなメソッドの再定義を尊重しません。 Integer#+ .