하위 노드를 기억하여 재귀 속도를 높이는 방법이 있습니까?

Question

예를 들어 N-th Fibonacci 번호를 계산하는 코드를보십시오.

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

이 코드의 문제점은 (대부분의 컴퓨터에서) 15보다 큰 숫자에 대해 스택 오버플로 오류가 발생한다는 것입니다.

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

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

Answer 1

네, 당신의 통찰력이 정확합니다.이것은 ... 불리운다 동적 프로그래밍.이는 일반적으로 일반적인 메모리 런타임 절충안입니다.

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

편집]이 질문의 저자는 Fibonacci를 계산하는 방법보다는 캐시의 일반적인 방법을 찾고있는 것 같습니다.이 답변을 얻으려면 Wikipedia를 검색하거나 다른 포스터의 코드를 살펴보십시오.그 대답은 시간과 기억에 있어서 선형적입니다.

**여기에 메모리의 상수인 선형 시간 알고리즘 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))입니다.

이제 로그 시간 알고리즘(훨씬 더 빠르다)의 방법은 다음과 같습니다.u(n), u(n-1)을 알고 있는 경우 u(n+1), u(n) 계산은 행렬을 적용하여 수행할 수 있습니다.

| 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는 종종 동적 프로그래밍을 설명하기 위한 예로 사용되지만, 보시다시피 실제로는 관련이 없습니다.

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

@존2:지도가 좀 일반적인 것 같지 않나요?피보나치의 경우 모든 키가 연속되어 있으므로 벡터가 적절합니다. 다시 한 번 fibo 시퀀스를 계산하는 훨씬 빠른 방법이 있습니다. 저기 있는 내 코드 샘플을 참조하세요.

Answer 2

이것을 메모이제이션(memoization)이라고 하는데 메모이제이션에 관한 아주 좋은 글이 있습니다. 매튜 포드위소키 요즘 게시됨.이를 예시하기 위해 피보나치(Fibonacci)를 사용합니다.그리고 C#에서도 코드를 보여줍니다.읽어 여기.

Answer 3

C#을 사용하고 있고 다음을 사용할 수 있는 경우 포스트샤프, 코드에 대한 간단한 메모 기능은 다음과 같습니다.

[Serializable]
public class MemoizeAttribute : PostSharp.Laos.OnMethodBoundaryAspect, IEqualityComparer<Object[]>
{
    private Dictionary<Object[], Object> _Cache;

    public MemoizeAttribute()
    {
        _Cache = new Dictionary<object[], object>(this);
    }

    public override void OnEntry(PostSharp.Laos.MethodExecutionEventArgs eventArgs)
    {
        Object[] arguments = eventArgs.GetReadOnlyArgumentArray();
        if (_Cache.ContainsKey(arguments))
        {
            eventArgs.ReturnValue = _Cache[arguments];
            eventArgs.FlowBehavior = FlowBehavior.Return;
        }
    }

    public override void OnExit(MethodExecutionEventArgs eventArgs)
    {
        if (eventArgs.Exception != null)
            return;

        _Cache[eventArgs.GetReadOnlyArgumentArray()] = eventArgs.ReturnValue;
    }

    #region IEqualityComparer<object[]> Members

    public bool Equals(object[] x, object[] y)
    {
        if (Object.ReferenceEquals(x, y))
            return true;

        if (x == null || y == null)
            return false;

        if (x.Length != y.Length)
            return false;

        for (Int32 index = 0, len = x.Length; index < len; index++)
            if (Comparer.Default.Compare(x[index], y[index]) != 0)
                return false;

        return true;
    }

    public int GetHashCode(object[] obj)
    {
        Int32 hash = 23;

        foreach (Object o in obj)
        {
            hash *= 37;
            if (o != null)
                hash += o.GetHashCode();
        }

        return hash;
    }

    #endregion
}

다음은 이를 사용한 샘플 Fibonacci 구현입니다.

[Memoize]
private Int32 Fibonacci(Int32 n)
{
    if (n <= 1)
        return 1;
    else
        return Fibonacci(n - 2) + Fibonacci(n - 1);
}

Answer 4

C++의 빠르고 지저분한 메모 기능:

모든 재귀적 방법 type1 foo(type2 bar) { ... } 쉽게 메모됩니다 map<type2, type1> M.

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

// with memoization
map<int, int> M = map<int, int>();
int fib(int n)
{
    if(n==0 || n==1)
        return 1;

    // only compute the value for fib(n) if we haven't before
    if(M.count(n) == 0)
        M[n] = fib(n-1) + fib(n-2);

    return M[n];
}

편집하다:@콘라드 루돌프
Konrad는 std::map이 여기서 사용할 수 있는 가장 빠른 데이터 구조가 아니라고 지적합니다.그건 사실이에요, vector<something> a보다 빨라야 한다 map<int, something> (함수의 재귀 호출에 대한 입력이 이 경우처럼 연속적인 정수가 아닌 경우 더 많은 메모리가 필요할 수 있지만) 일반적으로 맵을 사용하는 것이 편리합니다.

Answer 5

에 따르면 위키피디아 Fib(0)은 0이어야 하지만 상관없습니다.

다음은 for Cycle을 사용한 간단한 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).

Answer 6

이것이 무슨 언어 지?그것은 C에서 아무것도 넘치지 않습니다 ...또한 힙에 조회 테이블을 생성하거나 맵을 사용해 볼 수도 있습니다.

Answer 7

캐싱은 일반적으로 이런 종류의 일에 좋은 생각입니다.피보나치 수는 일정하므로 계산한 결과를 캐시할 수 있습니다.빠른 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번의 조회가 발생하므로 이는 매우 느립니다. 그러나 이는 일반적인 아이디어를 설명해야 합니다.

Answer 8

이것은 의도적으로 선택된 예입니까?(예:테스트하고 싶은 극단적인 경우)

현재 O(1.6^n)이므로 실수로 잘못된 코드를 작성하는 것이 아니라 이 문제의 일반적인 경우(값 캐싱 등)를 처리하는 방법에 대한 답변을 찾고 있는지 확인하고 싶습니다. :D

이 특정 사례를 살펴보면 다음과 같은 내용을 알 수 있습니다.

var cache = [];
function fib(n) {
    if (n < 2) return 1;
    if (cache.length > n) return cache[n];
    var result = fib(n - 2) + fib(n - 1);
    cache[n] = result;
    return result;
}

최악의 경우 O(n)으로 퇴화됩니다 :D

[편집하다:*는 +와 같지 않습니다 :D ]

[또 다른 편집:하스켈 버전(왜냐면 나는 마조히스트 같은 사람이니까)

fibs = 1:1:(zipWith (+) fibs (tail fibs))
fib n = fibs !! n

]

Answer 9

맵을 사용해 보십시오. n은 키이고 해당 피보나치 수는 값입니다.

@폴

정보 주셔서 감사합니다.나는 그것을 몰랐다.로부터 위키피디아 링크 당신은 다음과 같이 언급했습니다.

이미 계산 된 값을 저장하는이 기술은 메모리라고합니다.

네, 이미 코드(+1)를 살펴봤습니다.:)

Answer 10

@ESRogs:

std::map 조회는 영형(통나무 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];
}

Answer 11

다른 사람들이 귀하의 질문에 정확하고 정확하게 답변해 주었습니다. 귀하는 메모이제이션을 찾고 계십니다.

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

귀하의 질문에 대한 표현은 나에게 흥미로운 아이디어를 생각하게 만들었습니다..스택 프레임의 하위 집합만 저장하고 필요할 때 다시 빌드하여 순수 재귀 함수의 스택 오버플로를 방지합니다.몇 가지 경우에만 정말 유용합니다.알고리즘이 반환이 아닌 컨텍스트에만 조건부로 의존하거나 속도가 아닌 메모리를 최적화하는 경우.

Answer 12

Mathematica는 해시와 함수 호출이 동일한 구문을 사용한다는 사실에 의존하여 메모를 수행하는 특히 매끄러운 방법을 제공합니다.

fib[0] = 1;
fib[1] = 1;
fib[n_] := fib[n] = fib[n-1] + fib[n-2]

그게 다야.fib[0] 및 fib[1]을 즉시 캐시(기억)하고 필요에 따라 나머지를 캐시합니다.패턴 일치 함수 호출에 대한 규칙은 보다 일반적인 정의보다 항상 보다 구체적인 정의를 사용하는 것과 같습니다.

Answer 13

재귀, 부분 함수, 커링, 메모화 등에 대한 C# 프로그래머를 위한 또 하나의 훌륭한 리소스는 Wes Dyer의 블로그이지만 한동안 게시하지 않았습니다.그는 여기에 확실한 코드 예제를 포함하여 메모에 대해 잘 설명합니다.http://blogs.msdn.com/wesdyer/archive/2007/01/26/function-memoization.aspx

Answer 14

이 코드의 문제점은 (대부분의 컴퓨터에서) 15보다 큰 숫자에 대해 스택 오버플로 오류가 발생한다는 것입니다.

정말?어떤 컴퓨터를 사용하고 있나요?44에서 시간이 오래 걸리긴 하지만 스택이 넘치지는 않습니다.실제로 스택이 오버플로되기 전에 정수가 보유할 수 있는 것보다 더 큰 값(~40억 부호 없음, ~20억 부호 있음)을 얻게 됩니다(Fibbonaci(46)).

이것은 당신이 하고 싶은 일에 효과가 있을 것입니다(빠르게 실행됩니다).

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

Answer 15

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) 조회가 보장됩니다.

Answer 16

다른 포스터에서도 알 수 있듯이 메모이제이션 속도를 위해 메모리를 교환하는 표준 방법입니다. 다음은 모든 함수에 대해 메모를 구현하는 의사 코드입니다(함수에 부작용이 없는 경우).

초기 기능 코드:

 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]

Answer 17

그런데 Perl에는 메모하다 지정한 코드의 모든 기능에 대해 이 작업을 수행하는 모듈입니다.

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

Answer 18

@lassevk:

이거 정말 대단하네요. 제가 메모이제이션에 대해 읽은 후 머리 속으로 생각했던 것과 똑같습니다. 고차 펄.제가 생각하기에 유용한 추가 사항 두 가지는 다음과 같습니다.

1. 캐시에 대한 키를 생성하는 데 사용되는 정적 또는 멤버 메서드를 지정하는 선택적 매개 변수입니다.
2. 디스크 또는 데이터베이스 지원 캐시를 사용할 수 있도록 캐시 개체를 변경하는 선택적 방법입니다.

속성을 사용하여 이런 종류의 작업을 수행하는 방법(또는 이러한 종류의 구현으로 가능한지 여부)을 잘 모르겠지만 시도해 볼 계획입니다.

(주제를 벗어:댓글로 게시하려고 했는데 댓글의 허용 길이가 너무 짧아 '답변'에 적합하지 않다는 사실을 깨닫지 못했습니다.)