performance - 종류 - 트리구조 실생활




자식 노드를 기억하여 재귀를 빠르게 할 수있는 방법이 있습니까? (12)

예를 들어, n 번째 피보나치 수를 계산하는 코드를 살펴보십시오.

fib(int n)
{
    if(n==0 || n==1)
        return 1;
    return fib(n-1) + fib(n-2);
}

이 코드의 문제점은 대부분의 컴퓨터에서 15보다 큰 수의 스택 오버플로 오류를 생성한다는 것입니다.

우리가 fib (10)를 계산한다고 가정합니다. 이 과정에서 fib (5)가 여러 번 계산된다고합니다. 빠른 검색을 위해이를 메모리에 저장하여 재귀 속도를 향상시킬 수있는 방법이 있습니까?

거의 모든 문제에서 사용할 수있는 일반적인 기술을 찾고 있습니다.


이 코드의 문제점은 대부분의 컴퓨터에서 15보다 큰 수의 스택 오버플로 오류를 생성한다는 것입니다.

정말? 어떤 컴퓨터를 사용하고 있습니까? 44시에는 오랜 시간이 걸리지 만 스택이 넘치지 않습니다. 사실, 스택이 오버 플로우 (Fibbonaci (46))가되기 전에 정수보다 큰 값을 얻으려고하면 40 억 개의 서명되지 않은 서명 (약 20 억 서명)이 가능합니다.

이것은 당신이하고 싶은 것을 위해 작동 할 것입니다 (빨리 움직입니다)

class Program
{
    public static readonly Dictionary<int,int> Items = new Dictionary<int,int>();
    static void Main(string[] args)
    {
        Console.WriteLine(Fibbonacci(46).ToString());
        Console.ReadLine();
    }

    public static int Fibbonacci(int number)
    {
        if (number == 1 || number == 0)
        {
            return 1;
        }

        var minus2 = number - 2;
        var minus1 = number - 1;

        if (!Items.ContainsKey(minus2))
        {
            Items.Add(minus2, Fibbonacci(minus2));
        }

        if (!Items.ContainsKey(minus1))
        {
            Items.Add(minus1, Fibbonacci(minus1));
        }

        return (Items[minus2] + Items[minus1]);
    }
}

@ ESRogs :

std::map lookup은 O (log n )이므로 느리게 진행됩니다. 벡터를 더 잘 사용하십시오.

vector<unsigned int> fib_cache;
fib_cache.push_back(1);
fib_cache.push_back(1);

unsigned int fib(unsigned int n) {
    if (fib_cache.size() <= n)
        fib_cache.push_back(fib(n - 1) + fib(n - 2));

    return fib_cache[n];
}

Scheme과 같은 일류 함수를 사용하는 언어를 사용하는 경우 초기 알고리즘을 변경하지 않고 메모를 추가 할 수 있습니다.

(define (memoize fn)
  (letrec ((get (lambda (query) '(#f)))
           (set (lambda (query value)
                  (let ((old-get get))
                    (set! get (lambda (q)
                                (if (equal? q query)
                                    (cons #t value)
                                    (old-get q))))))))
    (lambda args
      (let ((val (get args)))
        (if (car val)
            (cdr val)
            (let ((ret (apply fn args)))
              (set args ret)
              ret))))))


(define fib (memoize (lambda (x)
                       (if (< x 2) x
                           (+ (fib (- x 1)) (fib (- x 2)))))))

첫 번째 블록은 메모 작성 기능을 제공하고 두 번째 블록은 해당 기능을 사용하는 피보나치 시퀀스입니다. 이제는 O (n) 런타임이 있습니다 (O (2 ^ n)와는 대조적으로 암기가없는 알고리즘의 경우).

참고 : 제공된 메모 작성 기능은 이전 호출을 찾기 위해 일련의 클로저를 사용합니다. 최악의 경우 이것은 O (n) 일 수 있습니다. 그러나이 경우 원하는 값은 항상 체인의 맨 위에 있으므로 O (1) 조회가 수행됩니다.


네 통찰력이 맞습니다. 이를 동적 프로그래밍 이라고 합니다 . 이는 대개 일반적인 메모리 런타임 트레이드 오프입니다.

fibo의 경우 모든 것을 캐시 할 필요조차 없습니다.

이 질문의 저자는 피보나치를 계산하는 방법보다는 캐시하기위한 일반적인 방법을 찾고있는 것 같다. 위키 백과를 검색하거나 다른 포스터의 코드를보고이 대답을 얻으십시오. 그 해답은 시간과 메모리면에서 선형 적입니다.

** 여기에 선형 시간 알고리즘 O (n), 메모리 상수 **

in OCaml:

let rec fibo n = 
    let rec aux = fun
        | 0 -> (1,1)
        | n -> let (cur, prec) = aux (n-1) in (cur+prec, cur)
    let (cur,prec) = aux n in prec;;



in C++:

int fibo(int n) {
    if (n == 0 ) return 1;
    if (n == 1 ) return 1;
    int p = fibo(0);
    int c = fibo(1);
    int buff = 0;
    for (int i=1; i < n; ++i) {
      buff = c;
      c = p+c;
      p = buff;
    };
    return c;
};

선형 시간으로 수행됩니다. 그러나 로그는 실제로 가능합니다 !!! Roo의 프로그램 역시 선형이지만 속도가 느리고 메모리를 사용합니다.

다음은 로그 알고리즘 O (log (n))입니다.

이제 log-time 알고리즘 (way way way 빠름)을 위해 다음과 같은 방법이 있습니다. u (n), u (n-1), u (n + 1)을 계산하면 u 행렬 적용 :

| u(n+1) |  = | 1 1 | | u(n)   |
| u(n)   |    | 1 0 | | u(n-1) |    

그래서 당신은 :

| u(n)    |  = | 1 1 |^(n-1) | u(1) | = | 1 1 |^(n-1) | 1 |
| u(n-1)  |    | 1 0 |       | u(0) |   | 1 0 |       | 1 |

행렬의 지수를 계산하는 것은 로그의 복잡성을 갖습니다. 재귀 적으로 아이디어를 구현하십시오.

M^(0)    = Id
M^(2p+1) = (M^2p) * M
M^(2p)   = (M^p) * (M^p)  // of course don't compute M^p twice here.

대각선화할 수도 있습니다 (어려운 것은 아닙니다). 고유 값에서 금 번호와 공액을 찾을 수 있습니다. 결과는 u (n)에 대한 정확한 수학 공식을 제공합니다. 여기에는 그 고유치의 힘이 포함되어있어 복잡성은 여전히 ​​로그입니다.

Fibo는 종종 동적 프로그래밍을 설명하기 위해 예제로 사용되지만, 실제로 알 수 있듯이 실제로는 관련이 없습니다.

@ 존 : 해시와 관련이 없다고 생각합니다.

@ John2 :지도가 좀 일반적이라고 생각하지 않습니까? 피보나치의 경우, 모든 키가 연속적이어서 벡터가 적당합니다. 파이 오 코드 시퀀스를 계산하는 훨씬 더 빠른 방법이 있습니다. 저기있는 코드 샘플을보십시오.



이것이 무슨 언어 지? C에서 오버 플로우가 발생하지 않았습니다 ... 또한 힙에 조회 테이블을 만들거나지도를 사용할 수 있습니다


캐싱은 일반적으로 이런 종류의 일에 좋은 아이디어입니다. 피보나치 수는 일정하기 때문에 결과를 계산하면 캐시 할 수 있습니다. 빠른 c / 의사 코드 예제

class fibstorage {


    bool has-result(int n) { return fibresults.contains(n); }
    int get-result(int n) { return fibresult.find(n).value; }
    void add-result(int n, int v) { fibresults.add(n,v); }

    map<int, int>   fibresults;

}


fib(int n ) {
    if(n==0 || n==1)
            return 1;

    if (fibstorage.has-result(n)) {
        return fibstorage.get-result(n-1);
    }

    return ( (fibstorage.has-result(n-1) ? fibstorage.get-result(n-1) : fib(n-1) ) +
             (fibstorage.has-result(n-2) ? fibstorage.get-result(n-2) : fib(n-2) )
           );
}


calcfib(n) {
    v = fib(n);
    fibstorage.add-result(n,v);
}

모든 재귀가 3 개의 검색 결과를 얻으므로 이것은 매우 느릴 것입니다. 그러나 이것은 일반적인 아이디어를 설명해야합니다.


위키 백과 에 따르면 Fib (0)는 0이어야하지만 중요하지 않습니다.

다음은 사이클과 함께 간단한 C # 솔루션입니다.

ulong Fib(int n)
{
  ulong fib = 1;  // value of fib(i)
  ulong fib1 = 1; // value of fib(i-1)
  ulong fib2 = 0; // value of fib(i-2)

  for (int i = 0; i < n; i++)
  {
    fib = fib1 + fib2;
    fib2 = fib1;
    fib1 = fib;
  }

  return fib;
}

재귀를 꼬리 재귀 로 변환 한 다음 루프로 변환하는 것은 꽤 일반적인 트릭입니다. 자세한 내용은 예를 들어이 강의 (ppt)를 참조하십시오.


다른 사람들은 귀하의 질문에 정확하고 정확하게 답변했습니다 - 당신은 메모 작성을 원합니다.

꼬리 호출 최적화 (주로 함수 언어)를 사용하는 프로그래밍 언어는 스택 오버플로없이 재귀의 특정 경우를 수행 할 수 있습니다. 트릭이 있지만 피보나치의 정의에 직접적으로 적용되지는 않습니다.

귀하의 질문에 대한 말은 흥미로운 생각을하게했습니다. 단지 스택 프레임의 하위 집합을 저장하고 필요한 경우 재 구축함으로써 순수 재귀 함수의 스택 오버플로를 방지합니다. 몇 가지 경우에만 실제로 유용합니다. 귀하의 알고리즘이 반환과 대조적으로 컨텍스트에만 조건부 의존하는 경우 및 / 또는 속도가 아닌 메모리를 최적화하는 경우.


다른 포스터가 지적했듯이, memoization 은 속도를 위해 메모리를 교환하는 표준 방법이며, 여기에 함수에 대한 메모 작성을 구현하는 의사 코드가 있습니다 (함수에 부작용이없는 경우).

초기 기능 코드 :

 function (parameters)
      body (with recursive calls to calculate result)
      return result

이것은로 변형되어야한다.

 function (parameters)
      key = serialized parameters to string
      if (cache[key] does not exist)  {
           body (with recursive calls to calculate result)
           cache[key] = result
      }
      return cache[key]


그런데 Perl은 사용자가 지정한 코드의 모든 함수에 대해 이것을 수행하는 memoize 모듈을 가지고 있습니다.

# Compute Fibonacci numbers
sub fib {
      my $n = shift;
      return $n if $n < 2;
      fib($n-1) + fib($n-2);
}

이 기능을 메모하기 위해서는 다음을 사용하여 프로그램을 시작하십시오.

use Memoize;
memoize('fib');
# Rest of the fib function just like the original version.
# Now fib is automagically much faster ;-)






recursion