15

更新: 2009-05-29

すべての提案とアドバイスに感謝します。 私はあなたの提案を使用して、数日前の最高の結果よりも平均で 2.5 倍高速に実稼働コードを実行できるようにしました。 最終的にJavaコードを最速にすることができました。

教訓:

  • 以下のコード例は、プリミティブ int の挿入を示していますが、製品コードは実際には文字列を格納しています (私の悪い点です)。Pythonの実行時間が2.8秒から9.6秒になったことを修正しました。そのため、オブジェクトを格納するときは、実際には Java の方が高速でした。

  • しかしそれだけではありません。次のようにJavaプログラムを実行していました。

    Java -Xmx1024m SpeedTest

しかし、初期ヒープ サイズを次のように設定すると、大幅な改善が得られます。

java -Xms1024m -Xmx1024m SpeedTest

この単純な変更により、実行時間が 50% 以上短縮されました。したがって、SpeedTest の最終結果は python 9.6 秒です。Java 6.5 秒。

元の質問:

次のpythonコードがありました:

import time
import sys

def main(args):    
    iterations = 10000000
    counts = set()
    startTime = time.time();    
    for i in range(0, iterations):
        counts.add(i)
    totalTime = time.time() - startTime
    print 'total time =',totalTime
    print len(counts)

if __name__ == "__main__":
    main(sys.argv)

私のマシンでは約 3.3 秒で実行されましたが、もっと速くしたかったので、Java でプログラムすることにしました。Java はコンパイルされており、一般に Python よりも高速であると考えられているため、大きな見返りが得られると思いました。

Javaコードは次のとおりです。

import java.util.*;
class SpeedTest
{    
    public static void main(String[] args)
    {        
        long startTime;
        long totalTime;
        int iterations = 10000000;
        HashSet counts = new HashSet((2*iterations), 0.75f);

        startTime = System.currentTimeMillis();
        for(int i=0; i<iterations; i++)
        {
            counts.add(i);
        }
        totalTime = System.currentTimeMillis() - startTime;
        System.out.println("TOTAL TIME = "+( totalTime/1000f) );
        System.out.println(counts.size());
    }
}

したがって、この Java コードは基本的に Python コードと同じことを行います。しかし、3.3 秒ではなく 8.3 秒で実行されました。

単純化するために、この単純な例を実際の例から抽出しました。重要な要素は、例のように多くのメンバーで終わる (set または hashSet) があることです。

ここに私の質問があります:

  1. Python の実装が Java の実装よりも速いのはなぜですか?

  2. 一意のコレクションを保持するために、hashSet (java) よりも優れたデータ構造はありますか?

  3. Python の実装を高速化するにはどうすればよいでしょうか?

  4. Java の実装を高速化するにはどうすればよいでしょうか?

アップデート:

これまでに貢献してくれたすべての人に感謝します。詳細を追加させてください。

非常に複雑なため、本番コードは含めていません。そして、多くの気晴らしを生み出すでしょう。上記のケースは、可能な限り単純化したものです。つまり、java の put 呼び出しは、python set の add() よりもはるかに遅いようです。

本番コードの Java 実装も、上記と同様に、Python バージョンよりも約 2.5 ~ 3 倍遅くなります。

VM のウォームアップや起動時のオーバーヘッドは気にしません。startTime から totalTime までのコードを比較したいだけです。他のことは気にしないでください。

ハッシュセットを再ハッシュする必要がないように、十分な数のバケットを使用してハッシュセットを初期化しました。(コレクションに最終的に含まれる要素の数は常に前もってわかっています。) 私は、コレクションを iterations/0.75 に初期化するべきだったと主張することができると思います。しかし、試してみると、実行時間に大きな影響がないことがわかります。

好奇心旺盛な人のために Xmx1024m を設定しました (私のマシンには 4GB の RAM があります)。

Java バージョン: Java(TM) SE ランタイム環境 (ビルド 1.6.0_13-b03) を使用しています。

のプロダクション バージョンでは、hashSet に文字列 (2 ~ 15 文字) を格納しているため、プリミティブを使用できませんが、これは興味深いケースです。

コードを何度も実行しました。私は、Python コードが Java コードよりも 2.5 倍から 3 倍高速であることを確信しています。

4

20 に答える 20

21

Java と Python を実際にテストしているわけではありません。java.util.HashSet自動ボックス化された整数と Python のネイティブ セットおよび整数処理を使用してテストしています。

どうやら、この特定のマイクロベンチマークの Python 側は確かに高速です。

TIntHashSet私は HashSetをGNU Trove のものに置き換えてみましたが、3 倍から 4 倍の高速化を達成し、Java が Python よりわずかに優れていました。

本当の問題は、あなたのサンプル コードが、あなたが考えているほど実際にアプリケーション コードを代表しているかどうかです。プロファイラーを実行して、CPU 時間のほとんどが膨大な数の int を HashSet に入れるのに費やされていると判断したことがありますか? そうでない場合、例は無関係です。唯一の違いが、実稼働コードが int 以外のオブジェクトを格納することである場合でも、それらの作成とそのハッシュコードの計算は、セットの挿入を簡単に支配し (そして int を特別に処理するという Python の利点を完全に破壊し)、この質問全体を無意味にします。

于 2009-05-28T09:26:11.660 に答える
12

これは、Python が整数値自体をハッシュとして使用し、set のハッシュテーブル ベースの実装がその値を直接使用しているためだと思われます。ソースのコメントから:

これは必ずしも悪いことではありません!反対に、サイズが 2**i のテーブルでは、下位 i ビットを最初のテーブル インデックスとして使用することは非常に高速であり、int の連続した範囲によってインデックス付けされた dict の衝突はまったくありません。キーが「連続した」文字列の場合もほぼ同じです。したがって、これにより、一般的なケースでランダムよりも優れた動作が得られます。これは非常に望ましいことです。

このマイクロベンチマークは、ハッシュ衝突が正確にゼロになるため、Python にとっては最良のケースです。一方、Javas HashSet がキーを再ハッシュしている場合、追加の作業を実行する必要があり、衝突により動作がさらに悪化します。

範囲 (繰り返し) を一時変数に格納し、ループの前に random.shuffle を実行すると、シャッフルとリストの作成がループの外で行われたとしても、ランタイムは 2 倍以上遅くなります。

于 2009-05-28T08:46:54.967 に答える
7

もう 1 つの考えられる説明は、Python のセットは C コードでネイティブに実装されているのに対し、Java の HashSet は Java 自体に実装されているということです。そのため、Python のセットは本質的にはるかに高速である必要があります。

于 2009-05-27T23:06:52.827 に答える
7

Javaは少し「低レベル」の言語であるにもかかわらず、PythonプログラムはJavaプログラムよりも高速に実行されるというのが私の経験です。ちなみに、どちらの言語もバイト コードにコンパイルされます (これが .pyc ファイルです。.class ファイルのようなものと考えることができます)。どちらの言語も、仮想スタック マシンで解釈されるバイトコードです。

たとえば、a.b. Java では、これa.bは逆参照に解決されます。一方、Python は、1 つまたは複数のハッシュ テーブル ルックアップを実行する必要があります。ローカル スコープをチェックし、モジュール スコープをチェックし、グローバル スコープをチェックし、ビルトインをチェックします。

一方、Javaは、オブジェクトの作成(おそらくあなたの例の原因)やシリアライゼーションなどの特定の操作が苦手なことで有名です。

要約すると、単純な答えはありません。すべてのコード例でどちらの言語も高速になるとは思いません。

訂正: 何人かの人々が、Java はもはやオブジェクト作成においてそれほど悪くないと指摘しています。したがって、あなたの例では、それは別のものです。おそらく、コストがかかるのはオートボクシングです。おそらく、この場合、Python のデフォルトのハッシュ アルゴリズムの方が優れています。私の実際の経験では、Java コードを Python に書き直すと常にパフォーマンスが向上しますが、それは一般的に書き直しによるものと同じくらいパフォーマンスの向上につながる可能性があります。

于 2009-05-27T23:04:37.917 に答える
6

回答で見たいくつかの神話を払拭したいと思います。

Java はバイトコードにコンパイルされますが、最終的にはほとんどのランタイム環境でネイティブ コードにコンパイルされます。C の方が本質的に高速であると言う人は、すべてを語っているわけではありません。バイト コンパイル言語は本質的に高速であると主張できます。これは、JIT コンパイラーが、はるかに先を行くコンパイラーでは利用できないマシン固有の最適化を行うことができるためです。

違いを生む可能性のある多くのことは次のとおりです。

  • Python のハッシュ テーブルとセットは、Python で最も高度に最適化されたオブジェクトであり、Python のハッシュ関数は、同様の入力に対して同様の結果を返すように設計されています。 Python の整数。
  • 上記の二次的な効果は、ハッシュ テーブルに順番にアクセスするため、Python コードの参照の局所性が高くなることです。
  • Java は、コレクションに整数を追加するときに、整数の派手なボックス化とボックス化解除を行います。ボーナス面では、これにより Java での算術演算が Python よりもはるかに高速になりますが (bignum を使用しない限り)、欠点としては、慣れているよりも多くの割り当てが必要になります。
于 2009-05-28T09:53:03.367 に答える
5

編集:割り当てパターンによっては、実際のユースケースでは TreeSet の方が高速な場合があります。以下の私のコメントは、この単純化されたシナリオのみを扱います。しかし、それが大きな違いを生むとは思えません。本当の問題は別のところにあります。

ここの何人かは、HashSet を TreeSet に置き換えることを推奨しています。O(log n) の挿入時間を持つデータ構造が、すべての要素を格納するのに十分なバケットを事前に割り当てる O(1) 構造よりも速いという方法はないため、これは私にとって非常に奇妙なアドバイスのように思えます。

これをベンチマークするコードを次に示します。

import java.util.*;
class SpeedTest
{    
    public static void main(String[] args)
    {        
        long startTime;
        long totalTime;
        int iterations = 10000000;
        Set counts;

        System.out.println("HashSet:");
        counts = new HashSet((2*iterations), 0.75f);
        startTime = System.currentTimeMillis();
        for(int i=0; i<iterations; i++) {
            counts.add(i);
        }
        totalTime = System.currentTimeMillis() - startTime;
        System.out.println("TOTAL TIME = "+( totalTime/1000f) );
        System.out.println(counts.size());

        counts.clear();

        System.out.println("TreeSet:");
        counts = new TreeSet();
        startTime = System.currentTimeMillis();
        for(int i=0; i<iterations; i++) {
            counts.add(i);
        }
        totalTime = System.currentTimeMillis() - startTime;
        System.out.println("TOTAL TIME = "+( totalTime/1000f) );
        System.out.println(counts.size());
    }
}

そして、これが私のマシンでの結果です:

$ java -Xmx1024M SpeedTest
HashSet:
TOTAL TIME = 4.436
10000000
TreeSet:
TOTAL TIME = 8.163
10000000

また、ボクシングはパフォーマンスの問題ではなく、オブジェクトの作成は安価であると主張する人もいます。オブジェクトの作成が高速であることは事実ですが、プリミティブほど高速ではないことは明らかです。

import java.util.*;
class SpeedTest2
{    
    public static void main(String[] args)
    {        
        long startTime;
        long totalTime;
        int iterations = 10000000;

        System.out.println("primitives:");
        startTime = System.currentTimeMillis();
        int[] primitive = new int[iterations];
        for (int i = 0; i < iterations; i++) {
            primitive[i] = i;
        }
        totalTime = System.currentTimeMillis() - startTime;
        System.out.println("TOTAL TIME = "+( totalTime/1000f) );

        System.out.println("primitives:");
        startTime = System.currentTimeMillis();
        Integer[] boxed = new Integer[iterations];
        for (int i = 0; i < iterations; i++) {
            boxed[i] = i;
        }
        totalTime = System.currentTimeMillis() - startTime;
        System.out.println("TOTAL TIME = "+( totalTime/1000f) );
    }
}

結果:

$ java -Xmx1024M SpeedTest2
primitives:
TOTAL TIME = 0.058
primitives:
TOTAL TIME = 1.402

さらに、大量のオブジェクトを作成すると、ガベージ コレクターから追加のオーバーヘッドが発生します。これは、数千万のライブ オブジェクトをメモリに保持し始めると重要になります。

于 2009-05-27T23:33:12.947 に答える
4

このようなベンチマークは無意味だと思います。テストケースのように見える問題は解決しません。たいして面白くない。

NumPy と JAMA を使用した有意義な線形代数ソリューションのソリューションを見たいと思っています。多分私はそれを試して、結果を報告します。

于 2009-05-27T23:20:36.293 に答える
3

ここでまとめておきたい問題がいくつかあります。

最初に、一度だけ実行するプログラムの場合、余分に数秒かかることは問題ですか?

次に、これは 1 つのマイクロベンチマークにすぎません。マイクロベンチマークは、パフォーマンスの比較には無意味です。

スタートアップには多くの問題があります。

Java ランタイムは Python よりもはるかに大きいため、ディスクからのロードに時間がかかり、より多くのメモリを消費します。これは、スワップを行う場合に重要になる可能性があります。

設定していない場合は-Xms、ヒープのサイズを変更するためだけに GC を実行している可能性があります。最初にヒープのサイズを適切に設定することもできます。

Java が解釈から開始してからコンパイルするのは事実です。Sun クライアント [C1] Hotspot では約 1,500 回、サーバー [C2] では 10,000 回の繰り返し。Server Hotspot を使用すると、最終的にはパフォーマンスが向上しますが、より多くのメモリが必要になります。両方の長所を活かすために、非常に頻繁に実行されるコードにクライアント Hotspot がサーバーを使用する場合があります。ただし、これは通常、数秒の問題ではありません。

最も重要なことは、反復ごとに 2 つのオブジェクトを作成している可能性があることです。ほとんどのコードでは、実行のこのような割合でこれらの小さなオブジェクトを作成することはありません。6u14 と Harmony がさらに良くなっているので、TreeSet はオブジェクト数のスコアで優れている可能性があります。

Python は、実際にオブジェクトを持つのではなく、小さな整数オブジェクトを参照に格納することで勝っている可能性があります。これは間違いなく優れた最適化です。

多くのベンチマークの問題は、1 つのメソッドに多くの異なるコードが混在していることです。そんな気にするようなコードは書きませんよね?では、実際に高速に実行したいコードとは異なるパフォーマンス テストを試みているのはなぜでしょうか?

より良いデータ構造: 次のようなものBitSetは理にかなっているように見えます (ただし、同期が行われているため、パフォーマンスに影響する場合と影響しない場合があります)。

于 2009-05-27T23:21:41.503 に答える
2

プリミティブ型をセットに格納し、その上で重い作業を行いたい場合は、独自のセットを Java で展開します。ジェネリック クラスは、科学計算には十分な速度ではありません。

Ants Aasma が言及しているように、Python はハッシュをバイパスし、整数を直接使用します。Java は Integer オブジェクト ( autoboxing ) を作成し、それを Object (実装内) にキャストします。このオブジェクトも、ハッシュ セットで使用するためにハッシュする必要があります。

楽しい比較のために、これを試してください:

ジャワ

import java.util.HashSet;
class SpeedTest
{ 
  public static class Element {
    private int m_i;
    public Element(int i) {
      m_i = i;
    }
  }

  public static void main(String[] args)
  {        
    long startTime;
    long totalTime;
    int iterations = 1000000;
    HashSet<Element> counts = new HashSet<Element>((int)(2*iterations), 0.75f);

    startTime = System.currentTimeMillis();
    for(int i=0; i<iterations; ++i)
    {
      counts.add(new Element(i));
    }
    totalTime = System.currentTimeMillis() - startTime;
    System.out.println("TOTAL TIME = "+( totalTime/1000f) );
    System.out.println(counts.size());
  }
}

結果:

$java SpeedTest
TOTAL TIME = 3.028
1000000

$java -Xmx1G -Xms1G SpeedTest
TOTAL TIME = 0.578
1000000

パイソン

#!/usr/bin/python
import time
import sys

class Element(object):
  def __init__(self, i):
    self.num = i

def main(args):    
    iterations = 1000000
    counts = set()
    startTime = time.time();    
    for i in range(0, iterations):
        counts.add(Element(i))
    totalTime = time.time() - startTime
    print 'total time =',totalTime
    print len(counts)


if __name__ == "__main__":
  main(sys.argv)

結果:

$./speedtest.py 
total time = 20.6943161488
1000000

「Python は Java より速い」というのはどうですか?

于 2009-05-28T09:30:18.170 に答える
1

より高速なPythonのためのいくつかの変更。

#!/usr/bin/python
import time
import sys

import psyco                 #<<<<  
psyco.full()

class Element(object):
    __slots__=["num"]        #<<<<
    def __init__(self, i):
        self.num = i

def main(args):    
    iterations = 1000000
    counts = set()
    startTime = time.time();
    for i in xrange(0, iterations):
        counts.add(Element(i))
    totalTime = time.time() - startTime
    print 'total time =',totalTime
    print len(counts)

if __name__ == "__main__":
  main(sys.argv)

(env)~$ python speedTest.py
total time = 8.82906794548
1000000

(env)~$ python speedTest.py
total time = 2.44039201736
1000000

今、いくつかの古き良き浮気と...

#!/usr/bin/python
import time
import sys
import psyco

psyco.full()

class Element(object):
    __slots__=["num"]
    def __init__(self, i):
        self.num = i

def main(args):    
    iterations = 1000000
    counts = set()
    elements = [Element(i) for i in range(0, iterations)]
    startTime = time.time();
    for e in elements:
        counts.add(e)
    totalTime = time.time() - startTime
    print 'total time =',totalTime
    print len(counts)

if __name__ == "__main__":
  main(sys.argv)

(env)~$ python speedTest.py
total time = 0.526521921158
1000000
于 2009-06-02T13:53:25.490 に答える
1

ここでは暗闇の中で突き刺すだけですが、Python が行っているいくつかの最適化はおそらく Java ではありません:

  • Python の range() 呼び出しは、最適化された C コードで、10000000 個の整数オブジェクトすべてを一度に作成しています。Java は反復ごとに Integer オブジェクトを作成する必要があるため、処理が遅くなる可能性があります。
  • Python では int は不変であるため、オブジェクトにスロットを割り当てるのではなく、たとえばグローバル "42" への参照を格納するだけで済みます。Java のボックス化された Integer オブジェクトがどのように比較されるかはわかりません。
  • 組み込みの Python アルゴリズムとデータ構造の多くは、特殊なケース向けに大幅に最適化されています。たとえば、整数のハッシュ関数は、単純に恒等関数です。Java がより「巧妙な」ハッシュ関数を使用している場合、処理がかなり遅くなる可能性があります。ほとんどの時間をデータ構造のコードに費やしているのであれば、Python C 実装を手動で調整するために何年にもわたって費やされてきた労力を考えると、Python が Java を上回ったとしてもまったく驚かないでしょう。
于 2009-05-28T01:53:24.287 に答える
1

JVM を起動したときのメモリ量は? 場合によります?1 Gig の RAM を使用してプログラムで JVM を実行すると、次のようになります。

$ java -Xmx1024M -Xms1024M -classpath . SpeedTest 
TOTAL TIME = 5.682
10000000
$ python speedtest.py 
total time = 4.48310899734
10000000

少ないメモリで JVM を実行すると、時間がかかります...かなり長くなります:

$ java -Xmx768M -Xms768M -classpath . SpeedTest 
TOTAL TIME = 6.706
10000000
$ java -Xmx600M -Xms600M -classpath . SpeedTest 
TOTAL TIME = 14.086
10000000

HashSetこの特定のインスタンスでは、これがパフォーマンスのボトルネックだと思います。を に置き換えるHashSetLinkedList、プログラムは大幅に高速化されます。

最後に -- Java プログラムは最初に解釈され、何度も呼び出されるメソッドだけがコンパイルされることに注意してください。したがって、Python をコンパイラではなく Java のインタープリターと比較している可能性があります。

于 2009-05-27T23:14:12.343 に答える
1

Java プログラムをチューニングする場合は、Python プログラムもチューニングする必要があります。

>>> import timeit
>>> timeit.Timer('x = set()\nfor i in range(10000000):\n    x.add(i)').repeat(3, 1)
[2.1174559593200684, 2.0019571781158447, 1.9973630905151367]
>>> timeit.Timer('x = set()\nfor i in xrange(10000000):\n    x.add(i)').repeat(3, 1)
[1.8742368221282959, 1.8714439868927002, 1.869229793548584]
>>> timeit.Timer('x = set(xrange(10000000))').repeat(3, 1)
[0.74582195281982422, 0.73061800003051758, 0.73396801948547363]

を使用xrangeするだけで、私のマシンでは約 8% 高速になります。また、エクスプレッションset(xrange(10000000))はまったく同じセットを構築しますが、2.5 倍高速です (1.87 秒から 0.74 秒)。

Python プログラムをチューニングするとプログラムが短くなるのが気に入っています。:) しかし、Java でも同じことができます。誰もが知っているように、Java で小さい整数の密なセットが必要な場合は、ハッシュ テーブルを使用しません。あなたはjava.util.BitSet

BitSet bits = new BitSet(iterations);

startTime = System.currentTimeMillis();
bits.set(0, iterations, true);
totalTime = System.currentTimeMillis() - startTime;
System.out.println("TOTAL TIME = "+( totalTime/1000f) );
System.out.println(bits.cardinality());

それはかなり速いはずです。残念ながら、今はテストする時間がありません。

于 2009-11-20T23:53:31.430 に答える
0

単純な少し余分なものを追加するだけで、Javaマイクロベンチャム​​をはるかに高速にすることができます。

    HashSet counts = new HashSet((2*iterations), 0.75f);

になります

    HashSet counts = new HashSet((2*iterations), 0.75f) {
        @Override public boolean add(Object element) { return false; }
    };

シンプルで高速で、同じ結果が得られます。

于 2009-05-27T23:59:54.450 に答える
0

最大の問題は、おそらく、特定のコードが測定するのは経過時間(時計が測定する時間) ですが、コードのランタイムを比較するために測定する必要があるのはプロセス時間です。タスク。

于 2009-05-27T23:24:43.493 に答える