简短回答
对于整数范围:
-
Enumerable#sum
回报(range.max-range.min+1)*(range.max+range.min)/2
-
Enumerable#inject(:+)
迭代每个元素。
Theory
1 到 1 之间的整数之和n
被称为三角数 https://en.wikipedia.org/wiki/Triangular_number,并且等于n*(n+1)/2
.
之间的整数之和n
and m
是三角形数m
减去三角形数n-1
,等于m*(m+1)/2-n*(n-1)/2
,并且可以写成(m-n+1)*(m+n)/2
.
Ruby 2.4 中的枚举#sum
该属性用于Enumerable#sum http://ruby-doc.org/core-2.4.0/Enumerable.html#method-i-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 的这一部分!
sum
(1...1000000000000000000000000000000).sum
需要三次加法、一次乘法、一次减法和一次除法。
它的运算次数是恒定的,但乘法是 O((log n)²),所以Enumerable#sum
对于整数范围来说是 O((log n)²)。
inject
(1...1000000000000000000000000000000).inject(:+)
需要999999999999999999999999999998个补充!
加法是 O(log n),所以Enumerable#inject
是 O(n log n)。
With 1E30
作为输入,inject
永远不会回来。太阳早就爆炸了!
Test
检查 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#+
.