MATLAB Answers

Loop is killing proccesor.

1 ビュー (過去 30 日間)
Scragmore
Scragmore 2011 年 10 月 29 日
I am running the code below where I am trying to create a matrix for all the products of x digit numbers. Works fine for 1 and 2 digit numbers but three kills it. I have taken the semi colon off of 'z' and also 'x' in the first if statement so I can watch the output. For the first hundred loops (999 to 900) it is fast then gets progressively slower. The same number of tasks are being done each loop, so where my problem must be in loading the answers onto the end of my matrix 'NumLine'. Is this my problem?
function palout =paladin(numDig)
%NumLine = ((10^(numDig-1)^2):((10^numDig)-1)^2);
xMax = 10^numDig-1; %Upper bound
x = xMax;
y = x;
z = 10^(numDig-1) %Lowwer bound
NumLine = [];
while x >= z
NumLine(end+1) = x*y;
if y == z
x = x-1
y = xMax;
else
y = y-1;
end
end
palout = NumLine;

採用された回答

bym
bym 2011 年 10 月 29 日
yes, you need to pre-allocate NumLine
  1 件のコメント
Scragmore
Scragmore 2011 年 10 月 29 日
Thanks, just clarified by asking the oracle google. I belive I understand. I declared the variable/matrix but did not allocate memory for this to be stored. So as it gets exponentially bigger it has to re allocate memory and move the matrix into it. thus the huge performance hit.
Before I close this thread could you briefly explain the consideration for the size I pre-allocate. Should it be the size of the matrix I am expecting to build or in large enough blocks it step-wise increases (does it do this) sufficiently not to hit performance too much.
Regarding pre-allocation size I briefly noticed comments on an old programming theme about the the gluttony of size of modern PC's and the over reliance on allocating large memory blocks, though I am not expecting an answer on this point. How should I consider this issue in my case.
Regards,
AD

サインインしてコメントする。

その他の回答 (1 件)

bym
bym 2011 年 10 月 29 日
I was going to comment but I thought my reply might be better an answer. You can preallocate as long as you know apriori what the size you are expecting. If you don't know the size, the allocate in 'reasonable' chunks.
I take it from your code, you are trying to solve Project Euler #4 which ask for the largest palindrome for a product of two 3 digit numbers. So without preallocation generate the first chunk of data by using
a = (999:-1:900)'*(999:-1:900);
which gives you the first 10,000 products of two 3 digit numbers. You can search through these for the largest palindrome.
If you want to continue using loops, just allocate numbers in (100 x 100) blocks till you achieve your result. I think you will find you do not have to go beyond the range I have shown above
  1 件のコメント
Scragmore
Scragmore 2011 年 10 月 30 日
Thanks for the clarification and good catch on Q? No.4. Following your previous answer I had already decided to drop this approach not only because of the huge data set I was likely to produce but also the redundancy within the set. My follow up q? was more for personnel clarification on what I was doing wrong and not to do in the future rather than implementation.
I have concluded that brute force is about the only approach, so am looking for the most efficient and quickest way to do it with the tool I have (matlab). To quote 'when you have 124kBit encryption, use a spanner'.
Thanks again.
AD

サインインしてコメントする。

タグ

Community Treasure Hunt

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

Start Hunting!

Translated by