[BangPypers] python speed comparison

[Shashwat Anand]

On Fri, Jul 23, 2010 at 1:51 PM, Baishampayan Ghose <b.ghose at 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.ghose at 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 at python.org
> http://mail.python.org/mailman/listinfo/bangpypers
>



-- 
~l0nwlf