1

添付のテストを実行しました。結果は一貫して、インデックスによる配列を介したアクセスがキーによるマップを介したアクセスよりも 10 倍高速であることを示しています。この桁違いの違いは私たちを驚かせました。

Map のキーは java.lang.String です ... Map キーの java.lang.String.hashcode() 実装を計算するコストが唯一の理由ですか? 添付のコードでは、キーを 1 つだけ使用して実行しました

java.lang.String key = 1;

この場合、コンパイラ/ランタイムはキャッシュしませんか? それとも、呼び出しごとに再計算しますか?

洞察をありがとう。

public class PerfTest {
static java.util.HashMap<String, Double> map;
static Double[] array = {1.0,2.0,3.0,4.0,5.0,6.0,7.0,8.0,9.0,10.0};

static long nTimes = 1000000;

static{
    map = new java.util.HashMap<String, Double>();
    map.put("1",    new Double(1));
    map.put("2",    new Double(2));
    map.put("3",    new Double(3));
    map.put("4",    new Double(4));
    map.put("5",    new Double(5));
    map.put("6",    new Double(6));
    map.put("7",    new Double(7));
    map.put("8",    new Double(8));
    map.put("9",    new Double(9));
    map.put("10",   new Double(10));        
}

public static void main(String[] args){

    PerfTest tester = new PerfTest();
    long timeInMap  = tester.testHashMap();
    long timeInArray    = tester.testArray();

    System.out.println("Corrected time elapsed in map(in seconds): "        
            + (timeInMap)/1000000000.0);
    System.out.println("Corrected time elapsed in array(in seconds): " 
            + (timeInArray)/1000000000.0);
}

private long testHashMap(){
    int sz = map.size();
    long startTime = System.nanoTime();

    String key = "1";   

    for (int i=0; i <nTimes; i++){
        double sum = 0; 

        for (int j =1; j<=sz; j++){
            sum += map.get(key);                            
        }
    }
    return (System.nanoTime() - startTime);
}

private long testArray(){
    long startTime = System.nanoTime();

    for (int i=0; i <nTimes; i++){
        double sum = 0;

        for (int j=0; j< array.length; j++) {       
            sum += array[j];
        }
    }   
    return (System.nanoTime() - startTime);
   }
 }
4

5 に答える 5

6

Java のシステム時間を使用することは、実際のベンチマークを取得するための良い方法ではありません。私はあなたのコードをリファクタリングしてGoogle Caliper (とりわけ JVM をウォームアップします) を使用しました...そしてあなたと同様の結果を発見しました。System.out.printlnコメント投稿者は、私の元のバージョンが良くなく、ほとんどの場合電話に出ていたことを正しく指摘しました。

私が言ったように、ベンチマークを書くのは難しいです。以下に更新されたのは、新しい正しいバージョンです。

結果：

 0% Scenario{vm=java, trial=0, benchmark=HashMap} 51.04 ns; σ=0.22 ns @ 3 trials
50% Scenario{vm=java, trial=0, benchmark=Array} 4.05 ns; σ=0.01 ns @ 3 trials

benchmark    ns linear runtime
  HashMap 51.04 ==============================
    Array  4.05 ==

コード：

import com.google.caliper.Runner;
import com.google.caliper.SimpleBenchmark;

public class PerfTest {
    public static double hashNum = 0;
    public static double arrayNum = 0;

    public static class PerfBenchmark extends SimpleBenchmark {
        static java.util.HashMap<String, Double> map;
        static Double[] array = {1.0,2.0,3.0,4.0,5.0,6.0,7.0,8.0,9.0,10.0};

        static{
            map = new java.util.HashMap<String, Double>();
            map.put("1",    new Double(1));
            map.put("2",    new Double(2));
            map.put("3",    new Double(3));
            map.put("4",    new Double(4));
            map.put("5",    new Double(5));
            map.put("6",    new Double(6));
            map.put("7",    new Double(7));
            map.put("8",    new Double(8));
            map.put("9",    new Double(9));
            map.put("10",   new Double(10));        
        }

        public void timeHashMap(int nTimes){
            int sz = map.size();

            String key = "1";   

            for (int i=0; i <nTimes; i++){
                double sum = 0; 

                for (int j =1; j<=sz; j++){
                    sum += map.get(key);                            
                }

                hashNum += sum;
            }
        }

        public void timeArray(int nTimes){
            for (int i=0; i <nTimes; i++){
                double sum = 0;

                for (int j=0; j< array.length; j++) {       
                    sum += array[j];
                }

                arrayNum += sum;
            }
        }
    }

    public static void main(String[] args){
        Runner.main(PerfBenchmark.class, new String[0]);

        System.out.println(hashNum);
        System.out.println(arrayNum);
    }
}
于 2013-05-01T21:54:24.017 に答える
1

HashMap が実際にはハッシュ テーブルであり、データを基になる配列全体に分散させ、インデックスを計算し、配列内で検索して返す必要があることを理解していれば、それほど驚くことではありません。一方、配列はメモリの連続したブロックであり、インデックスの場所を見つけるために計算は必要ありません。

それに加えて、非常に予測可能な順序で配列にアクセスしているため、最近のすべてのプロセッサが行うようにメモリをプリフェッチしても、ミスは発生しません。

于 2013-05-01T21:53:44.737 に答える
1

get()キーをハッシュする必要があり、キーに対して等価比較を実行する必要もあります (2 つの異なるキーがバッキング配列の同じインデックスにハッシュされる可能性があるため) - パフォーマンスの比較は、 10 個を超えるキー/配列要素を使用すると、String#equalsメソッドの平均コストが増加するためです (ただし、 を使用してこれを回避できたはずですHashMap<Integer, Double>) 。

これは HashMap#get が行っていることです-forループは、テーブルがバッキング配列の同じインデックスにハッシュされた複数のキーを格納している場合のためのものです (パフォーマンス テストではおそらく起こらなかったことであり、ループのみを意味します) 1回の反復を実行します）

for (Entry<K,V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) {
    Object k;
    if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
        return e.value;
}
于 2013-05-01T21:55:24.757 に答える