为什么总和比注入(:+)快得多？

Question

所以我在Ruby 2.4.0中运行了一些基准并意识到了这一点

(1...1000000000000000000000000000000).sum

立即计算,而

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

需要很长时间,我只是中止了操作.我的印象Range#sum是别名,Range#inject(:+)但似乎不是这样.那怎么sum工作,为什么它比这快得多inject(:+)？

NBEnumerable#sum(由其实现Range)的文档没有说明延迟评估或其他任何内容.

Answer 1

简短的回答

对于整数范围:

• 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中的可枚举#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 需要三个加法,一个乘法,一个减法和一个除法.

它是一个恒定的运算数,但乘法是O((log n)²),Enumerable#sum整数范围的O((log n)²)也是如此.

注入

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

需要999999999999999999999999999998添加!

加法是O(log n),Enumerable#injectO(n log n)也是.

随着1E30作为输入,inject与有去无回.太阳会在很久之前爆炸!

测试

很容易检查是否添加了Ruby Integers:

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#+.