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

[Xavier Ho]

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
future.

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/


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