Why is my code faster with append() in a loop than with a large list?

[Dave Angel]

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: 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).

DaveA