Why is there such a huge performance different between the same Python/Java code?

Question

I'm currently trying to work through the Project Euler questions with Python (something I've only picked up today). The question I'm working is question 5, where

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

I have worked through the problems using Java before, so using the same method as I did before, I just created a loop that iterated, however it seems that my code never ends.

Python:

i = 1
while 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:
        print i
        break
    i+=1

Java:

public class p5
{
    public static void main(String[] args)
    {
        for (int i=1;;i++)
        {
            if (i%1==0&&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)
            {
                System.out.println(i);
                break;
            }
        }
    }
}

Java executed that in under 3 seconds on my computer, whereas the Python code never seemed to end. Any tips?

Edit:

Apparently I typed something wrong, which caused it to never end. However, even with the entire thing written correctly (with the same output as my Java), it still took 1 minute and 20 seconds, whereas for Java it took around 1 - 2 seconds. Am I doing anything wrong? Or is Python's performance that bad (which shouldn't be afaik)

As an aside, this is not the algorithm that should be used to solve this problem. — Ignacio Vazquez-Abrams
– Ignacio Vazquez-Abrams, Commented Oct 24, 2012 at 17:57

jfs · Accepted Answer · 2013-04-29 14:18:36Z

4

Arithmetics with primitive ints is much faster in Java then with full integer objects in CPython i.e., the performance difference of 30 times that you see is not surprising for your code.

Note the algorithm is very inefficient and it won't work for a slightly larger input e.g., for numbers from 1 to 50 (It takes too long and the correct result is larger than max int/long in Java).

It takes ~100 micro-seconds to compute the result for all numbers from 1 to 100 on my machine with a more efficient algorithm:

#!/usr/bin/env python
from functools import reduce

def gcd(a, b):
    """Greatest common divisor (factor)."""
    while b: # Euclid's algorithm
        a, b = b, a % b
    return a

def lcm(*args):
    """Least common multiple."""
    # lcm(a, b, c) == lcm(lcm(a, b), c)
    return reduce(lambda a, b: a * b // gcd(a, b), args)

def f(n):
    """Smallest positive number evenly divisible by all numbers from 1
       to n including.
    """
    return lcm(*range(1, n + 1))

print(f(10)) # -> 2520
print(f(50)) # -> 3099044504245996706400

To estimate the performance:

#!/usr/bin/env python
import timeit
from functools import partial

def measure():
    for n in [10, 50, 100]:
        print("%d: %5.2f microseconds" % (n, timeit.timeit(partial(f, n),
                                                           number=1000*1000)))
measure()

edited Apr 29, 2013 at 14:18

answered Oct 24, 2012 at 19:09

jfs

417k210 gold badges1k silver badges1.7k bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

TheAmateurProgrammer Over a year ago

Thanks I do realize that my method isn't the most efficient way of doing things, but my question was more of why python takes around 60+ times longer than Java despite using the same code, but I guess you did sort of answer the question in your first sentence, so I'll mark it as correct

cat_baxter · Accepted Answer · 2012-10-24 15:17:50Z

2

My pure bruteforce solution takes ~250 ms using pypy:

i = 20
while 1:
    if i%20 == 0 and i%19==0 and i%18==0 and i%17==0 and i%16==0 and i%15==0 and i%14==0 and i%13==0 and i%12==0 and i%11==0:
        print i
        break
    i+=20

More elegant should use something like greatest common divisors and least common multiples.

answered Oct 24, 2012 at 15:17

cat_baxter

1392 bronze badges

1 Comment

Tom Johnson Over a year ago

Nope: 4 divides evenly into 2, but not 8, for example. You need the maximum power of each prime between 1 and 20: ie, 19, 17, 16, 13, 11, 9, 7, and 5.

Collectives™ on Stack Overflow

Why is there such a huge performance different between the same Python/Java code?

2 Answers 2

1 Comment

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related