[ruby] 왜 inject (: +)보다 합계가 훨씬 빠릅니까?

Program / 글쓴이

그래서 Ruby 2.4.0에서 일부 벤치 마크를 실행하고 있었고

(1...1000000000000000000000000000000).sum

반면에 즉시 계산

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

작업을 중단하는 데 너무 오래 걸립니다. 나는 Range#sum별명 인 인상 을 Range#inject(:+)받았지만 사실이 아닌 것 같습니다. 그렇다면 어떻게 sum작동하며 왜 그렇게 훨씬 빠릅 inject(:+)니까?

NB에Enumerable#sum 의해 구현 된 문서 Range는 게으른 평가 또는 그 라인을 따라 아무것도 말하지 않습니다.

답변

짧은 답변

정수 범위의 경우 :

  • Enumerable#sum 보고 (range.max-range.min+1)*(range.max+range.min)/2
  • Enumerable#inject(:+) 모든 요소를 ​​반복합니다.

이론

1과 3 사이의 정수의 합을 삼각 수n 라고하며 같습니다 .n*(n+1)/2

사이의 정수 합 n과 m의 삼각형 개수 m마이너스의 삼각형의 개수 n-1와 동일, m*(m+1)/2-n*(n-1)/2및 기록 될 수있다 (m-n+1)*(m+n)/2.

Ruby 2.4에서 열거 가능한 #sum

이 속성은 Enumerable#sum정수 범위 에 사용됩니다 .

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 다음과 같이 보입니다 :

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

이는 다음과 같습니다.

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

앞서 언급 한 평등!

복잡성

이 부분에 대해 @k_g와 @ Hynek-Pichi-Vychodil에게 감사드립니다!

합집합

(1...1000000000000000000000000000000).sum
곱하기, 빼기 및 나누기의 세 가지 덧셈이 필요합니다.

상수 연산 수이지만 곱셈은 O ((log n) ²)이므로 Enumerable#sum정수 범위의 경우 O ((log n) ²)입니다.

주사하다

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

999999999999999999999999999998 추가 필요!

덧셈은 O (log n)이므로 Enumerable#injectO (n log n)입니다.

와 1E30, 입력으로 inject반환하지 않습니다와. 태양은 오래 전에 폭발 할 것입니다!

테스트

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

실제로 enum.c의견에서 :

Enumerable#sum방법은 "+"
과 같은 방법의 방법 재정의를 존중하지 않을 수 있습니다 Integer#+.

답변