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

Question

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

我用两种语言解决了Project Euler问题5,虽然我在两种语言中的实现看起来与我的眼睛非常相似,但运行时却大不相同.Java只需几秒钟即可返回答案,而Python最多可能需要一分钟(当然,在同一台机器上).我很确定这不是Python的错,更不是程序员(我)的错,他们还没有学会用Python来学习.

请注意,我不是要求您重写我的代码.我只是在朝着正确的方向寻找一些推动力.(是的,我看过一些 类似的 线程,但大多数都是我的头脑,并没有直接比较两种语言中的相同算法.这个线程很有用,但同样,不直接比较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;
    }
}

蟒蛇

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,确保它是兼容的数字类型等等.这都需要时间,特别是当你'做了几十万次.

替代Python实现(如PyPy)会努力尝试确定变量的类型.在您的情况下,它可以确定number并x始终引用整数,并生成不必检查类型的适当的低级代码.

最后,您可能希望查找最小公倍数,以便以任何语言更快地解决Project Euler问题.与Project Euler问题一样,最快的解决方案不是通过编写更快的代码,而是通过选择合适的算法.

Answer 2

我不确定这有多大帮助，但是你的工作代码可以用更Pythonic的方式重写，如下所示：

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

如果您愿意，可以进一步优化它（例如，如果您已经测试过一个数字能否被 20 整除，则无需检查它是否能被 10、5 或 2 整除）。