Performance difference between loop and recursion in fibonacci sequence
15 Ansichten (letzte 30 Tage)
Ältere Kommentare anzeigen
Süleyman citir
am 18 Sep. 2021
Kommentiert: Süleyman citir
am 18 Sep. 2021
Both codes give the first "n" elements of Fibonacci sequence. Question is, what exactly creates such a performance difference (I added below) between recursion and loop. Besides the answer, you can give a link and I can research.
Recursive code:
function y = fibor_upgraded(n)
if n == 1
y = 1;
elseif n == 2
y = [1 1];
else
y = fibor_upgraded(n-1); % first n-1 elements
y = [y y(end-1)+y(end)]; % store & add
end
end
Loop code:
function y=fibor_loop(n)
y = [1 1];
i=3;
while i <= n
y(i)=y(i-2)+y(i-1);
i=i+1;
end
y=y(1:end);
end
To compare them I used tic-toc and I got this result:
tic; fibor_loop(5e4); toc;
Elapsed time is 0.005314 seconds.
tic; fibor_upgraded(5e4); toc;
Elapsed time is 0.418270 seconds.
2 Kommentare
Akzeptierte Antwort
Jan
am 18 Sep. 2021
Bearbeitet: Jan
am 18 Sep. 2021
A cleaner version of your loop uses a pre-allocation of the output:
function y = fibor_loop_2(n)
y = zeros(1, n); % Pre-allocation
y(1:2) = 1;
for i = 3:n
y(i) = y(i-2) + y(i-1);
end
end
On my computer (i7, R2018b):
% Elapsed time is 0.006649 seconds. your loop
% Elapsed time is 0.920276 seconds. recursive
% Elapsed time is 0.000695 seconds. cleaned loop, 10 times faster
The iterative growing of an array consumes a lot of resources. See thius example:
x = [];
for k = 1:1e6
x(k) = rand;
end
In each iteration a new array is created with the larger size, the old elements are copied and the new element is inserted. Although the final array needs 1e6*8 Bytes = 1MB only (a double needs 8 bytes), Matlab has to allocate and to copy sum(1:1e6)*8 Bytes, which are more than 4 TB!
A pre-allocation avoids this problem:
x = rand(1, 1e6);
for k = 1:1e6
x(k) = rand;
end
This aoolcates the 8MB directly and no further memory is required.
Calling a function has a remarkable overhead. Testing n for each element, if it equal 1 or 2 are 10e4 comparisons for n=5e4. Of course this takes time also.
Weitere Antworten (0)
Siehe auch
Kategorien
Mehr zu Loops and Conditional Statements finden Sie in Help Center und File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!