Hashmap Memoization langsamer als direkt die Antwort zu berechnen

Question

Ich habe mit den Project Euler Herausforderungen gespielt, um meine Kenntnisse über Java zu verbessern. Insbesondere habe ich den folgenden Code für geschrieben, der Sie auffordert, die längste Collatz-Kette zu finden, die bei einer Zahl unter 1.000.000 beginnt. Es geht davon aus, dass es unwahrscheinlich ist, dass Subketten mehr als einmal entstehen, und indem sie in einem Cache gespeichert werden, werden keine redundanten Berechnungen durchgeführt.

Collatz.java:

import java.util.HashMap; 

public class Collatz { 
    private HashMap<Long, Integer> chainCache = new HashMap<Long, Integer>(); 

    public void initialiseCache() { 
     chainCache.put((long) 1, 1); 
    } 

    private long collatzOp(long n) { 
     if(n % 2 == 0) { 
      return n/2; 
     } 
     else { 
      return 3*n +1; 
     } 
    } 

    public int collatzChain(long n) { 
     if(chainCache.containsKey(n)) { 
      return chainCache.get(n); 
     } 
     else { 
      int count = 1 + collatzChain(collatzOp(n));  
      chainCache.put(n, count); 
      return count; 
     } 
    } 
} 

ProjectEuler14.java:

public class ProjectEuler14 { 
    public static void main(String[] args) { 
     Collatz col = new Collatz(); 

     col.initialiseCache(); 
     long limit = 1000000; 

     long temp = 0; 
     long longestLength = 0; 
     long index = 1; 

     for(long i = 1; i < limit; i++) { 
      temp = col.collatzChain(i); 
      if(temp > longestLength) { 
       longestLength = temp; 
       index = i; 
      } 
     } 
     System.out.println(index + " has the longest chain, with length " + longestLength); 
    } 
} 

Dies funktioniert. Und nach dem Befehl "measure-command" von Windows Powershell dauert es ungefähr 1708 Millisekunden (1.708 Sekunden), um auszuführen.

Nach dem Lesen durch die Foren bemerkte ich jedoch, dass einige Leute, die scheinbar naiven Code geschrieben hatten, die jede Kette von Grund auf neu berechnen, viel bessere Ausführungszeiten als ich bekommen. Ich habe (konzeptuell) eine der Antworten, und übersetzt es in Java:

NaiveProjectEuler14.java:

public class NaiveProjectEuler14 { 
    public static void main(String[] args) { 
     int longest = 0; 
     int numTerms = 0; 
     int i; 
     long j; 

     for (i = 1; i <= 10000000; i++) { 
      j = i; 
      int currentTerms = 1; 

      while (j != 1) { 
       currentTerms++; 

       if (currentTerms > numTerms){ 
        numTerms = currentTerms; 
        longest = i; 
       } 

       if (j % 2 == 0){ 
        j = j/2; 
       } 
       else{ 
        j = 3 * j + 1; 
       } 
      } 
     } 
     System.out.println("Longest: " + longest + " (" + numTerms + ")."); 
    } 
} 

Auf meinem Rechner das gibt auch die richtige Antwort, aber es gibt es in 0.502 Millisekunden - ein Drittel der Geschwindigkeit meines ursprünglichen Programms. Zuerst dachte ich, dass es vielleicht einen kleinen Overhead bei der Erstellung einer HashMap geben würde, und dass die Zeiten zu klein waren, um irgendwelche Schlüsse zu ziehen. Wenn ich jedoch in beiden Programmen den oberen Grenzwert von 1.000.000 auf 10.000.000 erhöhe, benötigt NaiveProjectEuler14 4709 Millisekunden (4.709 Sekunden), während ProjectEuler14 unglaubliche 25324 Millisekunden (25.324 Sekunden) benötigt!

Warum dauert ProjectEuler14 so lange? Die einzige Erklärung, die ich ergründen kann, ist, dass das Speichern großer Mengen von Paaren in der HashMap-Datenstruktur einen enormen Aufwand verursacht, aber ich kann nicht verstehen, warum dies der Fall sein sollte. Ich habe auch versucht, die Anzahl der Paare (Schlüssel, Wert), die im Laufe des Programms gespeichert wurden (2.168.611 Paare für den 1.000.000 Fall und 21.730.849 Paare für den 10.000.000 Fall), aufzuzeichnen und dem HashMap-Konstruktor ein wenig über diese Zahl zu liefern dass es sich höchstens einmal selbst ändern muss, aber das scheint die Ausführungszeiten nicht zu beeinflussen.

Hat jemand Gründe dafür, warum die Memo-Version viel langsamer ist?

Answer 1

Es gibt einige Gründe für diese bedauerliche Realität:

• Statt containsKey, sofort tun bekommen und prüfen, ob null
• Der Code verwendet eine zusätzliche Methode
• Die Karte speichert gewickelt aufgerufen werden Objekte (Integer, Long) für primitive Typen
• Der JIT-Compiler, der Bytecode in Maschinencode übersetzt, kann mehr mit Berechnungen tun
• Das Zwischenspeichern betrifft keinen großen Prozentsatz, wie Fibonacci würde

vergleichbar

public static void main(String[] args) { 
    int longest = 0; 
    int numTerms = 0; 
    int i; 
    long j; 

    Map<Long, Integer> map = new HashMap<>(); 

    for (i = 1; i <= 10000000; i++) { 
     j = i; 

     Integer terms = map.get(i); 
     if (terms != null) { 
      continue; 
     } 
     int currentTerms = 1; 

     while (j != 1) { 
      currentTerms++; 

      if (currentTerms > numTerms){ 
       numTerms = currentTerms; 
       longest = i; 
      } 

      if (j % 2 == 0){ 
       j = j/2; 

       // Maybe check the map only here 
       Integer m = map.get(j); 
       if (m != null) { 
        currentTerms += m; 
        break; 
       } 
      } 
      else{ 
       j = 3 * j + 1; 
      } 
     } 
     map.put(j, currentTerms); 
    } 
    System.out.println("Longest: " + longest + " (" + numTerms + ")."); 
} 

wirklich Dies keine ausreichende memoization tun.Bei steigenden Parametern verringert die Überprüfung der 3*j+1 nicht die Fehler (kann aber auch meoisierte Werte überspringen).

Memoization lebt von schwerer Berechnung pro Anruf. Wenn die Funktion wegen tiefer Rekursion und nicht wegen Berechnung lange dauert, wird der Memo-Overhead pro Funktionsaufruf negativ gezählt.