Why is my code faster with append() in a loop than with a large list?
contact at xavierho.com
Mon Jul 6 08:12:58 EDT 2009
Thanks for the response all, I finally got my 'net working on the mountains,
and I think your reasons are quite sound. I'll keep that in mind for the
Ching-Yun "Xavier" Ho, Technical Artist
Mobile: (+61) 04 3335 4748
Skype ID: SpaXe85
Email: contact at xavierho.com
On Mon, Jul 6, 2009 at 6:09 PM, Dave Angel <davea at dejaviewphoto.com> wrote:
> 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
>> has over 500 divisors.
>> The sequence of triangle numbers is generated by adding the natural
>> 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
>> 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
>> 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
>> 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.
>> 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).
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Python-list