[BangPypers] python speed comparison

[Dhananjay Nene]

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

> _______________________________________________
> BangPypers mailing list
> BangPypers at python.org
> http://mail.python.org/mailman/listinfo/bangpypers
>



-- 
--------------------------------------------------------
blog: http://blog.dhananjaynene.com
twitter: http://twitter.com/dnene