Fastest way to fill in an array
조회 수: 85 (최근 30일)
이전 댓글 표시
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!
댓글 수: 0
채택된 답변
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
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
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
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:
It allocates a variable without initializing the data and is very fast.
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
Stephen23
2023년 10월 10일
편집: Stephen23
2023년 10월 11일
"Can someone please explain this one then?"
This topic has been discussed fairly regularly:
As far as I understand, the cause is due to the processor reading a whole block of data into its memory cache, which is then very fast to access (faster even than the main memory).
참고 항목
카테고리
Help Center 및 File Exchange에서 Logical에 대해 자세히 알아보기
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!