Jadi saya menjalankan beberapa tolok ukur di Ruby 2.4.0 dan menyadari itu

(1...1000000000000000000000000000000).sum

menghitung segera sedangkan

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

Butuh begitu lama sehingga saya baru saja membatalkan operasi. Saya berada di bawah kesan bahwa Range#sumitu adalah alias untuk Range#inject(:+)tetapi sepertinya itu tidak benar. Jadi bagaimana cara sumkerjanya, dan mengapa lebih cepat dari itu inject(:+)?

NB Dokumentasi untuk Enumerable#sum(yang dilaksanakan oleh Range) tidak mengatakan apa-apa tentang evaluasi malas atau apa pun di sepanjang garis itu.

Jawaban singkat

Untuk rentang integer:

• Enumerable#sum kembali (range.max-range.min+1)*(range.max+range.min)/2
• Enumerable#inject(:+) iterates atas setiap elemen.

Teori

Jumlah bilangan bulat antara 1 dan ndisebut bilangan segitiga , dan sama dengan n*(n+1)/2.

Jumlah bilangan bulat antara ndan madalah jumlah segitiga mminus jumlah segitiga n-1, yang sama dengan m*(m+1)/2-n*(n-1)/2, dan dapat ditulis (m-n+1)*(m+n)/2.

Dihitung # sum dalam Ruby 2.4

Properti ini digunakan Enumerable#sumuntuk rentang bilangan bulat:

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 terlihat seperti ini :

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

yang setara dengan:

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

kesetaraan yang disebutkan di atas!

Kompleksitas

Terima kasih banyak kepada @k_g dan @ Hynek-Pichi-Vychodil untuk bagian ini!

jumlah

(1...1000000000000000000000000000000).sum membutuhkan tiga tambahan, perkalian, substraksi, dan pembagian.

Ini adalah jumlah operasi yang konstan, tetapi perkalian adalah O ((log n) ²), demikian Enumerable#sumjuga O ((log n) ²) untuk rentang integer.

menyuntikkan

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

membutuhkan tambahan 9999999999999999999999999998!

Penambahan adalah O (log n), demikian Enumerable#injectjuga O (n log n).

Dengan 1E30sebagai input, injectdengan tidak pernah kembali. Matahari akan meledak jauh sebelumnya!

Uji

Sangat mudah untuk memeriksa apakah Ruby Integers sedang ditambahkan:

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

Memang, dari enum.ckomentar:

Enumerable#summetode mungkin tidak menghormati redefinisi "+" metode metode seperti Integer#+.