Python在这个算法上比Java慢很多

7 投票

4 回答

2157 浏览

提问于 2025-04-17 16:10

我正在学习算法，决定把教科书里的Java程序转成Python，因为我不喜欢Java的那些繁琐的东西，尤其是对于小程序来说，这也是一种练习。

这个算法其实很简单，它只是从一个数组中找出所有的三元组，然后用暴力的方法计算有多少个三元组的和为零（比如：[-2,7,-5]）。

 public static int count(int[] a) {
        int N = a.length;
        int cnt = 0;
        for (int i = 0; i < N; i++) {
            for (int j = i+1; j < N; j++) {
                for (int k = j+1; k < N; k++) {
                    if (a[i] + a[j] + a[k] == 0) {
                        cnt++;
                    }
                }
            }
        }
        return cnt;
    }

我把它转成了：

def count(a):
    cnt = 0
    ln = len(a)
    for i in xrange(0,ln): 
        for j in xrange(i + 1,ln):
            for k in xrange(j + 1,ln): 
                if a[i] + a[j] + a[k] == 0:
                    cnt+=1
    return cnt

现在只测量这些函数的时间：

java :   array of 2000 elements --> 3 seconds 
python : array of 2000 elements --> 2 minutes, 19 seconds

UPDATE 
python (pypy) : array of 2000 elements --> 4 seconds ( :-) )

当然，这个算法并不好，它只是用来展示这一点，无论是在这里还是在教科书中。我之前在Java和Python中都写过一些程序，但没意识到它们之间有这么大的差别。

问题归结起来就是：如何克服这个问题？更具体地说：

这个代码转得好吗，还是我漏掉了什么简单的东西？
换一个运行环境，比如Jython，是解决办法吗？在Eclipse里保持我的代码库只加一个解释器（编译器）容易吗？还是说换一个解释器/编译器只会稍微改善一下？

现在我在Windows 7上使用的是Python 2.7.3和Java 1.7 32位。

我知道在Stack Overflow上有类似关于Java/Python性能的问题，但那里的回答，比如说Python有不同的运行环境，对我现在并没有帮助。

我想知道这些运行环境是否能缩小这个巨大的差距，值得去探索吗？

更新：

我安装了pypy，现在的差别非常大……

更新2：

我注意到一些很有趣的事情：这里一个回答中的islice方法在“普通”Python上更快，但在pypy上却慢得多。即便如此，pypy在这个算法中无论是使用普通循环还是islice，速度仍然快很多。

正如Bakuriu在评论中提到的，运行环境可能非常重要，但对于这个算法来说更快的运行环境不一定对所有算法都更快……

4 个回答

正如你在帖子评论中看到的，想要让这个过程变得更快其实没有什么好办法（除了使用PyPy）。你可以试试islice，它会直接遍历"a"，而不是创建新的列表或范围，这样应该会稍微快一点。

from itertools import islice

def count(a):
    cnt = 0
    for x, i in enumerate(islice(a,0, None)): 
        for y, j in enumerate(islice(a, x + 1, None)):
            for k in islice(a, y + x + 2, None):
                if i + j + k == 0:
                   cnt+=1
    return cnt

回答于 2025-04-17 由 Python大师

分享举报

我在C和PHP中实现了这个功能。以下是结果：

PHP: 23.977946043015秒
Python: 19.31秒

C: 0.4秒
Java: 0.42秒

我们在比较不同类型系统的编程语言。PHP和Python是动态类型的，而C和Java是静态类型的。

这意味着，PHP和Python的解释器需要花很多时间来猜测变量的类型，所以运行起来比较慢。而在C和Java中，变量的类型（比如整数）是固定的，这样就省去了猜测的时间。显然，这个猜测的时间非常高，从上面的数字可以看出来。

使用PyPY时，猜测的时间大大减少，因为PyPY采用了即时编译（JIT）技术。这种方法非常擅长猜测变量的类型，因此你会看到性能的提升。

回答于 2025-04-17 由 Python大师

分享举报

试着用PyPy来运行它，而不是用CPython。这样做很可能会快很多。

回答于 2025-04-17 由 Python大师

分享举报

Python在这个算法上比Java慢很多

4 个回答

撰写回答