为什么这个算法在Python中的运行速度比Java慢20倍？

Question

我已经在Java和Python中实现了一个简单的算法来计算给定斜边长度的所有勾股三元组。出于某种原因，Python实现所需的时间要长约20倍。为什么会这样？你知道吗

$ time python PythagoreanTriples.py
[2800, 9600, 3520, 9360, 5376, 8432, 6000, 8000, 8000, 6000, 8432, 5376, 9360, 3520, 9600, 2800]
python PythagoreanTriples.py  13.92s user 0.71s system 87% cpu 16.698 total

$ time java PythagoreanTriples
[2800, 9600, 3520, 9360, 5376, 8432, 6000, 8000, 8000, 6000, 8432, 5376, 9360, 3520, 9600, 2800]
java PythagoreanTriples  0.32s user 0.12s system 72% cpu 0.618 total

算法是将a和b值按a值的升序和b值的降序添加到输出列表中。下面是Python和Java程序。你知道吗

Python：

def pythagorean_triples(c):
    """

    :param c: the length of the hypotenuse 
    :return: a list containing all possible configurations of the other two
             sides that are of positive integer length. Output each
             configuration as a separate element in a list in the format a b
             where a is in ascending order and b is in descending order in
             respect to the other configurations.
    """

    output = []
    c_squared = c * c
    for a in xrange(1, c):
        a_squared = a * a
        for b in xrange(1, c):
            b_squared = b * b
            if a_squared + b_squared == c_squared:
                output.append(a)
                output.append(b)
    return output

爪哇语：

public static Iterable<Integer> findTriples(int hypotenuse) {
    ArrayList<Integer> output = new ArrayList<Integer>();
    int c_2 = hypotenuse * hypotenuse;
    for(int a = 1; a < hypotenuse; a++) {
        int a_2 = a * a;
        for(int b = 1; b < hypotenuse; b++) {
           int b_2 = b * b;
           if(a_2 + b_2 == c_2) {
               output.add(a);
               output.add(b);
           }
        }
    }
    return output;
}

Answer 1

Python不是为数字运算而生的，但是使用更快的算法可以在几毫秒内解决问题：

def pythagorean_triples(c):
    """

    :param c: the length of the hypotenuse
    :return: a list containing all possible configurations of the other two
             sides that are of positive integer length. Output each
             configuration as a separate element in a list in the format a b
             where a is in ascending order and b is in descending order in
             respect to the other configurations.
    """
    output = []
    c_squared = c * c
    for a in xrange(1, c):
        a_squared = a * a
        b = int(round((c_squared - a_squared) ** 0.5))
        b_squared = b * b
        if a_squared + b_squared == c_squared:
            output.append(a)
            output.append(b)
    return output

Answer 2

似乎大部分时间都花在乘法上了：

因为替换

output = []
c_squared = c * c
for a in xrange(1, c):
    a_squared = a * a
    for b in xrange(1, c):
        b_squared = b * b
        if a_squared + b_squared == c_squared:
            output.append(a)
            output.append(b)
return output

由

all_b_squared = [b*b for b in xrange(1,c)]

output = []
c_squared = c * c
for a in xrange(1, c):
    a_squared = a * a
    for b_squared in all_b_squared:
        if a_squared + b_squared == c_squared:
            output.append(a)
            output.append(math.b)
return output

在我的电脑上显示性能大幅度提高

另请注意（在我的电脑上）

• python3.4比python2.7慢得多
• 使用a**2而不是a*a要慢得多

我建议您vprof和pprofile（pip install vprof）逐行分析您的方法

这可以解释，因为python中的int是一个完整的对象，而不仅仅是ram中的32位变量，它不会溢出，与java整数相反。你知道吗