재귀 검색 최적화

Question

재귀 대 피보나치 시퀀스의 시간을 측정하기 위해 실험을 실행했습니다. 재귀 적 메서드의 성능을 향상시키는 더 좋은 방법이 있습니까?

require 'benchmark' 

def fibonacci_iterative(n) 
    fib_numbers = [0, 1] 
    iterate = n-1 
    iterate.times do 
    number = fib_numbers[-2] + fib_numbers[-1] 
    fib_numbers << number 
    end 
    p fib_numbers[-1] 
end 

def fibonacci_recursive(n) 
    fib_number = 0 
    if n == 0 || n == 1 
    n 
    else 
    fib_number = fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2) 
    end 
end 

puts Benchmark.measure {fibonacci_iterative(5)} 
puts Benchmark.measure {fibonacci_recursive(5)} 

5 
    0.000000 0.000000 0.000000 ( 0.000037) 
    0.000000 0.000000 0.000000 ( 0.000005) 

puts Benchmark.measure {fibonacci_iterative(45)} 
puts Benchmark.measure {fibonacci_recursive(45)} 

1134903170 
    0.000000 0.000000 0.000000 ( 0.000039) 
378.990000 0.330000 379.320000 (379.577337) 

이것은 재귀의 고유 한 기능입니까?

Answer 1

루비의 피보나치 구현이 정확합니다. 당신은 유일한 장점은 조금 더 간결 그리고 당신은, 사실,이 요구 아니에요 추가 변수를 사용하지 않는 것이 다음과 같은 방법

def fib(n) 
    if n < 2 
    n 
    else 
    fib(n-1) + fib(n-2) 
    end 
end 

에서 그것을 다시 작성할 수 있습니다.

그러나 그렇다고해서 알고리즘에 비해 비용면에서 비용이 변하지 않습니다. few possible improvements이 있습니다. 재귀 알고리즘은 비 재귀 버전보다 느린 것으로 잘 알려져 있습니다.

피보나치 재귀 시퀀스의 시간 복잡도는 O(n^2)입니다. (계산에 대한 세부 사항은 건너 뜁니다. 많은 토픽이 있으며 SO answers이 사용 가능합니다). several variations이 있습니다.

빠른 개선 중 하나는 캐시를 추가하는 것입니다. 이렇게하면 시퀀스의 동일한 하위 번호 계산이 줄어 듭니다.

여기에 스토리지를 스토리지로 사용하는 매우 빠르고 불량한 예가 있습니다.

$cache = [] 

def fib(n) 
    $cache[n] ||= if n < 2 
    n 
    else 
    fib(n-1) + fib(n-2) 
    end 
end 

그냥 재미를 위해, 여기에 더 압축, 독립적 인 대안

def fib(n) 
    $fibcache ||= [] 
    $fibcache[n] ||= (n < 2 ? n : fib(n-1) + fib(n-2)) 
end 

PS입니다. 나는 memoization 패턴을 보여주기 위해 글로벌 변수만을 예제로 사용했습니다. 더 나은 시스템을 사용해야하며, 전역 변수는 Ruby에서 코드 냄새로 간주됩니다.

Answer 2

당신은 재귀 피보나치를 계산으로 결과를 저장하려고 할 수 있습니다

:

def fibonacci_recursive(n): 
    def fib_rec(n, a, b): 
     if n == 1: 
      return a 
     return fib_rec(n - 1, a + b, a) 
    return fib_rec(n, 1, 0) 

귀하의 재귀 코드는 지수의 행동이 : O (피^N)을 여기서 피 = (1 + SQRT (5))/2.

EDIT : 이것은 Python (Ruby 태그를 보지 못했습니다)입니다. 상당히 간단하게 번역해야합니다.

Answer 3

긴 실행 시간은 고유 한 재귀 함수는 아니지만 중복 된 재귀 계산이있을 때 자주 발생합니다. "메모 (memoization)"라는 기술을 사용하면 값을 한 번만 계산하고 나중에 사용할 수 있도록 표를 작성하는 것을 피할 수 있습니다.

여기 Fixnum이라는으로 원숭이 패치 피보나치 수의 memoized 재귀 구현 ... 당신은 정말 큰 가고 싶은 경우

class Fixnum 
    @@fib_value = [0,1] 

    def fib 
    raise "fib not defined for negative numbers" if self < 0 
    @@fib_value[self] ||= (self-1).fib + (self-2).fib 
    end 
end 

0.fib  # => 0 
1.fib  # => 1 
2.fib  # => 1 
5.fib  # => 5 
100.fib # => 354224848179261915075 

, O는 피보나치 알고리즘의 matrix multiplication version을 사용이야 (로그 n) : 출력 2600 80 칼럼 라인 위에 있지만

class Fixnum 
    def fib 
    raise "fib not defined for negative numbers" if self < 0 
    self.zero? ? self : matrix_fib(self)[1] 
    end 

    private 

    def matrix_fib(n) 
    if n == 1 
     [0,1] 
    else 
     f = matrix_fib(n/2) 
     c = f[0] * f[0] + f[1] * f[1] 
     d = f[1] * (f[1] + 2 * f[0]) 
     n.even? ? [c,d] : [d,c+d] 
    end 
    end 
end 

45.fib # => 1134903170 confirms correctness 

하면, 재귀 스택을 날려 거의 순간적 1000000.fib를 계산할 수 없다.