usado - ruby wikipedia



Por que a soma é muito mais rápida que a injeção(:+)? (1)

Resposta curta

Para um intervalo inteiro:

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

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 inteiros entre n e m é o número triangular de m menos o número triangular de n-1 , que é igual a m*(m+1)/2-n*(n-1)/2 , e pode ser escrito (m-n+1)*(m+n)/2 .

Enumerável # sum em Ruby 2.4

Esta propriedade é usada em Enumerable#sum para intervalos de números 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 aparece assim:

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

o que equivale a:

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

a igualdade acima mencionada!

Complexidade

Muito obrigado ao @k_g e @ Hynek-Pichi-Vychodil por essa 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) ²), então Enumerable#sum é O ((log n) ²) para um intervalo inteiro.

injetar

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

requer 999999999999999999999999999998 adições!

A adição é O (log n), então Enumerable#inject é O (n log n).

Com 1E30 como entrada, inject com nunca retornar. O sol vai explodir muito antes!

Teste

É fácil verificar se os números inteiros do Ruby estão sendo adicionados:

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 de enum.c comentários:

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

Então eu estava rodando 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. Eu estava com a impressão de que Range#sum era um apelido para Range#inject(:+) mas parece que isso não é verdade. Então, como a sum funciona e por que é tão mais rápida do que inject(:+) ?

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





ruby