On Fri, Jul 23, 2010 at 1:51 PM, Baishampayan Ghose <b.gh...@gmail.com>wrote:
> Emil, > > > 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. > def seq(n): kount = 1 while n != 1: if not n % 2: n /= 2 else: n = 3*n + 1 kount += 1 return kount sol, soln = 1, 1 for i in range(1,1000000): if sol < seq(i): sol, soln = seq(i), i print soln ### Takes 36 sec 14:23:33 l0nwlf-MBP:~/Codes/PE$ time python 14.py 837799 real 0m36.311s user 0m36.073s sys 0m0.091s > > Python is undoubtedly slower than C, more so when you use a naive > algorithm. Here is how I had solved this problem in Python on Jan, > 2007 (had to really dig out the code from my archives) - > > #!/usr/bin/env python > > # Solution for problem #14 at Project Euler > # (http://projecteuler.net/index.php?section=problems&id=14) > # Author: Baishampayan Ghose <b.gh...@gnu.org> > > length = 0 > max = 0 > start = 1 > > def cycle(x): > ''' Calculate the max cycle length, > ensuring that everything is < 1 million > ''' > i = 1 > > while (x != 1): > if (x % 2 == 0): > x = x / 2 > else: > x = 3*x + 1 > i += 1 > > return i > > for i in xrange(800000, 840000): > So did you applied some maths here ? :-/ > length = cycle(i) > if length > max: > max = length > start = i > > print start > > ### > > The above code gets the result in 1.7 seconds on my machine (the C > version takes 0.8 secs). The trick here was to calculate the range > properly, which you can arrive at by using some math. > > Note that brute force approaches rarely work with project Euler > problems. There is most certainly some math involved somewhere which > can simplify your solution a lot. > > Hope this helps. > > Regards, > BG > > -- > Baishampayan Ghose > b.ghose at gmail.com > _______________________________________________ > BangPypers mailing list > BangPypers@python.org > http://mail.python.org/mailman/listinfo/bangpypers > -- ~l0nwlf _______________________________________________ BangPypers mailing list BangPypers@python.org http://mail.python.org/mailman/listinfo/bangpypers
