Python在这个算法中比Java慢得多。

Question

我正在学习算法，并决定将教科书中的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中都写过一些编程，但没有意识到这种巨大的差异。

问题归结为：如何克服这个问题？更具体地说：

1. 这段代码是否是一个好的端口，或者我错过了一些微不足道的东西？ 2. 切换到另一个运行时（例如Jython）是否是一个解决方案？是否容易在eclipse中保持我的代码库并添加一个解释器（编译器）？或者切换到另一个解释器/编译器只会使事情稍微好一点？

我现在正在使用Windows 7上的python 2.7.3和Java 1.7 32ibts。

我知道SO上有类似Java/Python性能的问题，但像Python中存在不同的运行时环境这样的答案对我目前没有帮助。

我想知道的是，这些运行时环境中是否有一些可以弥补这个巨大差距的，并且值得探索？

更新：

我安装了pypy，现在差异非常大...

更新2：

我注意到一些非常有趣的事情：这里的islice方法在“常规”Python上更快，但在pypy上要慢得多。即使是这样，pypy仍然比使用常规循环或islices的algoritm快得多。

正如Bakuriu在备注中指出的那样，运行时环境可能非常重要，但对于这个算法更快的运行时环境不一定对于任何算法都更快...

- Peter

---

笑话：Java的开销比Python大得多：慢了2分21秒：慢了1/48倍。 - JB Nizet

你在移植算法时使用了错误的方法 - 使用更Pythonic的方法可能会更快。在这种情况下，您可以使用切片、求和和生成器表达式来替换嵌套的for循环：cnt = sum(1 for x in xrange(0, ln-3) if not sum(a[x:x+3]))。 - l4mpi

@l4mpi，您在评论中编写的代码解决了一个更简单的问题。OP并不是在寻找连续元素。 - Bakuriu

@Peter，“itertools.permutations”应该是相同的算法，除了结果的顺序。 - millimoose

需要注意的是，PyPy只在某些算法上运行得更快。例如，如果你正在处理长整数算术，CPython会更快。无论如何，你应该从这个基准测试中得出的结论是JIT能够显著提高性能，而不是说CPython通常很慢。你可以尝试在CPython上使用 psycho 运行你的算法，你可能会看到类似于PyPy的结果。（不幸的是它已经不再维护了）。 - Bakuriu

Answer 1

尝试使用PyPy而不是CPython来运行它。很可能会更快。

- Ned Batchelder

Answer 2

我用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）。这种方法非常擅长猜测所使用的变量类型，因此您可以获得性能提升。

- sul4bh

---

+1：虽然不算是一个答案，但我喜欢那些无需编写的基准测试。 - Peter

试图将一些计算机科学的东西放入透彻的视角中 :D 顺便说一下，数组的大小为1000。 - sul4bh

“因此，PHP和Python解释器花费了很多时间猜测所使用的变量类型，因此运行非常缓慢”- 这是明显错误和误导性的。Python不会猜测任何东西的类型，每个对象都有已知的类型。虽然确实由于缺乏编译时类型信息（或跟踪JIT）而导致了一部分开销，这阻止了CPython获得静态类型语言通常具有的性能水平，但它在任何地方都没有“猜测类型”。事实上，PyPy之所以更快，是因为它对变量类型做出了有根据的猜测！ - millimoose

-1: "......但我喜欢不必编写的基准测试" 另一方面，其他人无法重现的基准测试结果（因为除了作者以外没有人拥有源代码）是毫无价值的。 - Stephen C

-1：这是彻头彻尾的胡说八道。类型无法被猜测，因为数据没有固有的类型，它都是一样的。如果Python不知道变量的类型，它怎么会抛出TypeError呢？PHP和Python是解释型语言，这就是它们缓慢的原因。大多数静态类型语言都是编译型的，但这只是巧合。例如，Common Lisp就是编译型和动态类型的。 - Joonazan

Answer 3

正如您在起始帖子的评论中所说，除了使用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

- user2070336

---

你自己进行过基准测试吗？在我的情况下，速度要慢得多（在pypy中：对于一个包含2K个元素的数组，需要50秒而不是4秒）。 - Peter

我使用Python 2.7.3（无Pypy）进行了基准测试，与islice和小于2000的测试列表相比，用时为1.4秒，而islice用时为1.1秒。 - user2070336

我用普通的Python得到了2秒和1秒的结果，但是使用pypy却只需要0.1秒和0.5秒，慢了5倍，很奇怪：在pypy中，这种方法比普通的方法要慢得多，但仍然比普通Python中最快的方法要快。 - Peter

Answer 4

对于Python，可以使用标准库中的itertools组合函数，它会将for循环转移到C语言层面。

- MATTIA NERONI