How can I preallocate an array of structs in MATLAB? I want to preallocate "a" in this example so that it does not resize several times.
a = []
for i = 1:100
a(i).x = i;
end
Add a comment
|
7 Answers
Using repmat is by far the most efficient way to preallocate structs :
N = 10000;
b = repmat(struct('x',1), N, 1 );
This is ~10x faster using Matlab 2011a than preallocating via indexing, as in
N = 10000;
b(N).x = 1
The indexing method is only marginally faster than not preallocating.
No preallocation: 0.075524
Preallocate Using indexing: 0.063774
Preallocate with repmat: 0.005234
Code below in case you want to verify.
clear;
N = 10000;
%1) GROWING A STRUCT
tic;
for ii=1:N
a(ii).x(1)=1;
end
noPreAll = toc;
%2)PREALLOCATING A STRUCT
tic;
b = repmat( struct( 'x', 1 ), N, 1 );
for ii=1:N
b(ii).x(1)=1;
end;
repmatBased=toc;
%3)Index to preallocate
tic;
c(N).x = 1;
for ii=1:N
c(ii).x(1)=1;
end;
preIndex=toc;
disp(['No preallocation: ' num2str(noPreAll)])
disp(['Preallocate Indexing: ' num2str(preIndex)])
disp(['Preallocate with repmat: ' num2str(repmatBased)])
Results in command window:
No preallocation: 0.075524
Preallocate Indexing: 0.063774
Preallocate with repmat: 0.0052338
>>
P.S. I'd be interested to know why this is true, if anyone can explain it.
6 Comments
Mace
In the question asked, the values of the field
x are growing from 1 to 100. In the answer all instances are 1. How would you accomodate this? I am asking because, I need this :)
Maxweel
There's a mistake in your benchmark: there is no "tic" before initialising c (although it doesn't make much difference in your case as 2 is much faster than 3). However in some versions of Matlab (e.g. 2010) it seems 2) and 3) take the same time, not sure what changed in newer versions.
Ander Biguri
In MATLAB 2017a, repmat is still the fastest.
Camilo Rada
@jerad Look at my answer below for the question you point at the end of your answer.
Camilo Rada
@AnderBiguri And how about the method I show in my answer? My version of matlab is much older.
|
There's a nice discussion about this in Loren on the Art of MATLAB blog.
If I understand you correctly, here's a ways to initialize the struct you want:
a(100).x = 100;
With this method, we can see that elements are filled in with empty arrays.
1 Comment
Hazem
This is by far the most elegant solution I have seen. Since my most concern was about the number of lines of code, I give this answer a +1.
There's a bunch of ways you can initialize a structure. For example, you can use the struct command:
a(1:100) = struct('x',[]);
which sets all fields x to empty.
You can also use deal to create and fill the structure if you know what data should go in there
xx = num2cell(1:100);
[a(1:100).x]=deal(xx{:});
a(99).x
ans =
99
Or you can use struct again (note that if a field of the structure should be a cell array, the cell needs to be enclosed in curly brackets!)
a = struct('x',xx)
Comments
The way this is supposed to be done, and the simplest is
a=struct('x',cell(1,N));
If you fix the missing "tic" and add this method to the benchmarking code presented by jerad, the method I propose above is a bit slower than repmat but much simpler to implement, here is the output:
No preallocation: 0.10137
Preallocate Indexing: 0.07615
Preallocate with repmat: 0.01458
Preallocate with struct: 0.07588
The reason that repmat is faster is because a value to each 'x' field is assigned during the pre-allocation, instead of leaving it empty. If the above pre-allocation technique is changed so we start with all the x fields with a value (one) assigned, like this:
a=cell(1,N);
a(:)={1};
d=struct('x',a);
Then, the benchmarking improves a lot, been very close or some time faster than repmat. The difference is so small that every time I run it it changes which one is faster. Here an output example:
No preallocation: 0.0962
Preallocate Indexing: 0.0745
Preallocate with repmat: 0.0259
Preallocate with struct: 0.0184
Conversely, if the repmat pre-allocation is changed to set the field empty, like this
b = repmat( struct( 'x', {} ), N, 1 );
All the speed advantage is lost
Comments
using cell2struct is by far the fastest method I could figure out. Just check the following code to make a comparison:
clear;
N = 10000;
cel2s=0;
repm=0;
for i=1:100
a=0.0; b=0.0;
tic;
a = cell2struct(cell(1,N), {'x'}, 1 );
cel2s = cel2s + toc;
tic;
b = repmat(struct('x',1), N, 1 );
repm = repm + toc;
end
disp(['cell2struct preallocation: ', num2str(cel2s/100)]);
disp(['repmat preallocation : ', num2str(repm/100)]);
disp(['speedup : ', num2str(fix( repm/cel2s ) ) , ' X']);
Typical results show a mean speedup around 19 times! wrt repmat method:
cell2struct preallocation: 1.4636e-05
repmat preallocation : 0.00028794
speedup : 19 X
2 Comments
Cris Luengo
You cannot time things this short with tic/toc. Use
timeit instead.
Amir Ekrami
@CrisLuengo I made another version using timeit. The speedup is 12X! Not much different from the original one. N = 10000; cel2s = @() cell2struct(cell(1,N), {'x'}, 1 ); repm = @() repmat(struct('x',1), N, 1 ); t1=0.0; t2=0.0; for i=1:100 t1 = t1 + timeit(cel2s); t2 = t2 + timeit(repm); end disp(['cell2struct preallocation: ', num2str(t1/100)]); disp(['repmat preallocation : ', num2str(t2/100)]); disp(['speedup : ', num2str( fix( t2/t1 ) ) , ' X']);
According to this answer, there's also another way to do it:
[a.x] = deal(val);
where val is the value you want to assign to every element of the struct.
The effect of this command is different from those of the others, as every x field of every structure a will be assigned the val value.
Comments
Instead of pre-allocating the array of structs it may be easier to reverse the loop. In this way the array is allocated in the first iteration and the rest of the iterations are used to fill the structs.
a = []
for i = 100:-1:1
a(i).x = i;
end
