On Fri, Aug 6, 2010 at 3:00 AM, Dhananjay Nene <dhananjay.n...@gmail.com>wrote:
> On Fri, Jul 23, 2010 at 1:26 PM, Emil Chacko <emilcha...@gmail.com> wrote: > > > Below given is solution to a puzzle( > > http://projecteuler.net/index.php?section=problems&id=14) in python and > c > > > > Python: > > > > import time > > startT=time.time() > > maxlen=0 > > longest=0 > > for i in xrange(1,1000000): > > last=i > > cnt=0 > > while(last <> 1): > > cnt=cnt+1 > > if(last%2==0): > > last=last/2 > > else: > > last=3*last+1 > > if(cnt>maxlen): > > maxlen=cnt > > longest=i > > print "time taken (sec) : ",time.time()-startT > > print maxlen,longest > > > > Python Output: > > time taken (sec) : 99.4702298641 > > 524 837799 > > > > C: > > > > #include <stdio.h> > > int main(int argc, char **argv) > > { > > int longest = 0; > > int maxlen = 0; > > int i; > > unsigned long last; > > for (i = 1; i <= 1000000; i++) > > { > > last = i; > > int cnt = 0; > > while (last != 1) > > { > > cnt++; > > if (last % 2 == 0) > > last = last / 2; > > else > > last = 3 * last + 1; > > } > > if (cnt > maxlen) > > { > > maxlen = cnt; > > longest = i; > > } > > } > > printf("longest: %d (%d)\n", longest, maxlen); > > return 0; > > } > > > > > > My doubt is that in C the result comes in 1-2 sec but in python it takes > 99 > > secs.I don't expect python to be as fast as c but i cant understand why > it > > should be so slow in python.i'm new to python so if there is better way > to > > do the above prog in python please suggest. > > > > Your python code as is clocked about 72 seconds on my notebook. The > following came in at about 4.6 seconds (just has a small trick of reusing > earlier results) > > import time > start =time.time() > longest = None > longest_elements = 0 > solved = {} > for val in xrange(1,1000000) : > counter = 1 > number = val > while number != 1 : > number = number / 2 if number % 2 == 0 else 3 * number + 1 > if number in solved : > counter = counter + solved[number] > break > else : > counter = counter + 1 > if counter > longest_elements : > longest_elements = counter > longest = val > solved[val] = counter > end = time.time() > print "Time:", end - start > print longest, ':', longest_elements > > Dhananjay > Good approach. I remember solving around 50 or so project euler problems a while back in Python and I used caching of previous results in a dictionary for most complex problems which speeded up the calculation tremendously. This technique is often called "memoization". In Python, caching/memoizing decorators can often be used to solve this problem. > > > _______________________________________________ > > BangPypers mailing list > > BangPypers@python.org > > http://mail.python.org/mailman/listinfo/bangpypers > > > > > > -- > -------------------------------------------------------- > blog: http://blog.dhananjaynene.com > twitter: http://twitter.com/dnene > _______________________________________________ > BangPypers mailing list > BangPypers@python.org > http://mail.python.org/mailman/listinfo/bangpypers > -- --Anand _______________________________________________ BangPypers mailing list BangPypers@python.org http://mail.python.org/mailman/listinfo/bangpypers
