Pourquoi la somme est-elle tellement plus rapide que l'inject (: +)?

Question

J'ai donc été à l'exécution de certains repères dans Ruby 2.4.0 et réalisé que

(1...1000000000000000000000000000000).sum

calcule immédiatement alors que

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

prend tellement de temps que j'ai juste abandonné l'opération. J'étais sous l'impression qu' Range#sum a été un alias pour Range#inject(:+) , mais il semble que ce n'est pas vrai. Alors, comment est - sum de travail, et pourquoi est-il tellement plus rapide qu' inject(:+)?

N. B. La documentation pour Enumerable#sum (ce qui est mis en œuvre par Range) ne dit rien à propos de l'évaluation différée ou quelque chose le long de ces lignes.

Answer 1

Réponse courte

Pour un entier portée :

• Enumerable#sum retours (range.max-range.min+1)*(range.max+range.min)/2
• Enumerable#inject(:+) itère sur chaque élément.

---

La théorie de l'

La somme des entiers compris entre 1 et n est appelé un nombre triangulaire, et est égal à n*(n+1)/2.

La somme des entiers compris entre n et m est la forme triangulaire de nombre de m moins la forme triangulaire de nombre de n-1, ce qui est égal à m*(m+1)/2-n*(n-1)/2, et peuvent être écrites (m-n+1)*(m+n)/2.

Énumérable#somme en Ruby 2.4

Cette propriété est utilisée dans les Enumerable#sum pour l'entier des plages :

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 ressemble à ceci :

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

ce qui est équivalent à:

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

ladite égalité!

La complexité

Merci beaucoup à @k_g et @Hynek-Pichi-Vychodil pour cette partie!

somme

(1...1000000000000000000000000000000).sum nécessite trois additions, multiplication, soustraction et division.

C'est un nombre constant d'opérations, mais la multiplication est O((log n)2), de sorte Enumerable#sum O((log n)2) pour un intervalle entier.

injecter

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

nécessite 999999999999999999999999999998 ajouts!

Plus est O(log n), so Enumerable#inject O(n log n).

Avec 1E30 comme entrée, inject à ne jamais revenir. Le soleil va exploser depuis longtemps!

Test

Il est facile de vérifier si Ruby Entiers sont ajoutés :

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

En effet, à partir d' enum.c commentaires :

Enumerable#sum méthode peut ne pas respecter la méthode de redéfinition de l' "+" des méthodes telles que Integer#+.