Thanks for the response all, I finally got my 'net working on the mountains, and I think your reasons are quite sound. I'll keep that in mind for the future.<br><br>Best regards,<br><br clear="all">Ching-Yun "Xavier" Ho, Technical Artist<br>
<br>Contact Information<br>Mobile: (+61) 04 3335 4748<br>Skype ID: SpaXe85<br>Email: <a href="mailto:contact@xavierho.com">contact@xavierho.com</a><br>Website: <a href="http://xavierho.com/">http://xavierho.com/</a><br>
<br><br><div class="gmail_quote">On Mon, Jul 6, 2009 at 6:09 PM, Dave Angel <span dir="ltr"><<a href="mailto:davea@dejaviewphoto.com">davea@dejaviewphoto.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
Xavier Ho wrote:<br>
<blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;"><div class="im">
(Here's a short version of the long version below if you don't want to<br>
read:)<br>
<br>
Why is version B of the code faster than version A? (Only three lines<br>
different)<br>
<br>
Version A: <a href="http://pastebin.com/f14561243" target="_blank">http://pastebin.com/f14561243</a><br>
Version B: <a href="http://pastebin.com/f1f657afc" target="_blank">http://pastebin.com/f1f657afc</a><br>
<br>
------------------------------------------------<br>
<br>
I was doing the problems on Project Euler for practice with Python last<br>
night. Problem 12 was to find the value of the first triangular number that<br>
has over 500 divisors.<br>
=========================================================================================<br>
<br>
The sequence of triangle numbers is generated by adding the natural numbers.<br></div>
So the 7[image: ^(]th[image: )] triangle number would be 1 + 2 + 3 + 4 + 5 +<div><div></div><div class="h5"><br>
6 + 7 = 28. The first ten terms would be:<br>
<br>
1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...<br>
<br>
Let us list the factors of the first seven triangle numbers:<br>
<br>
* 1*: 1<br>
* 3*: 1,3<br>
* 6*: 1,2,3,6<br>
*10*: 1,2,5,10<br>
*15*: 1,3,5,15<br>
*21*: 1,3,7,21<br>
*28*: 1,2,4,7,14,28<br>
<br>
We can see that 28 is the first triangle number to have over five divisors.<br>
<br>
What is the value of the first triangle number to have over five hundred<br>
divisors?<br>
=========================================================================================<br>
<br>
My initial code was to loop through from 1 to half the number and see which<br>
were divisors, and as I find them I store them in a list. That would have<br>
taken days.<br>
<br>
My second try was factorising the number each time, and count the divisors<br>
using the powers of each factor, plus 1, and multiply together.<br>
The code is here (Version A): <a href="http://pastebin.com/f14561243" target="_blank">http://pastebin.com/f14561243</a><br>
<br>
This worked, but it took overnight to compute. Before I went to bed a friend<br>
of mine caught me online, and apparently left me a working version under 8<br>
seconds with only 3 line difference.<br>
The code is here (Version B): <a href="http://pastebin.com/f1f657afc" target="_blank">http://pastebin.com/f1f657afc</a><br>
<br>
That was amazing. But I have no idea why his edit makes it so much faster. I<br>
did a test to see whether if append() was faster (which I doubted) than<br>
defining a list with a large size to begin with, and I was right:<br>
<a href="http://pastebin.com/f4b46d0db" target="_blank">http://pastebin.com/f4b46d0db</a><br>
Which shows that appending is 40x slower, and was expected. But I still<br>
can't puzzle out why his use of appending in Version B was so much faster<br>
than mine.<br>
<br>
Any insights would be welcome. I'm going on a family trip, though, so my<br>
replies may delay.<br>
<br>
Best regards,<br>
<br>
Ching-Yun "Xavier" Ho, Technical Artist<br>
<br>
Contact Information<br>
Mobile: (+61) 04 3335 4748<br>
Skype ID: SpaXe85<br>
Email: <a href="mailto:contact@xavierho.com" target="_blank">contact@xavierho.com</a><br>
Website: <a href="http://xavierho.com/" target="_blank">http://xavierho.com/</a><br>
<br>
<br>
</div></div></blockquote>
Just by inspection, it would seem the bottleneck in your first version is that you return a huge list of nearly all zeroes, from factorize(). This slows down countDivisors() a great deal.<br>
<br>
It would probably save some time to not bother storing the zeroes in the list at all. And it should help if you were to step through a list of primes, rather than trying every possible int. Or at least constrain yourself to odd numbers (after the initial case of 2).<br>
<br>
DaveA<br>
</blockquote></div><br>