samedi 12 septembre 2020

Python multi-and statement takes enormously longer than Java multi-and statement

I have the following two programs which search for N where (N%i == 0) for [2<=i<=20].

Java:

//Euler5 ~ Smallest multiple
import java.util.concurrent.TimeUnit;

public class Euler5
{
    public static void main(String[] args) throws InterruptedException
    {
        long startTime = System.nanoTime();
        
        int solution = 0;
        int i = 2520;
        do
        {
            i++;
            if(((i%2)==0)&&
               ((i%3)==0)&&
               ((i%4)==0)&&
               ((i%5)==0)&&
               ((i%6)==0)&&
               ((i%7)==0)&&
               ((i%8)==0)&&
               ((i%9)==0)&&
               ((i%10)==0)&&
               ((i%11)==0)&&
               ((i%12)==0)&&
               ((i%13)==0)&&
               ((i%14)==0)&&
               ((i%15)==0)&&
               ((i%16)==0)&&
               ((i%17)==0)&&
               ((i%18)==0)&&
               ((i%19)==0)&&
               ((i%20)==0))
            {
                break;
            }
        } while(true);
        
        long endTime = System.nanoTime();
        long timeElapsed = endTime - startTime;
        System.out.println("Solution: " + i + "\n");
        System.out.println("Program completed in " + timeElapsed/1000000000 + " seconds.");
    }
}

Which completes in <1s.

Python:

#Euler5 ~ Smallest multiple
import timeit
start = timeit.default_timer()

i = 2520;
while(1):
    i = i + 1
    if i%2 == 0 and \
       i%3 == 0 and \
       i%4 == 0 and \
       i%5 == 0 and \
       i%6 == 0 and \
       i%7 == 0 and \
       i%8 == 0 and \
       i%9 == 0 and \
       i%10 == 0 and \
       i%11 == 0 and \
       i%12 == 0 and \
       i%13 == 0 and \
       i%14 == 0 and \
       i%15 == 0 and \
       i%16 == 0 and \
       i%17 == 0 and \
       i%18 == 0 and \
       i%19 == 0 and \
       i%20 == 0:
        
        break
    
    stop = timeit.default_timer()
    cpu_time = stop - start
    if(cpu_time > 200):
        print("Runtime has exceeded requirement.\n")
        print("Possible solution:",i,"\n")
        print("Program completed in",cpu_time,"seconds.")
        exit()
    
    
#stop = timeit.default_timer()
#print("Solution: ",i,"\n")
#print("Program completed in","{0:.3f}".format(stop - start), "seconds.")

Which completes in 116.948 seconds.

Project Euler has a soft rule that programs find the solution in 60s or less. I cannot think of a way to simplify the Python program other than nesting 20 if-loops, but that seems like it would be more costly not less. And because the Java implementation is so quick it makes me wonder if there is a problem with the way I wrote the loop, such using the \ characters. I'd like to know what is going on under the hood that causes such an enormous gap in runtime.

How can I reduce the runtime of the Python program so it more closely matches the Java program?

Aucun commentaire:

Enregistrer un commentaire