为什么总和比注入(:+)快得多?
所以我在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#+
。