为什么 sum 比 inject(:+) 快这么多?

本文介绍了为什么 sum 比 inject(:+) 快这么多?的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

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

So I was running some benchmarks in Ruby 2.4.0 and realized that

(1...1000000000000000000000000000000).sum

立即计算而

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

花费的时间太长，我只是中止了操作.我的印象是 Range#sum 是 Range#inject(:+) 的别名，但这似乎不是真的.那么 sum 是如何工作的，为什么它比 inject(:+) 快这么多?

takes so long that I just aborted the operation. I was under the impression that Range#sum was an alias for Range#inject(:+) but it seems like that is not true. So how does sum work, and why is it so much faster than inject(:+)?

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

N.B. The documentation for Enumerable#sum (which is implemented by Range) does not say anything about lazy evaluation or anything along those lines.

推荐答案

简短回答

对于整数范围:

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

• Enumerable#sum returns (range.max-range.min+1)*(range.max+range.min)/2
• Enumerable#inject(:+) iterates over every element.

介于 1 和 n 之间的整数之和称为 三角数，是等于 n*(n+1)/2.

The sum of integers between 1 and n is called a triangular number, and is equal to n*(n+1)/2.

n 和 m 之间的整数之和是 m 的三角数减去 n-1，等于m*(m+1)/2-n*(n-1)/2，可以写成(m-n+1)*(m+n)/2.

The sum of integers between n and m is the triangular number of m minus the triangular number of n-1, which is equal to m*(m+1)/2-n*(n-1)/2, and can be written (m-n+1)*(m+n)/2.

此属性在 Enumerable#sum 中使用 用于整数范围:

This property in used in Enumerable#sum for integer ranges :

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 这部分！

Thanks a lot to @k_g and @Hynek-Pichi-Vychodil for this part!

(1...1000000000000000000000000000000).sum需要三个加法，乘法、减法和除法.

(1...1000000000000000000000000000000).sum requires three additions, a multiplication, a substraction and a division.

这是一个常数操作，但乘法是 O((log n)²)，所以 Enumerable#sum 对于整数范围是 O((log n)²).

It's a constant number of operations, but multiplication is O((log n)²), so Enumerable#sum is O((log n)²) for an integer range.

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

需要 999999999999999999999999999998 添加！

requires 999999999999999999999999999998 additions!

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

Addition is O(log n), so Enumerable#inject is O(n log n).

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

With 1E30 as input, inject with never return. The sun will explode long before!

检查是否添加了 Ruby 整数很容易:

It's easy to check if Ruby Integers are being added :

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#+ 等方法.

Enumerable#sum method may not respect method redefinition of "+" methods such as Integer#+.