java - 如何使这个 Project Euler 解决方案在 Python 中以与 Java 相同的速度执行？

Question

在任何人开始之前，我知道在编程语言中谈论“速度”并不总是最……有用的讨论。也就是说，速度是这里的问题。

我解决了 Project Euler problem 5在这两种语言中，虽然我在这两种语言中的实现看起来非常相似，但运行时却大不相同。 Java 仅需几秒钟即可返回答案，而 Python 最多可能需要一分钟(当然，在同一台机器上)。我很确定这不是 Python 的错，而是一个还没有完全学会用 Python 方式思考的程序员(我)的错。

请注意，我并不是要您重写我的代码。我只是想在正确的方向上寻找一些插入力。 (是的，我看过 some similar threads，但其中大部分都在我的脑海中，并没有直接比较两种语言的相同算法。This thread 很有帮助，但同样，没有不要直接比较 Java 和 Python - 坦率地说，答案有点难以理解。)

事不宜迟:

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

有趣的是，并排阅读这些内容我已经可以看出该算法的 Python 版本比 Java 版本稍微优化了一些，但速度仍然慢得多。我现在更好奇地想找到另一种方法来解决这个问题。

Answer 1

Python 是一种动态类型的语言，而 Java 是一种静态类型的语言。这意味着 Java 在编译时有更容易获得的关于变量类型的信息，特别是数字。 Java 的设计者花费了大量的精力来定义 JVM，使得 32 位(int)和 64 位算术(long)计算可以高效地工作方式。

另一方面，Python 没有变量类型声明，因此 x 等变量可以容纳任何对象。在你的情况下，碰巧它们总是保存数字，但 CPython 的编译器不会去验证它。当 Python 执行您的代码时，评估诸如 number % x 的表达式涉及为 number 表示的对象查找 % 运算符，调用% 运算符，获取 x 的类型，确保它是一个兼容的数字类型，等等。这一切都需要时间，尤其是当你做无数次的时候。

PyPy 等替代 Python 实现会竭尽全力尝试确定变量的类型。在您的情况下，它可以确定 number 和 x 始终引用 integers，并生成不需要的适当的低级代码检查类型。

最后，您可能想要查找 Least common multiple以更快的方式用任何语言解决这个 Project Euler 问题。与欧拉计划问题一样，最快的解决方案不是通过编写更快的代码找到的，而是通过选择合适的算法找到的。