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

[MRAB]

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^(^th ) 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.
> 
In your version you're creating a list of (num + 1) elements, but in the
other version the list is only as long as the largest factor.

For example, for num=28, your version creates a list 29 elements long,
but the other version creates one only 7 elements long. Also, 'the time
needed to append an item to the list is "amortized constant"' (quoted
from http://effbot.org/zone/python-list.htm).

This means that your little speed test isn't representation of what's
actually happening.