[BangPypers] python speed comparison

[Baishampayan Ghose]

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.

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):
    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