そこで私はRuby 2.4.0でベンチマークを実行していたのですが、
(1...1000000000000000000000000000000).sum
すぐに計算しますが
(1...1000000000000000000000000000000).inject(:+)
Range#sum時間がかかりすぎるため、操作を中止しました。は の別名だと思っていましたRange#inject(:+)が、そうではないようです。 はどのようにsum機能し、 よりもずっと速いのはなぜでしょうかinject(:+)。
注意Enumerable#sum(によって実装されています)のドキュメントには、Range遅延評価やそれに類するものについては何も記載されていません。
ベストアンサー1
短い答え
整数範囲の場合:
Enumerable#sum戻り値(range.max-range.min+1)*(range.max+range.min)/2Enumerable#inject(:+)すべての要素を反復処理します。
理論
1から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).sum3 つの加算、乗算、減算、除算が必要です。
演算回数は定数ですが、乗算は O((log n)²) なので、Enumerable#sum整数範囲の場合は O((log n)²) になります。
注入する
(1...1000000000000000000000000000000).inject(:+)
999999999999999999999999999998 個の追加が必要です!
加算は O(log n) なので、Enumerable#injectO(n log n) も同様です。
を入力すると1E30、inject決して戻りません。ずっと前に太陽が爆発するでしょう!
テスト
Ruby 整数が追加されているかどうかを確認するのは簡単です:
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#+。