Xavier Ho wrote:
(Here's a short version of the long version below if you don't want to
read:)
Why is version B of the code faster than version A? (Only three lines
different)
Version A: http://pastebin.com/f14561243
Version B: http://pastebin.com/f1f657afc
------------------------------------------------
I was doing the problems on Project Euler for practice with Python last
night. Problem 12 was to find the value of the first triangular number that
has over 500 divisors.
=========================================================================================
The sequence of triangle numbers is generated by adding the natural numbers.
So the 7[image: ^(]th[image: )] triangle number would be 1 + 2 + 3 + 4 + 5 +
6 + 7 = 28. The first ten terms would be:
1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...
Let us list the factors of the first seven triangle numbers:
* 1*: 1
* 3*: 1,3
* 6*: 1,2,3,6
*10*: 1,2,5,10
*15*: 1,3,5,15
*21*: 1,3,7,21
*28*: 1,2,4,7,14,28
We can see that 28 is the first triangle number to have over five divisors.
What is the value of the first triangle number to have over five hundred
divisors?
=========================================================================================
My initial code was to loop through from 1 to half the number and see which
were divisors, and as I find them I store them in a list. That would have
taken days.
My second try was factorising the number each time, and count the divisors
using the powers of each factor, plus 1, and multiply together.
The code is here (Version A): http://pastebin.com/f14561243
This worked, but it took overnight to compute. Before I went to bed a friend
of mine caught me online, and apparently left me a working version under 8
seconds with only 3 line difference.
The code is here (Version B): http://pastebin.com/f1f657afc
That was amazing. But I have no idea why his edit makes it so much faster. I
did a test to see whether if append() was faster (which I doubted) than
defining a list with a large size to begin with, and I was right:
http://pastebin.com/f4b46d0db
Which shows that appending is 40x slower, and was expected. But I still
can't puzzle out why his use of appending in Version B was so much faster
than mine.
Any insights would be welcome. I'm going on a family trip, though, so my
replies may delay.
Best regards,
Ching-Yun "Xavier" Ho, Technical Artist
Contact Information
Mobile: (+61) 04 3335 4748
Skype ID: SpaXe85
Email: cont...@xavierho.com
Website: http://xavierho.com/
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.
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).
DaveA
--
http://mail.python.org/mailman/listinfo/python-list
