Ruby 为什么 sum 比 inject(：+) 快这么多

发布于01月04日

所以我在Ruby 2.4.0中运行了一些基准测试，并意识到

(1...1000000000000000000000000000000).sum

立即计算而

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

花了这么长时间，我才中止了手术.我的印象是Range#sum是Range#inject(:+)的别名，但似乎不是这样.那么sum是如何工作的，为什么它比inject(:+)快得多？

N.B. Enumerable#sum的文档(由Range实现)没有提到任何关于延迟判断或类似的内容.

Short answer

对于整数范围:

Enumerable#总和返回(range.max-range.min+1)*(range.max+range.min)/2
Enumerable#注射(:+)对每个元素进行迭代.

Theory

1和n之间的整数之和称为triangular number，等于n*(n+1)/2.

n到m之间的整数之和是m的三角形数减go n-1的三角形数，等于m*(m+1)/2-n*(n-1)/2，可以写成(m-n+1)*(m+n)/2.

Enumerable#总和 in Ruby 2.4

此属性在Enumerable#总和中用于整数范围:

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_总和(beg, end, excl, memo.v);
    } 
}

int_range_总和看起来像这样:

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

前述的平等！

Complexity

非常感谢@k_g和@Hynek Pichi Vychodil的这一部分！

总和

(1...1000000000000000000000000000000).总和

它是一个常数，但乘法是O((logn)²)，所以对于整数范围，Enumerable#总和是O((logn)²).

注射

(1...1000000000000000000000000000000).注射(:+)

需要999999999999999999999999999999999998个添加项！

加法是O(对数n)，所以Enumerable#注射是O(对数n).

输入1E30，输入注射，永不返回.太阳早就要爆炸了！

Test

判断是否添加了Ruby整数很容易:

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

class Integer
  prepend AdditionInspector
end

puts (1..5).总和
#=> 15

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

事实上，从enum.c条 comments 中: