13

kjellkod の記事ArrayListで、引数として受け取るメソッドを渡すと、ArrayList が追加のRandomAccessインターフェイスをList実装するため、パフォーマンスが低下することが言及されました。記事の例:

// SLOWER: as shown in http://ideone.com/1wnF1
private static void linearInsertion(Integer[] intArray, List<Integer> list) {
[...]
int list_size = list.size();
for (int i = 0; i < list_size; i++) {
if (integer.compareTo(list.get(i)) >= 0) { // ... more code

// FASTER: as shown in http://ideone.com/JOJ05
private static void linearInsertion(Integer[] intArray, ArrayList<Integer> list) {
[...]
int list_size = list.size();
for (int i = 0; i < list_size; i++) {
if (integer.compareTo(list.get(i)) >= 0) { // ... more code

参照から：

ジェネリック リスト アルゴリズムでは、指定されたリストがこのインターフェイスのインスタンスであるかどうかを確認してから、順次アクセス リストに適用するとパフォーマンスが低下するアルゴリズムを適用し、必要に応じて動作を変更して、許容可能なパフォーマンスを保証することをお勧めします。

ただし、上記のメソッドと check で実際に ArrayList を渡すとlist instanceof RandomAccess、どちらの場合も true になります。では、私の最初の質問は、なぜ Java VM が最初の方法でこれを順次リストとして解釈する必要があるのか​​ということです。

私のマシンでこの動作を確認するために、記事のテストを変更しました。ideone でテストを実行すると、kjellkodと同様の結果が表示されます。しかし、ローカルで実行すると、予期しない結果が得られました。これは、記事の説明と私の理解に反しています。私の場合、ArrayList as List の反復は、ArrayList として参照するよりも 5 ～ 25% 高速であるようです。

ここに画像の説明を入力

この違いはどのように説明できますか？アーキテクチャやプロセッサ コアの数に依存しますか? 私の作業マシンの構成は、Windows 7 Professional x64、Intel Core i5-3470 (4 コア、4 スレッド)、16 GB RAM です。

4

2 に答える 2

3

では、私の最初の質問は、なぜ Java VM が最初の方法でこれを順次リストとして解釈する必要があるのか​​ということです。

JVM には、シーケンシャルまたはランダム アクセス リストの概念がありません。(マーカー インターフェイスとは別に) ArrayList が O(n) 時間ではなく O(1) 時間でランダム アクセス ルックアップを実行することを認識しているのは、実装の開発者です。

アーキテクチャやプロセッサ コアの数に依存しますか?

-clientいいえ、たとえば 32 ビット Windows と-serverたとえば任意の 64 ビット JVMとの間には違いがあります。

List テストを 2 番目に実行したと思われます。これは、JIT と CPU キャッシュの両方でコードがより警告されるため、より高速になる可能性があります。各テストを少なくとも 3 回実行することをお勧めします。最も長いテストを最初に実行し、最初の実行は無視します。

注: contains() はリストに対して O(n) であるため、タイミングが O(n^2) に大きくなります。明らかに、重複を無視したい場合はリストを使用しません。何が最適化され、何が最適化されないかの微妙な点に非常に影響を受けやすいため、混乱します。すでに合理的に最適化されているコードを比較すると、より意味のある結果が得られます。

于 2013-06-11T11:22:49.327 に答える