ダイナミックプログラミングの実装が不良か、HashMapが遅いですか？

Question

私はテストしている2つのフィボナッチメソッドを持っています。どちらも線形でなければなりません。私はメモやHashMapのルックアップが私が思ったよりも遅いことを理解していません。

私は、DPを追加することで再帰関数を大きくするべきではないことを理解していますが、静的なので一度だけ計算する必要があります（スコープから外れることはありません）。最初の実行後、HashMapから回答を取得します。

私はO（log n）フィボナッチ関数とベンチマークを実装するための準備としてこれをやっていますが、これを見て少し迂回しました。 （反復的なアプローチへの追加のメモも、それを遅くする）。

私に教えてください、私は現時点ではかなり愚かだと感じています。

反復アプローチ：

public static int linearIterativeFib(int x) { 
    if (x <= 2) { 
     return 1; 
    } else { 
     int prev = 0; 
     int result = 1; 
     for (int i = 2; i <= x; i++) { 
      int temp = result; 
      result += prev; 
      prev = temp; 
     } 
     return result; 
    }  
} 

再帰的アプローチ：

static Map<Integer, Integer> memo = new HashMap<Integer, Integer>(); 

public static int linearRecursiveFib(int x) { 
    if (x <= 2) { 
     return 1; 
    } else if (memo.containsKey(x)) { 
     return memo.get(x); 
    } else { 
     int result = linearRecursiveFib(x - 1) 
       + linearRecursiveFib(x - 2); 
     memo.put(x, result); 
     return result; 
    } 
} 

とユニットテスト：

@Test 
public void testSpeed() { 
    int input = 35; 
    long start = System.currentTimeMillis(); 
    for (int i = 0; i < 10000000; i++) { 
     fib.linearIterativeFib(input); 
    } 
    System.out.println("Iterative approach took " 
      + (System.currentTimeMillis() - start) + "ms"); 

    start = System.currentTimeMillis(); 
    for (int i = 0; i < 10000000; i++) { 
     fib.linearRecursiveFib(input); 
    } 
    System.out.println("Recursive approach took " 
      + (System.currentTimeMillis() - start) + "ms"); 
} 

戻り値：

Iterative approach took 6ms 
Recursive approach took 132ms 

Answer 1

まず、Javaの再帰は反復よりも遅いです。

containsを実行してからgetするのではなく、単にヌルチェックを取得して実行するのはなぜですか？ハッシュとバケットは2回計算する必要がありますが、パーフォーマンスがどの程度大きいかはわかりません。

オートボクシング。 gnu Troveのようなプリミティブマップを使って外部のlibを使うことは良い考えです。パーフォーマンスがどうなるかわからないが、オブジェクトをもっと少なく割り当てる。

perf測定が健全であるかどうかを確認することもよいでしょう。再帰的なケースでは、最初の、または最初のいくつかの反復の方が残りの部分よりも遅くなりますか？平均値は良い測定値ではないかもしれません。レイテンシのヒストグラムを持つのはいいですね。