7

我正在研究算法并决定将 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。

我知道关于 java/python 性能的 SO 上存在类似的问题，但是目前诸如 python 有不同的运行时环境之类的答案对我没有帮助。

我想知道的是，其中一些运行时是否可以缩小这个巨大的差距并且值得探索？

更新 ：

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

更新 2：

我注意到一些非常有趣的事情：答案中的 islice 方法在“常规”python 上更快，但在 pypy 上慢得多。即便如此，无论在这个算法中使用常规循环还是 islice，pypy 仍然使用起来快得多

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

4

4 回答 4

8

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

于 2013-02-17T14:24:03.920 回答
3

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

于 2013-02-17T16:00:39.953 回答
2

正如您在开始帖子的评论中已经说过的那样，没有什么好方法可以使这个速度更快（除了 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
于 2013-02-17T15:09:52.500 回答
0

对于 Python 在标准库中使用 itertools 组合，它会将 for 循环移动到 C。

于 2021-03-04T20:05:00.667 回答