Memoizing chức năng fibonacci trong php

Question

tôi đã tạo ra một hàm memoized của phiên bản đệ quy của fibonacci. Tôi sử dụng điều này làm ví dụ cho các loại chức năng khác có thể sử dụng tính năng ghi nhớ. thực hiện của tôi là xấu vì nếu tôi đưa nó vào trong thư viện, đó có nghĩa là biến global vẫn thấy ..

Đây là đệ quy ban chức năng fibonacci:

function fibonacci($n) { 
    if($n > 1) { 
    return fibonacci($n-1) + fibonacci($n-2); 
    } 
    return $n; 
} 

và tôi sửa đổi nó vào một phiên bản được ghi nhớ:

$memo = array(); 
function fibonacciMemo($n) { 
    global $memo; 
    if(array_key_exists($n, $memo)) { 
    return $memo[$n]; 
    } 
    else { 
    if($n > 1) { 
     $result = fibonacciMemo($n-1) + fibonacciMemo($n-2); 
     $memo[$n] = $result; 
     return $result; 
    } 
    return $n; 
    } 
} 

Tôi cố tình không sử dụng phương pháp lặp lại khi triển khai mã fibonacci. Có cách nào tốt hơn để ghi nhớ hàm fibonacci trong php? Bạn có thể đề xuất tôi cải tiến tốt hơn không? Tôi đã nhìn thấy func_get_args() và call_user_func_array như một cách khác nhưng tôi dường như không thể biết những gì là tốt hơn?

Vì vậy, câu hỏi chính của tôi là: Làm thế nào tôi có thể memoize chức năng fibonacci trong php đúng cách? hoặc cách tốt nhất trong memoizing chức năng fibonacci trong php là gì?

Answer 1

Vâng, Edd Mann cho thấy một cách tuyệt vời để thực hiện một chức năng memoize trong php trong His post

Đây là đoạn mã ví dụ (trên thực tế được lấy từ bài Edd Mann):

$memoize = function($func) 
{ 
    return function() use ($func) 
    { 
     static $cache = []; 

     $args = func_get_args(); 

     $key = md5(serialize($args)); 

     if (! isset($cache[$key])) { 
      $cache[$key] = call_user_func_array($func, $args); 
     } 

     return $cache[$key]; 
    }; 
}; 

$fibonacci = $memoize(function($n) use (&$fibonacci) 
{ 
    return ($n < 2) ? $n : $fibonacci($n - 1) + $fibonacci($n - 2); 
}); 

Chú ý rằng global định nghĩa nó được thay thế nhờ chức năng clousure và hỗ trợ chức năng lớp học đầu tiên của PHP.

giải pháp khác:

Bạn có thể tạo một class chứa các thành viên như tĩnh: fibonnacciMemo và $memo. Lưu ý rằng bạn không còn phải sử dụng $memo làm biến toàn cục, vì vậy nó sẽ không gây ra xung đột với các không gian tên khác. Dưới đây là ví dụ:

class Fib{ 
    //$memo and fibonacciMemo are static members 
    static $memo = array(); 
    static function fibonacciMemo($n) { 
     if(array_key_exists($n, static::$memo)) { 
     return static::$memo[$n]; 
     } 
     else { 
     if($n > 1) { 
      $result = static::fibonacciMemo($n-1) + static::fibonacciMemo($n-2); 
      static::$memo[$n] = $result; 
      return $result; 
     } 
     return $n; 
     } 
    } 
} 

//Using the same method by Edd Mann to benchmark 
//the results 

$start = microtime(true); 
Fib::fibonacciMemo(10); 
echo sprintf("%f\n", microtime(true) - $start); 
//outputs 0.000249 

$start = microtime(true); 
Fib::fibonacciMemo(10); 
echo sprintf("%f\n", microtime(true) - $start); 
//outputs 0.000016 (now with memoized fibonacci) 

//Cleaning $memo 
Fib::$memo = array(); 
$start = microtime(true); 
Fib::fibonacciMemo(10); 
echo sprintf("%f\n", microtime(true) - $start); 
//outputs 0.000203 (after 'cleaning' $memo) 

Sử dụng này, bạn tránh được việc sử dụng các global và cũng là vấn đề của làm sạch bộ nhớ cache. Mặc dù điều, $memo không phải là chủ đề tiết kiệm và các phím được lưu trữ không giá trị băm. Anyways, bạn có thể sử dụng tất cả các Utilites php memoize như memoize-php

Answer 2

tôi nghĩ rằng ... này nên để cho memoize một fibonacci:

function fib($n, &$computed = array(0,1)) { 
    if (!array_key_exists($n,$computed)) { 
     $computed[$n] = fib($n-1, $computed) + fib($n-2, $computed); 
    } 
    return $computed[$n]; 
} 

một số thử nghiệm

$arr = array(0,1); 
$start = microtime(true); 
fib(10,$arr); 
echo sprintf("%f\n", microtime(true) - $start); 
//0.000068 

$start = microtime(true); 
fib(10,$arr); 
echo sprintf("%f\n", microtime(true) - $start); 
//0.000005 

//Cleaning $arr 
$arr = array(0,1); 
$start = microtime(true); 
fib(10,$arr); 
echo sprintf("%f\n", microtime(true) - $start); 
//0.000039