Kurze Antwort
Für einen ganzzahligen Bereich:
Enumerable#sum
kehrt zurück (range.max-range.min+1)*(range.max+range.min)/2
Enumerable#inject(:+)
iteriert über jedes Element.
Theorie
Die Summe der ganzen Zahlen zwischen 1 und n
wird als Dreieckszahl bezeichnet und ist gleich n*(n+1)/2
.
Die Summe der ganzen Zahlen zwischen n
und m
ist die Dreieckszahl von m
minus der Dreieckszahl von n-1
, die gleich m*(m+1)/2-n*(n-1)/2
ist und geschrieben werden kann (m-n+1)*(m+n)/2
.
Aufzählbare # Summe in Ruby 2.4
Diese Eigenschaft wird in Enumerable#sum
für ganzzahlige Bereiche verwendet:
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
sieht aus wie das :
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);
was äquivalent ist zu:
(range.max-range.min+1)*(range.max+range.min)/2
die vorgenannte Gleichheit!
Komplexität
Vielen Dank an @k_g und @ Hynek-Pichi-Vychodil für diesen Teil!
Summe
(1...1000000000000000000000000000000).sum
erfordert drei Additionen, eine Multiplikation, eine Subtraktion und eine Division.
Es ist eine konstante Anzahl von Operationen, aber die Multiplikation ist O ((log n) ²), ebenso Enumerable#sum
wie O ((log n) ²) für einen ganzzahligen Bereich.
injizieren
(1...1000000000000000000000000000000).inject(:+)
erfordert 999999999999999999999999999998 Ergänzungen!
Die Addition ist O (log n), ebenso Enumerable#inject
wie O (n log n).
Mit 1E30
als Eingabe, inject
mit nie zurückkehren. Die Sonne wird lange vorher explodieren!
Prüfung
Es ist einfach zu überprüfen, ob Ruby Integers hinzugefügt werden:
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
In der Tat aus enum.c
Kommentaren:
Enumerable#sum
Methode kann Methode Neudefinition von "+"
Methoden wie nicht respektieren Integer#+
.
n+1
Bereiche? Ich habe nicht 2.4 installiert oder ich würde mich selbst testen, aber es handelt sich um andere aufzählbare Objekte, die durch grundlegende Addition behandelt werden, da sie sichinject(:+)
abzüglich des Overheads des zu verarbeitenden Symbols befinden würden.n, n+1, n+2, .., m
die eine arithmetische Reihe darstellt, deren Summe gleich ist(m-n+1)*(m+n)/2
. Ebenso ist die Summe einer geometrischen Reihe ,n, (α^1)n, (α^2)n, (α^3)n, ... , (α^m)n
. kann aus einem Ausdruck in geschlossener Form berechnet werden.