6

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 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?

rlbond
  • 65,341
  • 56
  • 178
  • 228

5 Answers5

6

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.

Community
  • 1
  • 1
Amro
  • 123,847
  • 25
  • 243
  • 454
3

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

Pyrolistical
  • 27,624
  • 21
  • 81
  • 106
  • How are structs implemented? Does moving the array just mean copying pointers? – rlbond Apr 12 '10 at 22:17
  • As far as I know everything in Matlab is data. So struct is just data. And you don't "move the array". Just double the size of the existing array. `x(2*length(x)) = ...your 'empty' struct` – Pyrolistical Apr 12 '10 at 22:34
  • @rlbond: Yes, MATLAB structs and cells do not contain data itself but pointers to the data so all operations are cheap. – Mikhail Poda Apr 13 '10 at 09:51
2

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.

David
  • 7,011
  • 1
  • 42
  • 38
  • 5
    @rlbond: That is sad indeed. If you want to get to know it, go to the 'Desktop' menu of Matlab, and open the profiler. – Jonas Apr 13 '10 at 14:12
2

Well, I found the easy answer:

L = java.util.LinkedList;
rlbond
  • 65,341
  • 56
  • 178
  • 228
1

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).

Edward Shi
  • 51
  • 1
  • 3