我的雲端生活網 - Life+

Friday, September 7, 2007

pure function

A pure function:

Has no side effects

Return value depends only on arguments

Example:

sub factorial {
my $n = shift;
$n == 0 ? 1 : $n * factorial($n-1);
}

cache 只對pure function 有意義;這可以思考,查詢一個檔案的修改時間的這種function,他並非一個pure function,所以;對非pure function做cache 是沒有意義的,這裡有一個例子:

Highly Recursive Functions
sub fib {
my ($n) = @_;
return $n if $n ==0 || $n == 1;
return fib($n-2) + fib($n-1);
}

This function is very very slow!

Caching Fixes Recursion
Solution: Caching

@fib = (0, 1);
sub fib {
my ($n) = @_;
return $fib[$n] if defined $fib[$n];
return $fib[$n] = fib($n-1) + fib($n-2);
}

fib(20) computes fib(18) and fib(19)

fib(19) goes to compute fib(18)

But it is already in $fib[18]

Function is now very fast,Almost as fast as a pure iterative version,
Unlike the iterative version, this version required no ingenuity


以上文章節錄自 http://perl.plover.com/yak/hw-dcpm/

No comments:

Blog Archive