最も効率的なJava Collectionsライブラリとは何ですか?


Answers

質問は、(今)多くのデータを格納することです。これは、Map内のintなどのプリミティブ型を使用して表現できます。 私の意見では、ここの答えの中には誤解を招くものがあります。 なぜか見てみましょう。

私は実行時とメモリ消費の両方を測定するためにベンチマークをtroveから変更しました。 また、このベンチマークにPCJを追加しましたPCJはプリミティブ型の別のコレクションライブラリです(私はそれを広範囲に使用しています)。 '公式'のベンチマークは、IntIntMapsとJava CollectionのMap<Integer, Integer>比較しません。おそらくIntegersを格納し、 intsを格納することは技術的観点から同じではありません。 しかし、ユーザーはこの技術的な詳細を気にする必要はなく、 ints表現可能なデータを効率的に格納したいと考えていints

最初にコードの関連部分:

new Operation() {

     private long usedMem() {
        System.gc();
        return Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory();
     }

     // trove
     public void ours() {
        long mem = usedMem();
        TIntIntHashMap ours = new TIntIntHashMap(SET_SIZE);
        for ( int i = dataset.size(); i-- > 0; ) {
           ours.put(i, i);
        }
        mem = usedMem() - mem;
        System.err.println("trove " + mem + " bytes");
        ours.clear();
     }

     public void pcj() {
        long mem = usedMem();
        IntKeyIntMap map = new IntKeyIntOpenHashMap(SET_SIZE);
        for ( int i = dataset.size(); i-- > 0; ) {
           map.put(i, i);
        }
        mem = usedMem() - mem;
        System.err.println("pcj " + mem + " bytes");
        map.clear();
     }

     // java collections
     public void theirs() {
        long mem = usedMem();
        Map<Integer, Integer> map = new HashMap<Integer, Integer>(SET_SIZE);
        for ( int i = dataset.size(); i-- > 0; ) {
           map.put(i, i);
        }
        mem = usedMem() - mem;
        System.err.println("java " + mem + " bytes");
        map.clear();
     }

私は、データがプリミティブなintsとして来ると仮定します。 しかし、これはプリミティブコレクションフレームワークでは必要ではない自動ボクシングのために、java utilの実行時のペナルティを意味します。

WinXP、jdk1.6.0_10上で実行時の結果(もちろんgc()呼び出しなしgc()

                      100000 put operations      100000 contains operations 
java collections             1938 ms                        203 ms
trove                         234 ms                        125 ms
pcj                           516 ms                         94 ms

これは既に劇的に見えるかもしれませんが、これはそのようなフレームワークを使用する理由ではありません。

理由はメモリの性能です。 100000のintエントリを含むマップの結果:

java collections        oscillates between 6644536 and 7168840 bytes
trove                                      1853296 bytes
pcj                                        1866112 bytes

Javaコレクションは、プリミティブコレクションフレームワークと比較して3倍以上のメモリを必要とします。 すなわち、ディスクIOに頼ることなく、ランタイムパフォーマンスを大きく下げることなく、3倍のデータをメモリに保持することができます。 そして、これは重要です。 なぜhighscalabilityかを調べてください。

私の経験上、高いメモリ消費量はJavaで最大のパフォーマンス問題であり、もちろん実行時のパフォーマンスが悪くなります。 プリミティブコレクションフレームワークは本当にここで役立ちます。

だから:いいえ、java.utilは答えではありません。 また、Javaコレクションへの「機能の追加」は、効率性について質問する際のポイントではありません。 また、現代のJDKコレクションは「特殊化されたTroveコレクションでさえも実行できません 」。

免責事項:ここのベンチマークは完全ではありませんし、完璧でもありません。 それは私が多くのプロジェクトで経験したポイントを家に追いやることを意味しています。 プリミティブコレクションは、大量のデータを扱う場合に、魚のようなAPIに耐えられるほど十分に役立ちます。

Question

最も効率的なJava Collectionsライブラリとは何ですか?

数年前、私はたくさんのJavaを実行し、その時点で、Java(登録trove )コレクションの最も優れた実装であるという印象を受けました。 しかし、私が「 最も有用な無料のJavaライブラリ 」という質問に対する答えを読んだとき、私は、 troveがほとんど言及されていないことに気づいた。 だから、現在どのJava Collectionsライブラリが最適ですか?

更新:明確にするために、私は、ハッシュテーブルなどに何百万ものエントリを保存する必要があるときに、どのライブラリを使うべきかを知りたいと思っています(小さなランタイムとメモリフットプリントが必要です)。




他の論評家が気付いたように、「効​​率的な」という定義は広いネットを投げかけます。 しかし、誰もまだJavolutionライブラリについて言及していません。

いくつかのハイライト:

  • Javolutionクラスは高速で高速です(標準のStringBuffer / StringBuilderではO [n]ではなくO [Log(n)]でのテキスト挿入/削除など)。
  • すべてのJavolutionクラスは、ハードリアルタイム対応であり、非常に確定的な動作(マイクロ秒の範囲内)を持ちます。 さらに(標準ライブラリとは異なり)JavolutionはRTSJに安全です(Java Real-Time拡張機能で使用するとメモリのクラッシュやメモリリークはありません)。
  • Javolutionのリアルタイムコレクションクラス(マップ、リスト、テーブル、セット)は、ほとんどの標準コレクションクラスの代わりに使用でき、追加の機能を提供します。
  • Javolutionのコレクションは、並列アルゴリズムの実装を容易にするための並行性の保証を提供します。

Javolutionディストリビューションにはベンチマークスイートが含まれていますので、他のライブラリや組み込みコレクションとどのようにスタックするかを見ることができます。




「効率的」をどのように定義するかによって異なります。

すべてのデータ構造には、読み取り、書き込み、反復、メモリフットプリントなどのためのBig-Ohビヘイビアがあります。1つのライブラリ内のリンクされたリストは他のものと同じである可能性があります。 そして、ハッシュマップはリンクされたリストO(n)よりもO(1)を読む方が速いでしょう。

しかし、私が「最も有用な無料のJavaライブラリ」という質問に対する答えを読んだところ、 私は、実車がほとんど言及されていないことに気づいた。

これは「最も効率的」のようには聞こえません。 私にとっては「最も人気がある」のように聞こえる。

ほんの少しのフィードバック - 私はそれを聞いたことがないし、それを使った人は誰も知らない。 JDK、Google、またはApache Commonsに組み込まれているコレクションは、私にはよく知られています。




何百万ものレコードをハッシュテーブルに保存したい場合は、メモリの問題にぶつかる可能性があります。 これは私が230万のStringオブジェクトを持つマップを作成しようとしたときに起こったことです。 私はBerkeleyDBと一緒に行きましたBerkeleyDBは非常に成熟していて、うまく動作します。 彼らはコレクションAPIを包むJava APIを持っているので、わずかなメモリフットプリントで任意の大きなマップを簡単に作成することができます。 アクセスは(ディスクに保存されているので)遅くなります。

フォローアップの質問 :不変のコレクションのためのまともな(そして効率的な)よく管理されたライブラリがありますか? Clojureにはこれに対する優れたサポートがあり、Javaに似たようなものを用意することは良いことです。







java.util

申し訳ありませんが、ほとんどの用途ではデフォルトのJava Collectionsが十分です。