Dlaczego suma jest o wiele szybsza niż wstrzyknięcie (: +)?

Question 1

Więc przeprowadziłem kilka testów porównawczych w Rubim 2.4.0 i zdałem sobie z tego sprawę

(1...1000000000000000000000000000000).sum

oblicza natychmiast, podczas gdy

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

trwa tak długo, że właśnie przerwałem operację. Miałem wrażenie, że Range#sumto alias dla, Range#inject(:+)ale wygląda na to, że to nieprawda. Jak więc sumdziała i dlaczego jest o wiele szybszy niż inject(:+)?

Uwaga : Dokumentacja programu Enumerable#sum(która jest zaimplementowana przez Range) nie mówi nic o leniwej ocenie ani nic w tym zakresie.

Question 2

Krótka odpowiedź

Dla zakresu liczb całkowitych:

Enumerable#sum zwroty (range.max-range.min+1)*(range.max+range.min)/2
Enumerable#inject(:+) iteruje po każdym elemencie.

Teoria

Suma liczb całkowitych między 1 i nnazywana jest liczbą trójkątną i jest równa n*(n+1)/2.

Suma liczb całkowitych między ni mjest liczbą trójkątną mminus trójkątna liczba n-1, która jest równa m*(m+1)/2-n*(n-1)/2i można ją zapisać (m-n+1)*(m+n)/2.

Enumerable # sum w Rubim 2.4

Ta właściwość jest używana w Enumerable#sumzakresach liczb całkowitych:

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 wygląda tak :

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

co jest równoważne z:

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

wspomniana równość!

Złożoność

Wielkie dzięki dla @k_g i @ Hynek-Pichi-Vychodil za tę część!

suma

(1...1000000000000000000000000000000).sum wymaga trzech dodawania, mnożenia, odejmowania i dzielenia.

Jest to stała liczba operacji, ale mnożenie to O ((log n) ²), a więc Enumerable#sumO ((log n) ²) dla zakresu liczb całkowitych.

wstrzykiwać

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

wymaga 999999999999999999999999999998 dodatków!

Dodawanie to O (log n), więc Enumerable#injectjest O (n log n).

Z 1E30wejściem, injectbez powrotu. Słońce już dawno wybuchnie!

Test

Łatwo jest sprawdzić, czy dodawane są liczby całkowite 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

Rzeczywiście, z enum.ckomentarzy:

Enumerable#summetoda może nie uwzględniać przedefiniowania "+" metod, takich jak Integer#+.