Java反復HashTableとArrayListの速度

Question

私は単純な3D SWレンダリングエンジンを書いています。私はシーン全体を含むデフォルトのArrayList<Object3D>を持っています。さて、私は、3Dエディタのようにオブジェクトを追加、削除、選択することができるようにしたいと考えています。

私が最初に考えたのは、ArrayListという名前とインデックスのためにHashtableを持つことです。しかし、私はただ単にHashtableを使ってシーンを保存するだけで、イテレータを使ってレンダリングすることができたと思った。

3Dエンジンでは、スピード優先とは何ですか？オブジェクトを選択するのに比べて、1秒間に何度もシーンをループさせるためです。 ArrayListはiterated Hashtableより速いですか？ありがとう。無用同期に少ないオーバーヘッド：

Answer 1

まず、私はあなたがArrayListがVectorより良い選択であるのと同じ理由でHashMapの代わりHashtableを、使用することをお勧め。

私の推測では、ArrayListを反復することHashtable年代（またはHashMap年代）entrySet()メソッドによって返さSetを反復処理よりも高速になるということです。しかし、知る唯一の方法はプロファイルすることです。

表示リストの変更（最後の要素の追加または切り捨てを除く）は、ArrayListの場合よりもHashMapの方が速くなります。

EDIT 私は自分のアドバイスに従って、ベンチマークを行った。ここで私が使用するコードは次のとおりです。

import java.util.*; 

public class IterTest { 
    static class Thing { 
     Thing(String name) { this.name = name; } 
     String name; 
    } 

    static class ArrayIterTest implements Runnable { 
     private final ArrayList<Thing> list; 
     ArrayIterTest(ArrayList<Thing> list) { 
      this.list = list; 
     } 
     public void run() { 
      int i = 0; 
      for (Thing thing : list) { 
       ++i; 
      } 
     } 
    } 

    static class ArraySubscriptTest implements Runnable { 
     private final ArrayList<Thing> list; 
     ArraySubscriptTest(ArrayList<Thing> list) { 
      this.list = list; 
     } 
     public void run() { 
      int i = 0; 
      int n = list.size(); 
      for (int j = 0; j < n; ++j) { 
       Thing thing = list.get(j); 
       ++i; 
      } 
     } 
    } 

    static class MapIterTest implements Runnable { 
     private final Map<String, Thing> map; 
     MapIterTest(Map<String, Thing> map) { 
      this.map = map; 
     } 
     public void run() { 
      int i = 0; 
      Set<Map.Entry<String, Thing>> set = map.entrySet(); 
      for (Map.Entry<String, Thing> entry : set) { 
       ++i; 
      } 
     } 
    } 

    public static void main(String[] args) { 
     final int ITERS = 10000; 
     final Thing[] things = new Thing[1000]; 
     for (int i = 0; i < things.length; ++i) { 
      things[i] = new Thing("thing " + i); 
     } 
     final ArrayList<Thing> arrayList = new ArrayList<Thing>(); 
     Collections.addAll(arrayList, things); 
     final HashMap<String, Thing> hashMap = new HashMap<String, Thing>(); 
     for (Thing thing : things) { 
      hashMap.put(thing.name, thing); 
     } 
     final ArrayIterTest t1 = new ArrayIterTest(arrayList); 
     final ArraySubscriptTest t2 = new ArraySubscriptTest(arrayList); 
     final MapIterTest t3 = new MapIterTest(hashMap); 
     System.out.println("t1 time: " + time(t1, ITERS)); 
     System.out.println("t2 time: " + time(t2, ITERS)); 
     System.out.println("t3 time: " + time(t3, ITERS)); 
    } 

    private static long time(Runnable runnable, int iters) { 
     System.gc(); 
     long start = System.nanoTime(); 
     while (iters-- > 0) { 
      runnable.run(); 
     } 
     return System.nanoTime() - start; 
    } 
} 

そして、ここでは典型的な実験の結果、次のとおりです。

t1 time: 41412897 
t2 time: 30580187 
t3 time: 146536728 

は明らかにArrayListのを使用して、HashMapのオーバー（3-4倍）大きな勝利です少なくとも、私のスタイルではHashMapを繰り返し処理しています。私は、配列イテレータが配列添字よりも遅い理由は、作成してガベージコレクションする必要があるすべてのイテレータオブジェクトだと考えています。

参考までに、これは、空き容量が豊富なIntel 1.6GHzクアッドコアWindowsマシン上で、Java 1.6.0_26（64ビットJVM）を使用して行いました。

Answer 2

ArrayListを反復することは、Hashtableを反復するよりも速くなることは確かです。しかし、実際の内部ロジックでは2倍の差があるかもしれませんが、それほど重要ではありません。

ただし、マルチスレッド同期が必要な場合を除き、HashtableではなくHashMapを使用する必要があります。そこにはいくつかのパフォーマンスがあります。

Answer 3

A）Hashtableを使用しないでください。HashMapを使用してください。 Hashtableは非公式に非推奨です

B）これはアプリケーションによって異なります。 HashMapではルックアップが高速になりますが、イテレーションは両方とも内部で配列を使用する場合と同じになる可能性があります。 （しかし、HashMapの配列にはギャップがあるため、ArrayListにわずかな利点があるかもしれません）。ああ、あなたは、反復の一定の秩序を維持したい場合は、検索の同期を必要としない場合、（挿入によってソート）LinkedHashMapまたはTreeMap（自然順序付けでソート）

Answer 4

利用java.util.HashMapの代わりjava.util.Hashtableを使用しています。

Answer 5

実際には、現在のHashMapの実装（すべてが指摘するようにHashtableより優先されています）を見ました。値を反復することは、基本的な配列を単純に反復することのように見えます。

速度はおそらくArrayListの繰り返しに匹敵しますが、基本配列のギャップをスキップするのに時間がかかることがあります。

すべては、プロファイリングはキングです。

Answer 6

既に述べたように、HashMapを使用する方が良いです。反復に関して、理論的には、ArrayListは2つの理由により高速でなければならない。第一に、データ構造が単純でアクセス時間が短いことです。 2番目は、ArrayListは、Iteratorオブジェクトを作成せずにインデックスで反復することができます。これは、使用頻度が高い場合にはガベージが少なくなり、gcが少なくなります。 実際には、違いを気付かないかもしれませんが、どれくらい重く使うかによって異なります。