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

Question

我已经在 J​​ava 和 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

Java:

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

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

因为替换

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整数相反。