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: cont...@xavierho.com Website: http://xavierho.com/ On Mon, Jul 6, 2009 at 6:09 PM, Dave Angel <da...@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: cont...@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 >
-- http://mail.python.org/mailman/listinfo/python-list
