7

Before anyone starts in, I know that talking about "speed" in a programming language isn't always the most... useful discussion. That said, speed is the issue here.

I tackled Project Euler problem 5 in both languages and, while my implementations in both languages look fairly similar to my eye, the runtime is vastly different. Java returns an answer in only a few seconds whereas Python can take up to a minute (on the same machine, of course). I'm quite certain this is less the fault of Python and more the fault of a programmer (me) who hasn't quite learned to think Pythonically.

Note that I am not asking you to rewrite my code. I'm simply looking for a few nudges in the right direction. (And yes, I've looked at some similar threads but most of those are over my head and aren't directly comparing the same algorithm in two languages. This thread is helpful, but again, doesn't directly compare Java and Python - and frankly the answers are a little hard to follow.)

Without further ado:

Java

public class Problem5 {

    public static void main(String[] args){
        boolean found = false;

        for (int i = 20; !found; i += 20){
            if (DivisThrough20(i)) {
                found = true;
                System.out.println(i);
            }
        }
    }

    private static boolean DivisThrough20(int number){
        boolean result = true;
        for (int i = 19; result && i > 1; i--){
            if (number % i != 0) result = false;
        }
        return result;
    }
}

Python

def DivisThroughTwenty(number):
    for x in range(20,1,-1):
        if number % x != 0:
            return False
    return True

# the number we're looking for can't be any lower than 20, so we'll
# start there as a small optimization
testNumber = 20

keepLooking = True

while keepLooking:
    if not DivisThroughTwenty(testNumber):
        testNumber += 20
    else:
        keepLooking = False

print testNumber

It's funny, reading these side by side I can already see that the Python version of this algorithm is slightly more optimized than the Java version, yet it's still much slower. I'm even more curious to find another way to approach the problem now.

Community
  • 1
  • 1
Zelbinian
  • 3,221
  • 5
  • 20
  • 23
  • I doubt it's a mistake. Python is interpreted, ergo slower. – Chris Eberle Feb 07 '12 at 05:36
  • 4
    @Chris: Python is *compiled* to a virtual machine representation, just like Java is. However, Python is dynamically typed and Java is statically typed. – Greg Hewgill Feb 07 '12 at 05:42
  • This is a perfect example of why micro optimizing while you're using a brute force algorithm is a stupid idea: 5 minutes thinking can avoid hours of benchmarking and trial&error AND result in much faster code. Although I'm somewhat shocked by all the other threads which also don't mention the obvious solution of just computing the lcm by prime factorization or something (in which case the difference between python and java is unmeasurable on my pc) – Voo Feb 07 '12 at 15:54
  • 5
    @Voo That's a fairly elitist and unhelpful comment. Thanks for assuming I didn't spend time thinking about the problem beforehand. Do you really think I knew of a better solution and just didn't use it? The hallmark of a beginner is not knowing what you don't know. On top of that, your comment is a nonsequitor. I'm not interested in a faster algorithm, I'm interested in why the same algorithm has such different runtimes in the two different languages. – Zelbinian Feb 07 '12 at 18:09
  • @Zelbinian It is important to know that the advantages of optimizations such as the ones Java does and Python doesn't go away when you choose the right algorithm. Seeking the right algorithm is Pythonic; hand-optimizing the wrong algorithm is not. – Apalala Feb 12 '12 at 21:04

2 Answers2

7

Python is a dynamically typed language, while Java is a statically typed language. This means that Java has more readily available information at compile time about what types your variables are, in particular numbers. Java's designers spent quite a bit of effort defining the JVM in such a way that 32-bit (int) and 64-bit arithmetic (long) calculations can work in an efficient manner.

Python, on the other hand, does not have variable type declarations so the variables such as x can hold any object at all. In your case, it happens that they always hold numbers, but CPython's compiler doesn't go to the effort of verifying that. When Python executes your code, evaluating an expression such as number % x involves looking up the % operator for the object represented by number, calling the % operator, getting the type of x, making sure it is a compatible number type, etc. This all takes time, particularly when you're doing it zillions of times.

Alternate Python implementations such as PyPy go to great effort to try to nail down the types of your variables. In your case, it could determine that number and x always refer to integers, and generate appropriate low-level code that doesn't have to check types.

Finally, you might want to look up the Least common multiple for a faster way to solve this Project Euler problem, in any language. As is common with Project Euler problems, the fastest solution is found not by writing faster code, but by choosing an appropriate algorithm.

Greg Hewgill
  • 951,095
  • 183
  • 1,149
  • 1,285
  • 1
    I appreciate the insight. It doesn't help me learn how to write the second part of the code in a more "Pythonic" way, though, so that's why I chose the other answer. – Zelbinian Feb 07 '12 at 14:32
  • 1
    @Zelbinian: How does the performance of wim's implementation compare to yours? On my machine, it takes 27 seconds while yours takes 18. Smaller, more "pythonic" code doesn't necessarily mean *faster* code. – Greg Hewgill Feb 07 '12 at 18:05
  • Truth. Though learning how to make my Python code "Pythonic" is also a goal here. – Zelbinian Feb 07 '12 at 18:13
  • @GregHewgill Your timings are interesting - do you have any comment on why this is so? I assumed the generator expression and `any` would short circuit the same way as the OP's `return` does. Although I removed a double-negation in the logic, this shouldn't change timings. So where does the slowness come in?? – wim Feb 07 '12 at 23:49
  • @wim: I expect it's the number of callbacks invoked by the generator expression inside `any(...)`. The explicit loop in the OP's question avoids a generator expression call for every iteration. – Greg Hewgill Feb 07 '12 at 23:53
2

I'm not sure how much this might help, but your worker code can be rewritten in a much more pythonic way like so:

def divis_through_twenty(n):
  return any(n % x for x in xrange(20,1,-1))

x = 20
while divis_through_twenty(x):
  x += 20

print x

You can optimise it a bit more if you like (e.g., if you already tested a number was divisible by 20, you don't need to check if it's divisible by 10, 5, or 2).

wim
  • 338,267
  • 99
  • 616
  • 750
  • Thanks - this is the exact kind of thing I need. Let me ruminate a bit on the differences between your code and mine - I'm sure I'll have more questions! – Zelbinian Feb 07 '12 at 14:33
  • You're welcome, fire away. It has also just occurred to me that, since you are incrementing test number in multiples of 20, you don't even need to check divisibility of 20 (and 10, 5, 2). but this is somewhat off-topic .. as others have already mentioned a smarter algorithm would be the best optimisation (hint: lcm & gcd) – wim Feb 07 '12 at 23:50