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

所以我在 Ruby2.4.0中运行了一些基准测试，并意识到

(1...1000000000000000000000000000000).sum

立即计算，而

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

花了这么长时间，所以我中止了手术。我的印象是 Range#sum是 Range#inject(:+)的别名，但似乎不是这样的。那么 sum是如何工作的，为什么它比 inject(:+)快那么多呢？

注意: Enumerable#sum的文档(由 Range实现)没有提到任何关于延迟计算的内容或者类似的内容。

9224 次浏览
小开
最佳答案

长话短说

对于整数范围:

  • 返回 (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)2) ，所以对于整数范围来说，Enumerable#sum是 O ((log n)2)。

注射

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

需要99999999999999999999999999999999999999998添加！

加法是 O (log n) ，所以 Enumerable#inject是 O (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#+。


提交答案