Why is my code faster with append() in a loop than with a large list?
davea at dejaviewphoto.com
Mon Jul 6 06:09:46 EDT 2009
Xavier Ho wrote:
> (Here's a short version of the long version below if you don't want to
> Why is version B of the code faster than version A? (Only three lines
> 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
> 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:
> 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: contact at 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).
More information about the Python-list