Schlechte dynamische Programmierung Implementierung oder HashMap Slow?

Question

Ich habe zwei Fibonacci-Methoden, die ich gerade ausprobiere. Beide sollten linear sein. Entweder verstehe ich Memoization nicht oder HashMap-Lookups sind langsamer als ich dachte.

Ich verstehe, dass die rekursive Funktion nicht viel durch die Hinzufügung von DP beschleunigt werden sollte, aber da es statisch ist, muss es nur einmal berechnet werden (fällt nie aus dem Geltungsbereich). Nach der ersten Ausführung ruft es die Antwort von der HashMap ab.

Ich mache dies in Vorbereitung für die Implementierung der O (Log n) Fibonacci-Funktion und Benchmarking, aber ich habe ein wenig umgeleitet, als ich das sah. (Sogar eine zusätzliche Memoisierung zu dem iterativen Ansatz verlangsamt es).

Bitte erleuchte mich, ich fühle mich im Moment ziemlich dumm.

iterativen Ansatz:

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; 
    }  
} 

rekursive Ansatz:

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; 
    } 
} 

Und ein Unit-Test:

@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"); 
} 

Returns:

Iterative approach took 6ms 
Recursive approach took 132ms 

Answer 1

Erstens ist Rekursion in Java langsamer als Iteration.

Anstatt zu tun enthält und dann bekommen, warum nicht einfach einen Null-Check machen und tun? Hash und Bucket müssen zweimal berechnet werden, nicht sicher, wie groß der Perfusion ist.

Autoboxieren. Es könnte eine gute Idee sein, eine externe Lib mit primitiven Maps, wie Gnu Trove, zu verwenden. Nicht sicher, was die Perf-Verstärkung ist, aber Sie werden viel weniger Objekte zuweisen.

Es könnte auch eine gute Idee sein, zu überprüfen, ob die Perf-Messung korrekt ist. Sind im rekursiven Fall die ersten oder ersten Iterationen viel langsamer als der Rest? Der Mittelwert ist möglicherweise kein gutes Maß. Wäre schön, ein Latenz-Histogramm zu haben.