The stack object implemented here is a partial solution to the problem of dynamic arrays.
It is well known that appending elements to matlab arrays is inefficient (appending an element to a nx1 vector requires at least n assignments), e.g.
tic;v=[];for i=1:1e5,v=[v,i];end;toc; % O(n^2), approx 30 sec
tic;v=zeros(1e5,1); for i=1:numel(v),v(i)=i;end;toc; % O(n), approx 0.004 sec
In some applications we don't know the final length of the array. One solution is the use of stack objects.
A stack is a linked list containing the top item and a pointer to the top of the stack below. Here it is implemented as a nested cell array: s = {} (empty stack) or s = {x,s1} where s1 is a stack.
tic;
s={};
for i=1:1e5
s=push(i,s);
end;
w=stack2mat(s,1e5);
isequal(v,w) % returns 1
toc; % approx 3 sec
The code for push and pop is rather trivial. The functions stack2mat and stack2cell are useful if you need to access elements of the stack other than the last.
NOTE: The reason this is called a "partial" solution to the problem of dynamic arrays:
1. the memory overhead seems to be 120 bytes per stack element (doubles use 8 bytes)
2. large stacks (e.g 1e6 elements) can cause matlab to terminate unexpectedly, which seems to be from a bug in the way matlab handles large nested cell arrays (only tested in R2009a).
|