Very symple code with bad performance

This is the place for queries that don't fit in any of the other categories.

Very symple code with bad performance

Postby ja0335 » Sun Jun 15, 2014 11:37 pm

Hi..

I'm new with Python and i want to know if is there any way to improve the time execution of this simple code:
Code: Select all
import math

def IsPrime(x):
   
    if x == 1:
        return False
    elif x == 2 or x == 3 or x == 5:
        return True
    elif x % 2 == 0 or x % 3 == 0 or x % 5 == 0:
        return False
       
    top = int(math.ceil(math.sqrt(x)))

    for i in range(7, top+1, 30):
       
        if x%i == 0 or x%(i+2) == 0 or x%(i+4) == 0 or x%(i+6) == 0 or x%(i+10) == 0 or x%(i+12) == 0 or x%(i+16) == 0 or x%(i+22) == 0 or x%(i+24) == 0:
            return False

    return True

print IsPrime(9007199254740881)


when i run it, it takes at least 6 seconds to return me the result, i've coded the same task in other languages like Javascript and it takes less than 1 second
Code: Select all
<script>
   
function IsPrime(x)
{
  if (x == 1)
      return false;
  else if( x == 2 || x == 3 || x == 5)
      return true;
  else if( x % 2 == 0 || x % 3 == 0 || x % 5 == 0)
      return false;
 
  top = Math.ceil(Math.sqrt(x));
 
  for(i=7; i < top+1; i+=30)
  {
      if( x%i == 0 || x%(i+2) == 0 || x%(i+4) == 0 || x%(i+6) == 0 || x%(i+10) == 0 || x%(i+12) == 0 || x%(i+16) == 0 || x%(i+22) == 0 || x%(i+24) == 0)
          return false;
  }
 
  return true;
}
 
window.alert( IsPrime(9007199254740881) );

</script>


As i'm new i don't know if i'm loosing something.

Tanks in advance
Last edited by ja0335 on Tue Jun 17, 2014 10:53 pm, edited 1 time in total.
ja0335
 
Posts: 2
Joined: Sun Jun 15, 2014 11:32 pm

Re: Very symple code with bad performance

Postby micseydel » Mon Jun 16, 2014 3:47 am

I can't tell for sure, but I'm thinking the Javascript engine you're using might have some JIT aspect. This takes 0.6 seconds for me with Pypy, although it takes like 2.6s with regular Python 2. Just 2.4s swapping out range() for xrange().
Join the #python-forum IRC channel on irc.freenode.net!

Please do not PM members regarding questions which are meant to be discussed publicly. The point of the forum is so that others can benefit from it. We don't want to help you over PMs or emails.
User avatar
micseydel
 
Posts: 1355
Joined: Tue Feb 12, 2013 2:18 am
Location: Mountain View, CA

Re: Very symple code with bad performance

Postby metulburr » Mon Jun 16, 2014 5:17 am

Your exact code takes around 2 seconds for me as is.
Code: Select all
metulburr@ubuntu ~ $ time python test.py
True

real   0m1.825s
user   0m1.790s
sys   0m0.034s
metulburr@ubuntu ~ $ time python3 test.py
True

real   0m2.870s
user   0m2.861s
sys   0m0.006s


Your exact code wrapped in a c library executed by python runs at about .02 seconds

test.c
Code: Select all
#include <math.h>
#include <stdbool.h>

bool IsPrime(unsigned long int x)
{
  if (x == 1)
      return false;
  else if( x == 2 || x == 3 || x == 5)
      return true;
  else if( x % 2 == 0 || x % 3 == 0 || x % 5 == 0)
      return false;
 
  unsigned long int top = ceil(sqrt(x));
 
  for(unsigned int i=7; i < top+1; i+=30)
  {
      if( x%i == 0 || x%(i+2) == 0 || x%(i+4) == 0 || x%(i+6) == 0 || x%(i+10) == 0 || x%(i+12) == 0 || x%(i+16) == 0 || x%(i+22) == 0 || x%(i+24) == 0)
          return false;
  }
 
  return true;
}


wrapper.py
Code: Select all
import ctypes
import os

path = os.path.dirname(os.path.abspath(__file__))
fullpath = os.path.join(path, 'lib.so')

ctypes.cdll.LoadLibrary(fullpath)
lib = ctypes.CDLL(fullpath)
lib.IsPrime(9007199254740881)


Code: Select all
metulburr@ubuntu ~  $ gcc -std=c99 -shared -o lib.so -fPIC test.c
metulburr@ubuntu ~  $ time python wrapper.py

real   0m0.020s
user   0m0.015s
sys   0m0.006s
metulburr@ubuntu ~ $ time python3 wrapper.py

real   0m0.049s
user   0m0.022s
sys   0m0.006s
New Users, Read This
OS Ubuntu 14.04, Arch Linux, Gentoo, Windows 7/8
https://github.com/metulburr
steam
User avatar
metulburr
 
Posts: 1470
Joined: Thu Feb 07, 2013 4:47 pm
Location: Elmira, NY

Re: Very symple code with bad performance

Postby casevh » Mon Jun 16, 2014 6:24 am

Here is a slightly faster version of your program. The running time dropped from 2.3s to 1.6s on my computer.

Code: Select all
import math

def IsPrime(x):

    if x == 1:
        return False

    for p in (2, 3, 5, 7, 11, 13, 17, 19, 23, 29):
        if x == p:
            return True
        if not x % p:
            return False
       
    top = int(math.ceil(math.sqrt(x)))

    for d in (1, 7, 11, 13, 17, 19, 23, 29):
        for i in xrange(30 + d, top+1, 30):
            if not x % i:
                return False

    return True

print IsPrime(9007199254740881)


If your goal is to run the algorithm in both languages, I can think of any obvious improvements. If you just want to check if a number is prime, there are faster ways.

casevh
casevh
 
Posts: 70
Joined: Sat Feb 09, 2013 7:35 am

Re: Very symple code with bad performance

Postby ja0335 » Tue Jun 17, 2014 10:52 pm

2 seconds?

I'm running the code in a AMD A8 Processor, 6GB of Memory with Windows 8, and it takes 12 seconds... May be Windows 8 the problem?
ja0335
 
Posts: 2
Joined: Sun Jun 15, 2014 11:32 pm

Re: Very symple code with bad performance

Postby casevh » Wed Jun 18, 2014 3:17 am

I rebooted into Windows 8.1 and timed the code I posted previously. The execution time varied significantly depending on the version of Python and whether or not a 32-bit or 64-bit version of Python was used. The slowest time was reported by 32-bit Python 2.6 at ~10 seconds. The best time was reported by 64-bit Python 3.3 at ~4.5 seconds. The running time on Linux for 64-bit Python 2.7 was 1.6 seconds. The best time I could achieve using Python 3.x on Linux was ~2.8 seconds.

Why the differences?

The program spends much of its time calculating with small integers. Python 2.x has two integer types: "int" is optimized for small integers and "long' supports arbitrary precision integers. Since Python 2.x transparently converts between the two integer types, the differences rarely appear (usually just an "L" at the end of a long). Python 3.x only support arbitrary precision integers and operations are slower on the arbitrary precision integers. The threshold where "int" is promoted to "long" depends on the operating system and the version of Python used.

This particular benchmark accidentally highlights one of the differences between various versions (both operating system and Python releases) of the Python interpreter.

Historical note

In early versions of Python, "int" did not automatically overflow to "long". The OverflowError exception was all too common. IIRC, the automatic conversion to long was introduced in Python 2.2.

casevh
casevh
 
Posts: 70
Joined: Sat Feb 09, 2013 7:35 am


Return to General Coding Help

Who is online

Users browsing this forum: No registered users and 3 guests