Hofstadterfolge mit Cache

[javaschmava]

public class Hofstadter
{
    public int q (int n)
    {
        return (n < 3) ? 1: q(n - q (n - 1)) + q (n - q (n - 2));
    }
}
import java.util.HashMap;
public class HofstadterCache extends Hofstadter
{
    private static final HashMap<Integer, Integer> cache = new HashMap<>();
    public int q(int n)
    {
        Integer result = cache.get(n);
        if (result == null)
        {
            result = super.q(n);
            cache.put(n, result);
        }
        return result;
    }
    public static void main(String[] args)
    {
        HofstadterCache h = new HofstadterCache();
        System.out.println(h.q(10000000));
    }
}

Moin,
ich soll das zehnmillionste Folgenglied der Hofstadterfolge berechnen.
Da aber durch die Rekursion sich der Stack zu schnell auffüllt, sollte ich einen Cache implementieren, um sich vorherige Ergebnisse zu merken. Allerdings klappt das ganze trotzdem irgendwie nicht und ich bekomme einen StackOverflowError, obwohl ich das genauso mache wie es in meinem Buch beschrieben ist.
Könnte jemand erklären, was da los ist?
Danke und viele Grüße

 

[KonradN]

Die Stackgröße ist per default nur 1MB und das ist sehr wenig, denn Du hast da ja 2*(n-2) Aufrufe. Da kommst Du schnell in die Grenzen.
(Auf den Stack kommen ja mindestens Ergebnis, Rücksprungadresse, Parameter, und lokale Variablen. Also ein Minimum von 16 Byte so dass 2 * 10_000_000 * 16 sind also schon 320 MB an Stack, der hier benötigt würde, wenn man irgendwelche Java spezifischen Dinge weglassen würde)

Ein direkter Aufruf der Berechnung statt dem super.q(n) Aufruf würde den Bedarf übrigens bereits halbieren ...

VM Option -Xss kann natürleich eine andere Größe setzen, aber unter Windows konnte ich nicht mehr wie 1G setzen und das dürfte zu wenig sein.

Daher evtl. den super.q Aufruf weglassen und statt dessen die Logik in die Methode aufnehmen. Das zusammen mit -Xss1G Option schafft die Berechnung dann ...

Edit: Der Platzbedarf ist nur überschlagen mit den Typen, die man gesehen hat. Evtl. einfach noch ein paar mehr Details: Die JVM legt bei Aufrufen ein Stack Frame auf den Stack. Die Rücksprungadresse kann statt 4 Byte auch 8 Byte sein. Und was immer hinzu kommt: Ein Operand Stack der 16-64 Byte ausmachen kann. Das nur als Erläuterung, wieso ein -Xss1G mit dem super Aufruf nicht funktioniert obwohl die erste grobe Schätzung niedriger war. Da ging es nur um eine grobe Abschätzung um zu zeigen, um was für Größen es geht und mit dem Operand Stack reichen die 1G nicht. Die Optimierung war daher notwendig um in den 1G zu bleiben.

 

[ByteBitch]

Sieht aus, als wurde die Frage in zwei Foren gestellt: https://forum.byte-welt.net/t/folge-a005185-in-oeis-berechnen/25981

 

[KonradN]

Sieht aus, als wurde die Frage in zwei Foren gestellt: https://forum.byte-welt.net/t/folge-a005185-in-oeis-berechnen/25981

Nein, da ist nur das Grundthema gleich aber nicht die Fragestellung selbst. Hier wurde der rekursive Ansatz lediglich durch einen Cache ergänzt. In dem byte-forum Beitrag wird ein array aufgebaut, das komplett gefüllt wird um dann den letzten Wert zu nutzen. Dabei ist das Array mit n+2 schlicht um eins zu gross. Wenn man von 1...n Felder haben will, dann reicht ein Array n+1 aus.