The growing data structure in MATLAB

Question

I need to create a queue in matlab that contains structures that are very large. I don’t know how big this line will be. Matlab has no linked lists, and I am concerned that redistributing and copying really slows down this code, which has to run thousands of times. I need some way to use a growing data structure. I found several entries for linked lists in Matlab help, but I cannot figure out what is going on. Can someone help me with this problem?

Answer 1

Well, I found an easy answer:

L = java.util.LinkedList; 

Answer 2

I posted a solution some time ago to a similar problem. The way I tried this is to allocate an array with an initial size of BLOCK_SIZE , and then increase it by BLOCK_SIZE as necessary (if there are less than 10%*BLOCK_SIZE free slots).

Note that with a sufficient block size, performance is comparable to preallocating the entire array from the start. Please see another post for a simple test that I did.

Answer 3

Just create an array of structures and double the size of the array when it reaches the limit. It scales well.

Answer 4

If you are concerned that redistributing and copying is slowing your code down, give it a try. It can be very slow, but you may be pleasantly surprised.

Beware of premature optimization.

Answer 5

I think an inline cell structure would be suitable for storing growing structures. I made a comparison between:

• Dynamic cell size, cell size changes every cycle
• Pre-selected cell
• Java LinkedList

the 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 that dynamic and pre-selected versions are very close in speed. Perhaps the cell only stores pointer structures and is effective at resizing. The Java path is slower. And I find it sometimes unstable (it breaks my MATLAB when the scale is very large).