Có cách nào để tăng tốc độ đệ quy bằng cách nhớ các nút con không?

Question

Ví dụ, Nhìn vào đoạn code cho phép tính số Fibonacci thứ n:

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

Vấn đề với mã này là nó sẽ tạo ra đống lỗi tràn bộ nhớ cho bất kỳ số lớn hơn 15 (trong hầu hết các máy tính) .

Giả sử rằng chúng tôi đang tính toán fib (10). Trong quá trình này, nói fib (5) được tính toán rất nhiều lần. Có cách nào để lưu trữ này trong bộ nhớ để thu hồi nhanh và do đó làm tăng tốc độ đệ quy?

Tôi đang tìm một kỹ thuật chung có thể được sử dụng trong hầu hết mọi vấn đề.

Answer 1

Có cái nhìn sâu sắc của bạn là đúng. Đây được gọi là dynamic programming. Nó thường là một thời gian chạy bộ nhớ chung.

Trong trường hợp của fibo, bạn thậm chí không cần bộ nhớ cache tất cả mọi thứ:

[sửa] Tác giả của câu hỏi dường như được tìm kiếm một phương pháp chung để cache chứ không phải là một phương pháp để tính toán Fibonacci . Tìm kiếm wikipedia hoặc xem mã của người đăng khác để nhận câu trả lời này. Những câu trả lời là tuyến tính trong thời gian và bộ nhớ.

** Đây là một thuật toán O tuyến tính thời gian (n), liên tục trong bộ nhớ **

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

này thực hiện trong thời gian tuyến tính. Nhưng đăng nhập là thực sự có thể !!! Chương trình của Roo cũng tuyến tính, nhưng chậm hơn và sử dụng bộ nhớ.

Đây là thuật toán log O (log (n))

Bây giờ cho các thuật toán log-thời gian (cách cách cách nhanh hơn), đây là một phương pháp: Nếu bạn biết u (n), u (n-1), tính u (n + 1), u (n) có thể được thực hiện bằng cách áp dụng một ma trận:

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

Vì vậy mà bạn có:

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

Đang tính toán theo hàm mũ của các ma trận có độ phức tạp logarit. Chỉ cần thực hiện một cách đệ quy các ý tưởng:

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

Bạn cũng có thể chỉ diagonalize nó (không khó), bạn sẽ tìm thấy số vàng và liên hợp của nó trong eigenvalue của nó, và kết quả sẽ cung cấp cho bạn một công thức toán học chính xác cho u (n). Nó chứa các quyền hạn của các giá trị riêng biệt đó, do đó độ phức tạp sẽ vẫn là logarit.

Fibo thường được lấy làm ví dụ để minh họa Lập trình động, nhưng như bạn thấy, nó không thực sự thích hợp.

@John: Tôi không nghĩ rằng nó có liên quan gì đến việc làm với băm.

@ John2: Bản đồ hơi chung chung bạn nghĩ sao? Đối với trường hợp Fibonacci, tất cả các khóa đều tiếp giáp sao cho một vectơ là thích hợp, một lần nữa có nhiều cách nhanh hơn để tính toán trình tự fibo, xem mẫu mã của tôi ở đó.

Answer 2

Thử sử dụng bản đồ, n là khóa và số Fibonacci tương ứng của nó là giá trị.

@Paul

Cảm ơn thông tin. Tôi không biết điều đó. Từ Wikipedia link bạn đề cập:

Kỹ thuật này tiết kiệm giá trị mà đã được tính toán được gọi là memoization

Vâng tôi đã xem xét mã (+1). :)

Answer 3

Ngôn ngữ này là gì? Nó không tràn bất cứ điều gì trong c ... Ngoài ra, bạn có thể thử tạo bảng tra cứu trên heap hoặc sử dụng bản đồ

Answer 4

bộ nhớ đệm thường là ý tưởng hay cho loại điều này. Vì số lượng mã là hằng số, bạn có thể lưu lại kết quả khi bạn đã tính toán nó. Một c nhanh/example giả

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

Đây sẽ là khá chậm, như mọi kết quả đệ quy trong 3 tra cứu, tuy nhiên điều này nên minh họa cho ý tưởng chung

Answer 5

Điều này được gọi là ghi nhớ và có một bài viết rất hay về việc ghi nhớ Matthew Podwysocki đăng những ngày này. Nó sử dụng Fibonacci để minh họa nó. Và hiển thị mã trong C#. Đọc nó here.

Answer 6

Đây có phải là ví dụ được lựa chọn có chủ ý không? (ví dụ: trường hợp cực đoan mà bạn muốn thử nghiệm)

Vì hiện tại, tôi chỉ muốn đảm bảo bạn đang tìm kiếm câu trả lời về xử lý trường hợp chung của vấn đề này (giá trị lưu vào bộ nhớ cache) , vv) và không chỉ vô tình viết code nghèo: D

Nhìn vào trường hợp cụ thể này, bạn có thể có một cái gì đó dọc theo dòng:

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

nào degenerates để O (n) trong trường hợp xấu nhất: D

[Chỉnh sửa: * không bằng +: D]

[Tuy nhiên, một biên tập: phiên bản Haskell (vì tôi là một masochist hoặc một cái gì đó)

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

]

Answer 7

Nếu bạn đang sử dụng một ngôn ngữ với các chức năng hạng nhất như Scheme, bạn có thể thêm ghi nhớ mà không thay đổi thuật toán ban đầu:

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

Khối đầu tiên cung cấp cơ sở ghi nhớ và khối thứ hai là chuỗi mã số sử dụng cơ sở đó.Điều này bây giờ có một O (n) thời gian chạy (như trái ngược với O (2^n) cho các thuật toán mà không cần ghi nhớ).

Lưu ý: cơ sở ghi nhớ được cung cấp sử dụng chuỗi bao đóng để tìm kiếm các lời gọi trước đó. Trong trường hợp xấu nhất, điều này có thể là O (n). Tuy nhiên, trong trường hợp này, các giá trị mong muốn luôn ở đầu chuỗi, đảm bảo tra cứu O (1).

Answer 8

Vấn đề với mã này là nó sẽ tạo lỗi tràn ngăn xếp cho bất kỳ số nào lớn hơn 15 (trong hầu hết các máy tính).

Thật sao? Bạn đang sử dụng máy tính nào? Nó mất một thời gian dài ở 44, nhưng ngăn xếp không tràn. Trong thực tế, bạn sẽ nhận được một giá trị lớn hơn một số nguyên có thể giữ (~ 4 tỷ unsigned, ~ 2 tỷ ký) trước khi ngăn xếp sẽ đi qua dòng chảy (Fibbonaci (46)).

này sẽ làm việc cho những gì bạn muốn làm dù (chạy wiked nhanh)

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 9

Theo wikipedia fib (0) phải là 0 nhưng nó không quan trọng.

Đây là đơn giản C# giải pháp với chu kỳ:

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

Đó là lừa khá phổ biến để chuyển đổi đệ quy để tail recursion và sau đó lặp. Để biết thêm chi tiết, xem ví dụ: lecture (ppt).

Answer 10

memoization Nhanh chóng và bẩn trong C++:

Bất kỳ phương pháp đệ quy type1 foo(type2 bar) { ... } có thể dễ dàng memoized với 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]; 
} 

EDIT: @ Konrad Rudolph
Konrad chỉ ra rằng std :: bản đồ không phải là cấu trúc dữ liệu nhanh nhất chúng ta có thể sử dụng ở đây. Đó là sự thật, vector<something> phải nhanh hơn map<int, something> (mặc dù nó có thể yêu cầu nhiều bộ nhớ hơn nếu đầu vào cho các cuộc gọi đệ quy của hàm không phải là số nguyên liên tiếp như trong trường hợp này), nhưng bản đồ rất thuận tiện để sử dụng nói chung.

Answer 11

@ESRogs:

std::map tra cứu là O (log n) mà làm cho nó chậm ở đây. Sử dụng vector tốt hơ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 12

Nếu bạn đang sử dụng C#, và có thể sử dụng PostSharp, đây là một khía cạnh memoization đơn giản cho mã của bạn:

[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 
} 

Dưới đây là một việc thực hiện mẫu Fibonacci sử dụng nó:

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

Answer 13

Những người khác đã trả lời câu hỏi của bạn tốt và chính xác - bạn đang tìm kiếm bản ghi nhớ.

Ngôn ngữ lập trình với tail call optimization (chủ yếu là ngôn ngữ chức năng) có thể thực hiện một số trường hợp đệ quy mà không bị tràn ngăn xếp.Nó không trực tiếp áp dụng cho định nghĩa của bạn về Fibonacci, mặc dù có các thủ thuật ..

Câu hỏi của bạn khiến tôi nghĩ về một ý tưởng thú vị .. Tránh tràn ngăn của hàm đệ quy thuần túy bằng cách chỉ lưu trữ một tập con các khung ngăn xếp, và xây dựng lại khi cần thiết .. Chỉ thực sự hữu ích trong một vài trường hợp. Nếu thuật toán của bạn chỉ có điều kiện dựa vào ngữ cảnh trái với sự trở lại, và/hoặc bạn đang tối ưu hóa cho bộ nhớ không tốc độ.

Answer 14

Áp phích khác như đã chỉ ra, memoization là một cách tiêu chuẩn để trao đổi bộ nhớ cho tốc độ, đây là một số mã giả để thực hiện memoization cho bất kỳ chức năng (cung cấp chức năng đã không có tác dụng phụ):

Initial mã chức năng:

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

này nên được chuyển thành

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 15

Bằng cách này Perl có một memoize mô-đun thực hiện điều này cho bất kỳ chức năng nào trong mã của bạn mà bạn chỉ định.

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

Để memoize chức năng này tất cả các bạn làm là bắt đầu chương trình của bạn với

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

Answer 16

Mathematica có một cách đặc biệt trơn để làm memoization, dựa trên thực tế là băm và các cuộc gọi chức năng sử dụng cùng một cú pháp:

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

Vậy đó. Nó lưu trữ (memoizes) fib [0] và fib [1] khỏi bat và lưu trữ phần còn lại khi cần thiết. Các quy tắc cho các cuộc gọi hàm kết hợp mẫu là như vậy mà nó luôn sử dụng một định nghĩa cụ thể hơn trước một định nghĩa tổng quát hơn.

Answer 17

Một nguồn tài nguyên tuyệt vời hơn cho các lập trình viên C# cho đệ quy, chia tay, currying, ghi nhớ, và ilk của họ, là blog của Wes Dyer, mặc dù ông đã không đăng trong một thời gian. Ông giải thích memoization tốt, với mã ví dụ rắn ở đây: http://blogs.msdn.com/wesdyer/archive/2007/01/26/function-memoization.aspx

Answer 18

@lassevk:

Đây là tuyệt vời, chính xác những gì tôi đã suy nghĩ về trong đầu tôi sau khi đọc về memoization trong cao hơn theo thứ tự Perl. Hai điều tôi cho là bổ sung hữu ích:

1. Tham số tùy chọn để chỉ định phương pháp tĩnh hoặc thành viên được sử dụng để tạo khóa cho bộ nhớ cache.
2. Một cách tùy chọn để thay đổi đối tượng bộ nhớ cache để bạn có thể sử dụng bộ đệm cache hoặc cơ sở dữ liệu.

Không chắc chắn làm thế nào để làm điều này với các thuộc tính (hoặc nếu chúng thậm chí có thể với loại triển khai này) nhưng tôi có kế hoạch để thử và tìm ra.

(Tắt chủ đề: Tôi đã cố gắng đăng nhận xét này, nhưng tôi không nhận ra rằng nhận xét có độ dài cho phép ngắn như vậy không thực sự phù hợp như 'câu trả lời')