15

セルオートマトンのようなプログラムの場合、リストのようなオブジェクトに対して可能な限り短い時間（ミリ秒単位）で100,000〜1,000,000のランダムアクセス読み取りを行う必要があるプログラムがあります。私が使用している更新アルゴリズムはすでに最適化されていると思います（アクティブなセルを効率的に追跡するなど）。リストはサイズを変更する必要がありますが、そのパフォーマンスはそれほど重要ではありません。したがって、ArrayListsの代わりにArraysを使用した場合のパフォーマンスが、このような短い時間で多くの読み取りを処理するときに違いを生むのに十分かどうか疑問に思っています。現在、ArrayListsを使用しています。

編集：言及するのを忘れました：私は整数を格納しているだけなので、別の要因は、整数ラッパークラス（ArrayListsの場合）とints（配列の場合）を使用することです。ArrayListを使用するのに実際に3つのポインタールックアップ（1つはArrayList、1つは基になる配列、もう1つはInteger-> int）が必要かどうかは誰にもわかりませんが、配列には1つしか必要ありません（配列アドレス+特定のオフセット） int）？HotSpotは余分なルックアップを最適化しますか？それらの余分なルックアップはどれほど重要ですか？

Edit2：また、ランダムアクセス書き込み（挿入ではなく書き込み）も実行する必要があることを忘れました。

4

12 に答える 12

11

配列が実際にはプリミティブ型の配列であると述べたので、 Troveライブラリのプリミティブ型のコレクションクラスの使用を検討してください。

@vikingは、彼のアプリケーションでTroveを使用すると、大幅な（10倍！）高速化を報告しています。コメントを参照してください。反対に、TroveコレクションタイプはJavaの標準コレクションAPIとタイプ互換性がありません。したがって、Trove（または同様のライブラリ）がすべての場合に答えになるわけではありません。

于 2009-07-26T01:55:29.153 に答える
10

両方を試してください、しかし測定してください。

ほとんどの場合、コードをそれほど変更せずに、何かを一緒にハックして、内部ループに配列を使用させることができます。私の疑惑は、HotSpotがすでにメソッド呼び出しをインライン化しており、パフォーマンスの向上が見られないことです。

また、Java 6 update 14を試して、-XX：+DoEscapeAnalysisを使用してください

于 2009-07-25T20:15:57.513 に答える
3

私はケビンのアドバイスで行きます。

プログラムがアレイを備えたバージョンと比較するのが遅い場合は、最初にリストを使用してパフォーマンスを測定してください。それが測定可能なパフォーマンスの向上をもたらす場合は、アレイを使用してください。リストにとどまらない場合は、作業がはるかに楽になるためです。

于 2009-07-25T20:20:50.247 に答える
3

ArrayListsはArraysよりも低速ですが、ほとんどの人は違いはわずかであると考えています。あなたの場合は、何十万ものそれらを扱っているので、しかし問題になる可能性があります。

ちなみに、複製：Javaの配列またはリスト。どちらが速いですか？

于 2009-07-25T19:56:35.880 に答える
3

配列の代わりに使用するとオーバーヘッドが発生しますが、ArrayList小さい可能性が非常に高くなります。実際、の有用なデータはArrayListレジスタに格納できますが、おそらくもっと多くのデータを使用します（Listたとえばサイズ）。

編集で、ラッパーオブジェクトを使用していると述べています。これらは大きな違いを生みます。通常、同じ値を繰り返し使用している場合は、適切なキャッシュポリシーが役立つ場合があります（Integer.valueOf-128〜128でも同じ結果が得られます）。プリミティブの場合、プリミティブ配列は通常快適に勝ちます。

改良点として、隣接するセルが配列内で隣接する傾向があることを確認することをお勧めします（スペース充填曲線のある列の行よりもうまくいくことができます）。

于 2009-07-26T00:36:56.217 に答える
2

1つの可能性は、ArrayListを再実装することです（それほど難しくはありません）が、ロック/解放呼び出しサイクルを介してバッキング配列を公開します。これにより、書き込みが便利になりますが、アレイのサイズに影響を与えないことが事前にわかっている一連の読み取り/書き込み操作のためにアレイが公開されます。リストがロックされている場合、追加/削除は許可されません。取得/設定するだけです。

例えば：

  SomeObj[] directArray = myArrayList.lockArray();
  try{
    // myArrayList.add(), delete() would throw an illegal state exception
    for (int i = 0; i < 50000; i++){
      directArray[i] += 1;
    }
  } finally {
    myArrayList.unlockArray();
  }

このアプローチは、ArrayListの配列の成長などの動作をカプセル化し続けます。

于 2009-07-25T20:27:29.907 に答える
2

Javaは、オブジェクトに二重間接参照を使用するため、オブジェクトはメモリ内で移動でき、参照は引き続き有効です。つまり、すべての参照ルックアップは2つのポインタールックアップと同等です。これらの余分なルックアップを完全に最適化することはできません。

おそらくさらに悪いのは、キャッシュのパフォーマンスがひどくなることです。キャッシュ内の値へのアクセスは、メインメモリ内の値へのアクセスよりも何倍も高速になります。（おそらく10倍）int []がある場合、値はメモリ内で連続しているため、キャッシュに簡単にロードされます。ただし、Integer []の場合、Integersの個々のオブジェクトはメモリ全体にランダムに表示される可能性があり、キャッシュミスの可能性がはるかに高くなります。また、整数は24バイトを使用します。これは、4バイトの値よりもキャッシュに収まる可能性がはるかに低いことを意味します。

整数を更新すると、多くの場合、int値を更新するよりも桁違いに大きい新しいオブジェクトが作成されます。

于 2009-07-25T22:27:35.453 に答える
2

リストを一度作成し、そこから何千もの読み取りを行う場合、ArrayListからのオーバーヘッドは無視できるほどわずかである可能性があります。何千ものリストを作成する場合は、標準の配列を使用してください。ループ内でのオブジェクトの作成は、メンバー変数のインスタンス化、コンストラクターの継承チェーンの呼び出しなどのすべてのオーバーヘッドのために、すぐに2次式になります。

このため、そして2番目の質問に答えるために、Integerクラスではなく標準のintを使用してください。両方のプロファイルを作成すると、その理由がすぐに（またはむしろゆっくりと）わかります。

于 2009-07-26T00:57:25.987 に答える
1

オプションは次のとおり
です。1。配列を使用する
2.内部的に配列を使用するArrayListを使用する

ArrayListによってオーバーヘッドが発生することは明らかです（ArrayListのソースコードを調べてください）。ユースケースの99％では、このオーバーヘッドは簡単に無視できます。ただし、時間に敏感なアルゴリズムを実装し、インデックスごとにリストから数千万回の読み取りを行う場合は、リストの代わりにベア配列を使用すると、大幅な時間の節約になります。常識を使用します。

こちらをご覧ください：http ：//robaustin.wikidot.com/how-does-the-performance-of-arraylist-compare-to-arrayコンパイラの最適化を回避するために、個人的にテストを微調整します。たとえば、「j」を変更します。 ="を"j+ = "に変換し、ループの後に"j"を使用します。

于 2012-01-05T17:11:09.673 に答える
1

この構造体からの読み取り以上のことを行わない場合は、先に進んで配列を使用してください。これは、インデックスで読み取る場合の方が高速です。

ただし、そこにデータを取得する方法を検討してください。並べ替え、挿入、削除などが問題になる場合は、その場合は、他のコレクションベースの構造を検討することをお勧めします。

于 2009-07-25T19:58:19.217 に答える
1

プリミティブははるかに（はるかに）高速です。いつも。JITエスケープ分析などでも。java.lang.Integerでのラッピングをスキップします。また、ほとんどのArrayList実装がget（int）で行う配列境界チェックをスキップします。ほとんどのJITは、単純なループパターンを認識してループを削除できますが、パフォーマンスが心配な場合は、それほど多くの理由はありません。

プリミティブアクセスを自分でコーディングする必要はありません-COLTライブラリからIntArrayListを使用するように切り替わることができると思います-http://acs.lbl.gov/~hoschek/colt/を参照してください-"ColtはJavaでの高性能科学技術コンピューティングのためのオープンソースライブラリ"）-数分のリファクタリングで。

于 2009-07-26T07:32:37.620 に答える
0

配列は、少なくとも関数呼び出し（つまり、get（i））をスキップするため、より高速になります。

サイズが静的な場合は、配列が最適です。

于 2009-07-25T19:56:13.323 に答える