Fastest way to fill in an array

133 次查看（过去 30 天）
Martin
Martin 2013-7-24
编辑： Stephen23 2023-10-11
Hi,
I have written the following program, 3 ways to create the same array:
number = 1e5;
tic
A = [];
for i = 1 : number
A = [A i];
end
toc
tic
for i = 1 : number
B(i) = i;
end
toc
tic
C = [];
for i = 1 : number
C(i) = i;
end
toc
Here are the results:
Elapsed time is 11.126158 seconds.
Elapsed time is 0.003447 seconds.
Elapsed time is 0.020941 seconds.
- Why is the first method (A = [A i];) so slow compared to B(i) = i; ??
Why does writing C = []; slow down the computation? (compared to B)
Thanks!

请先登录，再回答此问题。

采纳的回答

David Sanchez
David Sanchez 2013-7-24
The first method is the slowest because even when the matrix is preallocated, its size changes within the loop, what renders the first preallocation useless. The system has to look for increasing room for a growing matrix. The third method is slower than the second because it preallocates the matrix but with no specific size, the problem is similar to the first method but faster because the matrix is not overwritten. The second method gives more freedom to the system to locate the matrix.
  3 个评论
显示 1更早的评论
Martin
Martin 2013-7-24
Thanks for your answer. Ok for the first comparison.
But for the second one I still have trouble understanding. After the first step, the two loops should be the same as the previous initialization C = []; does not have any impact anymore.
But I tried with bigger numbers and the solving times ratio remains the same, e.g. with number = 1e8:
Elapsed time is 0.353962 seconds.
Elapsed time is 2.141597 seconds.
It is as if Matlab drew the conclusion, after reading "C = [];", that C will always be small and that Matlab should rather allocate only a small space, even if C is growing.
I'm intrigued. :)
James Tursa
James Tursa 2013-7-24
编辑：James Tursa 2013-7-24
@Martin: Please read my Answer. You can't take your code literally as written because the MATLAB JIT will change it to something else depending on what patterns it recognized. I strongly suspect that the 2nd example has been rewritten by the JIT as simply
B = 1:number;
Compare the timing of that statement with the timing of your 2nd example to see how similar they are.
I suspect that the 3rd example is the result of the JIT doing the pre-allocation for you, but still doing the loop.

请先登录，再进行评论。

更多回答（2 个）

James Tursa
James Tursa 2013-7-24
编辑：James Tursa 2013-7-24
The results will be highly dependent on MATLAB version used. Since none of the examples explicitly pre-allocate the result, you are at the mercy of the JIT as to what MATLAB will do with the three methods. On paper, all three methods are pretty much equivalent ... they have to reallocate the memory on each iteration to make room for the next entry. The only difference is a slight syntax difference that either the JIT recognizes or it doesn't. If it recognizes the pattern of what you are doing in the loop, it can pre-allocate the result for you and greatly increase performance time. If it can't recognize the pattern, then you are stuck with the very inefficient as-written reallocation at each iteration. The JIT might even be smart enough to simply calculate the result directly and avoid the loop entirely (which might be the difference between method 2 and 3 in your example). E.g., here are the timings from an older version of MATLAB that does not have the JIT smarts that later versions have:
Elapsed time is 11.726275 seconds.
Elapsed time is 12.153010 seconds.
Elapsed time is 12.048716 seconds.
Basically no difference in the timings because none of the methods is recognized by the JIT as something it can pre-allocate or pre-calculate for you.
Bottom line: Best to explicitly pre-allocate like David has shown you rather than rely on the JIT to recognize the pattern in your loop to do the pre-allocation for you. Even if you know a certain pattern is recognized by the JIT of your version, what will happen to the performance if it ever gets ported to another machine with an earlier version of MATLAB? Well, what I have shown above will happen ... lousy performance. So always explicitly pre-allocate.
  4 个评论
显示 2更早的评论
James Tursa
James Tursa 2013-7-25
Another alternative, if you know you will be filling in the data downstream, is this UNINIT function from the FEX:
http://www.mathworks.com/matlabcentral/fileexchange/31362-uninit-create-an-uninitialized-variable-like-zeros-but-faster
It allocates a variable without initializing the data and is very fast.

请先登录，再进行评论。

dan
dan 2023-10-10
Can someone please explain this one then?
tic
Test = zeros(20000);
for i = 1:20000
for j=1:20000
Test(i,j) = i+j;
end
end
toc
tic
Test = zeros(20000);
for i = 1:20000
for j=1:20000
Test(j,i) = i+j;
end
end
toc
Elapsed time is 5.271389 seconds.
Elapsed time is 0.938210 seconds.
  2 个评论

请先登录，再进行评论。

类别

在 Help Center 和 File Exchange 中查找有关 Performance and Memory 的更多信息

标签

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by