为什么 sum 比 inject(:+) 快这么多? [英] Why is sum so much faster than 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<的三角数/code>,等于
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 asInteger#+
.
这篇关于为什么 sum 比 inject(:+) 快这么多?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!