ruby - 为什么 sum 比 inject( :+)?

Question

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

(1...1000000000000000000000000000000).sum

立即计算而

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

花了很长时间，我刚刚中止了操作。我的印象是 Range#sum 是 Range#inject(:+) 的别名，但事实并非如此。那么 sum 是如何工作的，为什么它比 inject(:+) 快得多？

N.B. Enumerable#sum(由 Range 实现)的文档没有说明惰性求值或任何类似的内容.

Answer 1

简答

对于整数范围:

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

---

理论

1 到 n 之间的整数之和称为 triangular number , 并且等于 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)²)，所以 Enumerable#sum 对于整数范围是 O((log n)²)。

注入(inject)

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

需要 999999999999999999999999999998 次添加!

加法是 O(log n)，所以 Enumerable#inject 是 O(n log n)。

以 1E30 作为输入，inject 永不返回。太阳早就爆炸了!

测试

检查是否添加了 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 method may not respect method redefinition of "+" methods such as Integer#+.