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

[Xavier Ho]

(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/
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-list/attachments/20090706/853296e4/attachment.html>