Growable data structure in MATLAB

I need to create a queue in matlab that holds structs which are very large. I don't know how large this queue will get. Matlab doesn't have linked lists, and I'm worried that repeated allocation and copying is really going to slow down this code which must开发者_C百科 be run thousands of times. I need some sort of way to use a growable data structure. I've found a couple of entries for linked lists in the matlab help but I can't understand what's going on. Can someone help me with this problem?

I posted a solution a while back to a similar problem. The way I tried it is by allocating the array with an initial size BLOCK_SIZE, and then I keep growing it by BLOCK_SIZE as needed (whenever there's less than 10%*BLOCK_SIZE free slots).

Note that with an adequate block size, performance is comparable to pre-allocating the entire array from the beginning. Please see the other post for a simple benchmark I did.

Just create an array of structs and double the size of the array when it hits the limit. This scales well.

If you're worried that repeated allocation and copying is going to slow the code down, try it. It may in fact be very slow, but you may be pleasantly surprised.

Beware of premature optimization.

Well, I found the easy answer:

L = java.util.LinkedList;

I think the built-in cell structure would be suitable for storing growable structures. I made a comparison among:

• Dynamic size cell, size of the cell changes every loop
• Pre-allocated cell
• Java LinkedList

Code:

clear;
scale = 1000;

% dynamic size cell
tic;
dynamic_cell = cell(0);
for ii = 1:scale
  dynamic_cell{end + 1} = magic(20);
end
toc

% preallocated cell
tic;
fixed_cell = cell(1, scale);
for ii = 1:scale
  fixed_cell{ii} = magic(20);
end
toc

% java linked list
tic;
linked_list = java.util.LinkedList;
for ii = 1:scale
  linked_list.add(magic(20));
end
toc;

Results:

Elapsed time is 0.102684 seconds. % dynamic
Elapsed time is 0.091507 seconds. % pre-allocated
Elapsed time is 0.189757 seconds. % Java LinkedList

I change scale and magic(20) and find the dynamic and pre-allocated versions are very close on speed. Maybe cell only stores pointer-like structures and is efficient on resizing. The Java way is slower. And I find it sometimes unstable (it crashes my MATLAB when the scale is very large).