为什么总和比注入(:+)快得多?
所以我在Ruby 2.4.0中运行了一些基准,并意识到这一点
(1...1000000000000000000000000000000).sum
而立即计算
(1...1000000000000000000000000000000).inject(:+)
需要很长时间才会中止手术。 我的印象是Range#sum是Range#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 。
n和m之间的整数之和是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#+。