Python code works 20 times slower than Java. Is there a way to speed up Python? -
i wrote program in python , in java search smallest integer solution of equation:
a^5+b^5+c^5+d^5=e^5 (expected output 133^5+110^5+84^5+27^5=144^5)
powers , roots either computed directly ("direct calculation" method) or computed , stored in array ("power lookup" method). fifth powers looked n5 = fifth_power[n]. fifth power root computed using binary search in array 'fifth_power`.
i running on netbeans if matters. takes:
30. s (python, direct) 20. s (python, lookup) 5.6 s (java, direct) 0.8 s (java, lookup) is there way boost python performance? not looking better math (sieving of kind). looking better implementation of "for each combination of a,b,c,d compute of powers, check if sum perfect power. if - print result".
is expected python runs 20 times slower java?
python 3.5
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 b in range(1,a+1): c in range(1,b+1): 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 enough size=176 fifth_power = [none] * size in range(size): fifth_power[i]=long(math.pow(i,5)) millis4 = int(round(time.time() * 1000)) #returns value if perfect power (32 returns 2) #returns -1 if between perfect powers, -2 if greater max value in array, -3 if smaller 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 b in range(1,a+1): c in range(1,b+1): 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:
import java.util.arraylist; public class eu514 { public static void main(string[] args) { bruteforce(); //solution found bruteforce in 5600 ms. prepopulate(); //solution found prepopulation in 761 ms. } public static void bruteforce(){ //java bruteforce long t2 = 0l; long t1 = system.currenttimemillis(); boolean keepsearching = true; int = 0; long e = 0; string solution = ""; while (keepsearching) { a++; (int b = 1; b <= a; b++) { (int c = 1; c <= b; c++) { (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 = + "^5 + " + b + "^5 + " + c + "^5 + " + d + "^5 = " + e + "^5"; keepsearching = false; } } } } } long delta = ((t2-t1)); system.out.println(solution+"\nsolution found 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 = 0; int e = 0; string solution = ""; while (keepsearching) { a++; (int b = 1; b <= a; b++) { (int c = 1; c <= b; c++) { (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 = + "^5 + " + b + "^5 + " + c + "^5 + " + d + "^5 = " + e + "^5"; keepsearching = false; } } } } } long delta = ((t2-t1)); system.out.println(solution+"\nsolution found prepopulation in "+delta+" ms."); } public static long[] populatepowers(int max){ long[] powers = new long[max]; (int = 0; < 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; } }
from array import * import time import numpy np #python, bruteforce : ~30 s millis1 = int(round(time.time() * 1000)) keep_searching = true = 1 result = "" while(keep_searching): += 1 a_pow = ** 5 b in xrange(1, a+1): b_pow = b ** 5 c in xrange(1, b+1): c_pow = c ** 5 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, code optimizations
133^5 + 110^5 + 84^5 + 27^5 = 144.0^5 found solution in 8333 ms
it little different cpu cpu.
Comments
Post a Comment