[BangPypers] python speed comparison

[Anand Balachandran Pillai]

On Fri, Aug 6, 2010 at 3:00 AM, Dhananjay Nene <dhananjay.nene at gmail.com>wrote:

> On Fri, Jul 23, 2010 at 1:26 PM, Emil Chacko <emilchacko at 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 at python.org
> > http://mail.python.org/mailman/listinfo/bangpypers
> >
>
>
>
> --
> --------------------------------------------------------
> blog: http://blog.dhananjaynene.com
> twitter: http://twitter.com/dnene
> _______________________________________________
> BangPypers mailing list
> BangPypers at python.org
> http://mail.python.org/mailman/listinfo/bangpypers
>



-- 
--Anand