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.
--
http://mail.python.org/mailman/listinfo/python-list
