java - 为什么相同的 Python/Java 代码之间会有如此巨大的性能差异？

Question

我目前正在尝试使用 Python 解决 Project Euler 问题(这是我今天才学会的)。我正在处理的问题是问题 5，其中

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?

我以前使用 Java 解决过这些问题，所以使用与以前相同的方法，我只是创建了一个迭代的循环，但是我的代码似乎永远不会结束。

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 在我的电脑上执行了不到 3 秒，而 Python 代码似乎永远不会结束。有什么建议吗？

编辑:

显然我输入错误，导致它永远不会结束。然而，即使所有内容都正确编写(输出与我的 Java 相同)，它仍然需要 1 分 20 秒，而对于 Java，它大约需要 1 - 2 秒。我做错了什么吗？或者是 Python 的性能那么差(这不应该是 afaik)

Answer 1

在 Java 中使用原始 int 的算法比在 CPython 中使用完整的整数对象要快得多，即您看到的 30 倍的性能差异对于您的代码来说并不奇怪。

请注意，该算法非常低效，它不适用于稍大的输入，例如 1 到 50 的数字(它花费的时间太长，正确的结果比 Java 中的 max int/long 大)。

在我的机器上使用更高效的算法计算从 1 到 100 的所有数字的结果需要 ~100 微 秒:

#!/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()