How to make recursion faster in Matlab (Matlab seems to forget steps already done)?
9 次查看(过去 30 天)
显示 更早的评论
I have defined a recursive function successfully in Matlab.
function result = f(a,i,j)
subl = a(i:j);
n=length(subl);
first=subl(1);
last=subl(end);
if (i==j)
result = a(i);
else
result = max(first*(2*n-1)+f(a,i+1,j), last*(2*n-1)+f(a,i,j-1));
end
However, if I run the function for long enough array a. Say
a = [5 0 2 3 0 2 2 8 1 1 0 1 2 3 4 1 0 1 8 0 1 1 2 3 4]
The recursion gets really slow. This is because Matlab tends to calculate all the steps in the recursion again and again without remembering the between the steps. In Mathematica this can be easily changed by changing the recursive function a bit but I haven't found a way to do this in Matlab. Indeed, in Mathematica the same functions runs extremely fast.
Is there a way to do this easily?
7 个评论
Stephen23
2020-9-10
Perhaps this might help (no idea how it works with recursive functions):
Fangjun Jiang
2020-9-10
@Stephen Cobeldick, indeed, it can be improved.
>> tic;b=f1(a,1,20);toc
Elapsed time is 0.043371 seconds.
>> fh=@f1
fh =
function_handle with value:
@f1
>> memoizedFcn = memoize(fh)
memoizedFcn =
MemoizedFunction with properties:
Function: @f1
Enabled: 1
CacheSize: 10
>> tic;b=memoizedFcn(a,1,20);toc
Elapsed time is 0.053710 seconds.
>> tic;b=memoizedFcn(a,1,20);toc
Elapsed time is 0.001782 seconds.
回答(2 个)
Fangjun Jiang
2020-9-10
编辑:Fangjun Jiang
2020-9-10
The code can be simplified first.
I see the potential saving. f(a,1,20) depends on f(a,2,20) and f(a,1,19), which depends on f(a,3,20), f(a,2,19), f(a,2,19), f(a,1,18). Here, f(a,2,19) is probabaly calculated twice. Might be able to save it.
function result = f1(a,i,j)
n=j-i+1;
if (i==j)
result = a(i);
else
result = max(a(i)*(2*n-1)+f1(a,i+1,j), a(j)*(2*n-1)+f1(a,i,j-1));
end
>> a=ones(1,20);
>> tic;b=f(a,1,20);toc
Elapsed time is 0.310610 seconds.
>> tic;b=f1(a,1,20);toc
Elapsed time is 0.045661 seconds.
Fangjun Jiang
2020-9-10
编辑:Fangjun Jiang
2020-9-10
You might not need to use recursive function to get the solution. Instead, just calculate the result as a nxn matrix, but, it needs to be in a particular order.
For a=ones(1,20), i=1, j=20, Initially, R=nan(20)
first, calculate R(1,1),R(2,2), ..., R(20,20)
second, calculate R(1,2), R(2,3), R(3,4), ... R(19,20)
third, calculate R(1,3), R(2,4), R(3,5),...
function result = f2(a,i,j)
n=j-i+1;
result=nan(n);
for k=i:j
result(k,k)=a(k);
end
for increase=1:j-i
for k=i:j-increase
result(k,k+increase)=max(a(k)*(2*increase+1)+result(k+1,k+increase), a(k+increase)*(2*increase+1)+result(k,k+increase-1));
end
end
end
2 个评论
Fangjun Jiang
2020-9-10
I think at issue is the fact that your recursive function called the function TWICE in one recursion. In next recursion, the function will be called 4 times and so on. I don't have knowledge why Mathematica is smarter about this. I am glad I understood the question and figured out ways to get a solution.
另请参阅
类别
在 Help Center 和 File Exchange 中查找有关 Loops and Conditional Statements 的更多信息
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!