Python code works 20 times slower than Java. Is there a way to speed up Python?

Question

I wrote a program in Python and in Java to search for the smallest integer solution of the equation:

a^5+b^5+c^5+d^5=e^5 (expected output is 133^5+110^5+84^5+27^5=144^5)

Powers and roots are either computed directly ("direct calculation" method) or computed and stored in an array ("power lookup" method). Fifth powers are looked up like n5 = fifth_power[n]. Fifth power root is computed using a binary search in array 'fifth_power`.

I am running it on NetBeans if it matters. It takes:

30. s (Python, direct)
20. s (Python, lookup)
5.6 s (Java, direct)
0.8 s (Java, lookup)

Is there a way to boost Python performance? I am not looking for better math (sieving of some kind). I am looking for better implementation of "for each combination of a,b,c,d compute some of their powers, check if the sum is a perfect power. If it is - print the result".

Is it expected that Python runs some 20 times slower than Java?

Python 3.5

http://pastebin.com/qVthWGKm

from array import *
import math
import time

#PYTHON, BRUTEFORCE : ~30 s
millis1 = int(round(time.time() * 1000))
keep_searching = True
a=1
result=""
while(keep_searching):
    a+=1
    for b in range(1,a+1):
        for c in range(1,b+1):
            for d in range(1,c+1):
                sum=math.pow(a,5)+math.pow(b,5)+math.pow(c,5)+math.pow(d,5)
                root = math.pow(sum,0.2)
                e = round(root)


                e5 = math.pow(e,5)              

                if(e5==sum):
                    result="{}^5 + {}^5 + {}^5 + {}^5 = {}^5".format(int(a),int(b), int(c),int(d), int(e))
                    keep_searching = False
                    millis2 = int(round(time.time() * 1000))

print(result)
print("Found solution in {} ms".format(millis2-millis1))

#PYTHON, PRECOMPUTE POWERS: ~20 s
millis3 = int(round(time.time() * 1000))  
#fifth_power #175 is enough
size=176
fifth_power = [None] * size
for i in range(size):
    fifth_power[i]=long(math.pow(i,5))

millis4 = int(round(time.time() * 1000))  

#returns  value if it is a perfect power (32 returns 2)  
#returns -1 if between perfect powers, -2 if greater than max value in array, -3 if smaller than min value in array

def check_perfect_power(number, min, max, fifth_power):


    current=int((min+max)/2)
    while(max>=min):
        if(number==fifth_power[current]):
            return current
        elif(number>fifth_power[current]):
            min=current+1
            current=int((max+min)/2)
        else:
            max=current-1
            current=int((max+min)/2)

    if(min>=len(fifth_power)):        
        return -2
    if(max<0):
        return -3

    return -1  

keep_searching = True
a=0
result=""
while(keep_searching):
    a+=1
    for b in range(1,a+1):
        for c in range(1,b+1):
            for d in range(1,c+1):
                mymax=min(int(a*1.32)+1, size-1)
                e=check_perfect_power(fifth_power[a]+fifth_power[b]+fifth_power[c]+fifth_power[d], a, mymax, fifth_power)
                if(e>0):
                    result="{}^5 + {}^5 + {}^5 + {}^5 = {}^5".format(int(a),int(b), int(c),int(d), int(e))
                    keep_searching = False
                    millis5 = int(round(time.time() * 1000))

print(result)

    print("Populated in {} ms, find solution in {} ms".format(millis4-millis3,millis5-millis4))

Java 8:

http://pastebin.com/G4V3fHnD

import java.util.ArrayList;

public class Eu514 {
    public static void main(String[] args) {

       bruteforce();  //Solution found by bruteforce in 5600 ms.
       prepopulate(); //Solution found by prepopulation in 761 ms.
    }    

    public static void bruteforce(){ //JAVA BRUTEFORCE        
        Long t2 = 0L;
        Long t1 = System.currentTimeMillis();    
        boolean keepSearching = true;
        int a = 0;
        long e = 0;
        String solution = "";

        while (keepSearching) {
            a++;
            for (int b = 1; b <= a; b++) {
                for (int c = 1; c <= b; c++) {
                    for (int d = 1; d <= c; d++) {
                        long sum = (long) (Math.pow(a, 5) + Math.pow(b, 5) + Math.pow(c, 5) + Math.pow(d, 5)); //sum=a^5+b^5+c^5+d^5

                        e = Math.round(Math.pow(sum, 0.2)); //e= sum^(1/5), rounded
                        long e5 = (long) Math.pow(e,5);    //e^5

                        if(e5==sum){
                            t2 = System.currentTimeMillis();
                            solution = a + "^5 + " + b + "^5 + " + c + "^5 + " + d + "^5 = " + e + "^5";
                            keepSearching = false;
                        }
                    }
                }
            }
        }
        long delta = ((t2-t1));
        System.out.println(solution+"\nSolution found by bruteforce in "+delta+" ms.");    
    }

    public static void prepopulate(){  //JAVA PREPOPULATE
        Long t2 = 0L;
        Long t1 = System.currentTimeMillis();

        int size = 176;
        long[] powers = populatePowers(size);

        boolean keepSearching = true;
        int a = 0;
        int e = 0;
        String solution = "";

        while (keepSearching) {
            a++;
            for (int b = 1; b <= a; b++) {
                for (int c = 1; c <= b; c++) {
                    for (int d = 1; d <= c; d++) {
                        long sum = powers[a] + powers[b] + powers[c] + powers[d];
                        int max = (int) Math.min(size - 1, (a * 1.32 + 1));
                        e = checkIfPerfectPower(sum, a, max, powers);
                        if (e > 0) {
                            t2 = System.currentTimeMillis();
                            solution = a + "^5 + " + b + "^5 + " + c + "^5 + " + d + "^5 = " + e + "^5";
                            keepSearching = false;
                        }
                    }
                }
            }
        }
        long delta = ((t2-t1));
        System.out.println(solution+"\nSolution found by prepopulation in "+delta+" ms.");
    }

    public static long[] populatePowers(int max){
        long[] powers = new long[max];
        for (int i = 0; i < powers.length; i++) {
            powers[i]=(long) Math.pow(i,5);
        }        
        return powers;
    }

    public static int checkIfPerfectPower(long number, int min, int max, long[] arr){
        int current =((min+max)/2);
        while(max>=min){
            if(number==arr[current]){
                return current;
            }else if(number>arr[current]){
                min = current + 1;
                current = (max + min) / 2;                
            }else{
                max=current-1;
                current=(max+min)/2;
            }
        }
        if(min>=arr.length) return -2;
        if(max<0) return -3;
        return -1;              
    }  

}

You could start by replace every instance of math.pow(x,y) with x**y. — Robᵩ
– Robᵩ, Commented Sep 12, 2016 at 22:03
That's actually a much better showing on Python's side than I expected, considering CPython has no JIT and dynamic lookup for almost everything. — user2357112
– user2357112, Commented Sep 12, 2016 at 22:12
And delete the binary lookup, build a set() instead to check for e's membership in fifth_powers. — Robᵩ
– Robᵩ, Commented Sep 12, 2016 at 22:13
You're also computing the powers in the innermost loop, when things like math.pow(a,5) won't change, so moving those to just inside their respective loops offers an easy step to improve matters. (saves about 10s for me) — Simon Fraser
– Simon Fraser, Commented Sep 12, 2016 at 22:14

Stanley Kirdey · Accepted Answer · 2016-09-12 22:49:09Z

from array import *
import time
import numpy as np

#PYTHON, BRUTEFORCE : ~30 s
millis1 = int(round(time.time() * 1000))
keep_searching = True
a = 1
result = ""
while(keep_searching):
    a += 1
    a_pow = a ** 5
    for b in xrange(1, a+1):
        b_pow = b ** 5
        for c in xrange(1, b+1):
            c_pow = c ** 5
            for d in xrange(1, c+1):
                d_pow = d ** 5
                sum_pow = a_pow + b_pow + c_pow + d_pow
                root = sum_pow ** 0.2
                e = round(root)


                e5 = e ** 5             

                if(e5 == sum_pow):
                    result="{}^5 + {}^5 + {}^5 + {}^5 = {}^5".format(a, b, c, d, e)
                    keep_searching = False
                    millis2 = int(round(time.time() * 1000))

print(result)
print("Found solution in {} ms".format(millis2-millis1))

Python 2.7, with some code optimizations

133^5 + 110^5 + 84^5 + 27^5 = 144.0^5 Found solution in 8333 ms

It could be a little different from CPU to CPU.

Antonín Lejsek · Accepted Answer · 2016-09-13 00:26:34Z

1

What about improving the java code?

int size = 200;
long[] pow5 = new long[size];

for (int i = 1; i < size; ++i)
{
    long sqr = i * i;
    pow5[i] = sqr * sqr * i;
}

for (int a = 1; a < size; ++a)
{
    for (int b = 1; b <= a; ++b)
    {
        for (int c = 1; c <= b; ++c)
        {
            int e = a + 1;
            for (int d = 1; d <= c; ++d)
            {
                long sum = pow5[a] + pow5[b] + pow5[c] + pow5[d];
                while(pow5[e] < sum){ e++; }
                if (pow5[e] == sum)
                {
                    System.out.println(a + "^5 + " + b + "^5 + " + c + "^5 + " + d + "^5 = " + e + "^5");
                    return;
                }
            }
        }
    }
}

answered Sep 13, 2016 at 0:26

Antonín Lejsek

6,1132 gold badges18 silver badges18 bronze badges

Collectives™ on Stack Overflow

Python code works 20 times slower than Java. Is there a way to speed up Python?

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related