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に保持し、インタープリター（コンパイラー）を追加するのは簡単ですか？それとも、別のインタプリタ/コンパイラに切り替えると、状況が少しだけ良くなるだけですか？

現在、Windows7でPython2.7.3とJava1.732ibtsを使用しています。

私は、Java / pythonのパフォーマンスについて、SOについて同様の質問があることを知っていますが、Pythonのランタイム環境が異なるなどの回答は、現時点では役に立ちません。

私が知りたいのは、これらのランタイムのいくつかがこの巨大なギャップを埋めることができ、epxloringする価値があるかどうかです。

アップデート ：

私はpypyをインストールしましたが、今ではその違いは非常に大きいです...

更新2：

私が気付いたいくつかの非常に興味深いこと：ここでの回答のisliceメソッドは、「通常の」Pythonでは高速ですが、pypyでははるかに低速です。それでも、このアルゴリズムで通常のループやisliceを使用していても、pypyを使用するとはるかに高速なままです。

Bakuriuが発言で気づいたように、ランタイム環境は非常に重要ですが、このアルゴリズムのランタイム環境が高速であると、どのアルゴリズムでも必ずしも高速であるとは限りません...

4

4 に答える 4

8

CPythonの代わりにPyPyで実行してみてください。おそらくはるかに速くなります。

于 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がJust In Time（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 に答える