Então, eu estava executando alguns benchmarks no Ruby 2.4.0 e percebi que

(1...1000000000000000000000000000000).sum

calcula imediatamente enquanto

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

leva tanto tempo que acabei de abortar a operação. Fiquei com a impressão de que Range#sumera um apelido para, Range#inject(:+)mas parece que isso não é verdade. Então, como sumfunciona e por que é muito mais rápido que inject(:+)?

NB A documentação para Enumerable#sum(que é implementada por Range) não diz nada sobre avaliação lenta ou algo nesse sentido.

Resposta curta

Para um intervalo inteiro:

• Enumerable#sum retorna (range.max-range.min+1)*(range.max+range.min)/2
• Enumerable#inject(:+) itera sobre cada elemento.

Teoria

A soma dos números inteiros entre 1 e né chamada de número triangular e é igual a n*(n+1)/2.

A soma dos números inteiros entre ne mé o número triangular de mmenos o número triangular de n-1, que é igual a m*(m+1)/2-n*(n-1)/2, e pode ser gravado (m-n+1)*(m+n)/2.

# Sum enumerável no Ruby 2.4

Esta propriedade é usada em Enumerable#sumpara intervalos inteiros:

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 se parece com isso :

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);

que é equivalente a:

(range.max-range.min+1)*(range.max+range.min)/2

a igualdade acima mencionada!

Complexidade

Muito obrigado a @k_g e @ Hynek-Pichi-Vychodil por esta parte!

soma

(1...1000000000000000000000000000000).sum requer três adições, uma multiplicação, uma subtração e uma divisão.

É um número constante de operações, mas a multiplicação é O ((log n) ²), assim Enumerable#sumcomo O ((log n) ²) para um intervalo inteiro.

injetar

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

requer 999999999999999999999999999998 adições!

A adição é O (log n), assim Enumerable#injectcomo O (n log n).

Com 1E30como entrada, injectsem retorno. O sol vai explodir muito antes!

Teste

É fácil verificar se estão sendo adicionados números inteiros 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

De fato, a partir dos enum.ccomentários:

Enumerable#sumO método pode não respeitar a redefinição de "+" métodos como Integer#+.