Why are my nested loops taking so long to compute?
I have a code that generates all possible combinations of 4 integers from 0 to 36.
This will be 37 ^ 4 digits = 1874161.
My code is written in MATLAB:
i=0;
for a = 0:36
for b= 0:36
for c = 0:36
for d = 0:36
i=i+1;
combination(i,:) = [a,b,c,d];
end
end
end
end
I tested this using a number 3
instead of a number 36
and it worked fine.
If there are 1,874,161 combinations, and with An overly cautionary about guessing 100 clock ticks to make additions and write values, then if I have a 2.3GHz PC it is:
1874161 * (1/2300000000) * 100 = 0.08148526086
Fraction of a second. But he has been working for about half an hour so far.
I got a warning stating that combination changes size every loop iteration, consider predefining its size for speed
, but it can't affect it, if possible?
source to share
As @horchler suggested you to preallocate the target array
This is because your program is not O(N^4)
without prior use. Every time you add a new line to the array, it needs to be changed, so a new larger array is created (since Matlab doesn't know how big an array it will only grow by 1 element) and then the old array will be copied into it and finally , the old array has been deleted. So when you have 10 elements in the array and adding the 11th number, then copying 10 elements is added per iteration ... if I'm not mistaken, resulting in something like O(N^12)
that is massively larger
- assessed as
(N^4)*(1+2+3+...+N^4)=((N^4)^3)/2
In addition, the reallocation process grows in size, breaking through the CACHE barriers, slowing down further as the i
size of CACHE increases above each barrier.
The only solution for this without prior use is to store the result in a linked list
Not sure if Matlab has this parameter, but it will take one / two pointers for each element (32-bit value bytes), which makes your array 2+
times larger.
If you need even more speed, there are ways (maybe not for Matlab):
- using multithreading to populate an array is fully parallelizable
- use block copy (
rep movsd
) or DMA, data is repeated periodically. - You might also consider calculating the value from i in a run rather than memorizing the entire array, depending on the use it might be faster in some cases ...
source to share