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

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

(1...1000000000000000000000000000000).sum 

而立即计算

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

需要很长时间才会中止手术。 我的印象是Range#sumRange#inject(:+)的别名,但似乎不是这样。 那么sum是如何工作的?为什么它比inject(:+)更快呢?

注意 Enumerable#sum (由Range实现)的文档并没有提到任何有关懒惰评估的内容或者这些内容。

简短的回答

对于整数范围:

  • Enumerable#sum返回(range.max-range.min+1)*(range.max+range.min)/2
  • Enumerable#inject(:+)迭代每个元素。

理论

1和n之间的整数之和称为三angular形数 ,等于n*(n+1)/2

nm之间的整数之和是m的三angular形数减去n-1的三angular形数,它等于m*(m+1)/2-n*(n-1)/2 ,可以是写(m-n+1)*(m+n)/2

在Ruby 2.4中枚举#总和

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)2),所以Enumerable#sum是O((log n)2)的整数范围。

注入

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

要求999999999999999999999999999998补充!

另外是O(log n),所以Enumerable#inject是O(n log n)。

1E30作为input, inject永不返回。 太阳将爆炸很久以前!

testing

检查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#+