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