OutOfMemoryError

[DrPils]

Hi

Nach jedem aufruf von Evolve wird der Zustand eines Fisches um 1 veringert.
Ist der Zustand -1 bekommt er Nachwuchs mit dem Zustand 8 und der eigene Zustand wird auf 6 gesetzt.

Day 6 - Advent of Code 2021

adventofcode.com

Eine Liste von Fischen mit ihrem Start Zustand ist bereits gegeben. Ziel ist es die Population nach x Tagen zu berechnen.

Mit 256 Tagen bekomme ich aber einen OutOfMemoryError in der LaternFishGroup.evolve() Methode.

public class LanternFish {

    private int state;

    public LanternFish(int state) {
        this.state = state;
    }

    public Optional<LanternFish> evolve() {
        if (--state < 0) {
            state = 6;
            return Optional.of(new LanternFish(8));
        }
        return Optional.empty();
    }
}

public class LanternFishGroup {

    private List<LanternFish> fishes;

    public LanternFishGroup(List<Integer> initialStates) {
        fishes = initialStates.stream()
                .map(LanternFish::new)
                .toList();
    }

    public void evolve() {
        List<LanternFish> nextGen = new ArrayList<>(fishes);
        for (LanternFish fish : fishes) {
            Optional<LanternFish> evolve = fish.evolve();
            evolve.ifPresent(nextGen::add);
        }
        fishes = nextGen;
    }

    public int countOfFishes() {
        return fishes.size();
    }
}

public class LanternFishPopulation {

    private LanternFishGroup fishGroup;

    public LanternFishPopulation(String path) {
        List<Integer> initialStates = FileUtils.stringStreamFromRessourceFile(path)
                .flatMap(s -> Arrays.stream(s.split(",")))
                .map(Integer::parseInt)
                .toList();

        fishGroup = new LanternFishGroup(initialStates);
    }

    public int challenge1() {
        for (int i = 0; i < 80; i++) {
            fishGroup.evolve();
        }
        return fishGroup.countOfFishes();
    }

    public int challenge2() {
        for (int i = 0; i < 256; i++) {
            fishGroup.evolve();
        }
        return fishGroup.countOfFishes();
    }
}

[CODE title="input"]4,1,4,1,3,3,1,4,3,3,2,1,1,3,5,1,3,5,2,5,1,5,5,1,3,2,5,3,1,3,4,2,3,2,3,3,2,1,5,4,1,1,1,2,1,4,4,4,2,1,2,1,5,1,5,1,2,1,4,4,5,3,3,4,1,4,4,2,1,4,4,3,5,2,5,4,1,5,1,1,1,4,5,3,4,3,4,2,2,2,2,4,5,3,5,2,4,2,3,4,1,4,4,1,4,5,3,4,2,2,2,4,3,3,3,3,4,2,1,2,5,5,3,2,3,5,5,5,4,4,5,5,4,3,4,1,5,1,3,4,4,1,3,1,3,1,1,2,4,5,3,1,2,4,3,3,5,4,4,5,4,1,3,1,1,4,4,4,4,3,4,3,1,4,5,1,2,4,3,5,1,1,2,1,1,5,4,2,1,5,4,5,2,4,4,1,5,2,2,5,3,3,2,3,1,5,5,5,4,3,1,1,5,1,4,5,2,1,3,1,2,4,4,1,1,2,5,3,1,5,2,4,5,1,2,3,1,2,2,1,2,2,1,4,1,3,4,2,1,1,5,4,1,5,4,4,3,1,3,3,1,1,3,3,4,2,3,4,2,3,1,4,1,5,3,1,1,5,3,2,3,5,1,3,1,1,3,5,1,5,1,1,3,1,1,1,1,3,3,1[/CODE]

Kann ich den Code irgendwie Effizienter gestalten?

 

[kneitzel]

Da immer nur Fische hinzu kommen, ist dadurch das OutOfMemory erklärt. Speicherbedarf geht Richtung 2^n. (Verdoppelung alle 6 Zyklen so ich das richtig verstanden habe. Erste Teilung erst nach 8 Zyklen, aber danach immer nur 6.) Das erklärt das OutOfMemory.

Eine Optimierung ist denkbar - statt zwei mal das ganze Array zu halten könnte man in evolve einfach nur eine ArrayList mit neuen Elementen füllen und dann am Ende diese Elemente mittels addAll hinzu fügen. Aber das ist eine Optimierung die nur minimal Auswirkung zeigt.

Zusätzlich kann man Java beim Start mehr Speicher zusprechen. Aber auch der Effekt bringt nur geringfügig etwas - denn mit der ständigen verdoppelung des Fischbestandes ist es auch nur so, dass man da relativ wenig an Durchläufen gewinnt. Verdoppelung des Speichers bringt vermutlich also nur um 6 Durchläufe mehr.

 

[LimDul]

Aus dem Bauch heraus - da nur nach der Anzahl der Fische nach X Tagen gefragt ist, interessiert der individuelle Fisch nicht.

Ergo brauch ich nur 8 Zahlen - die Anzahl der Fische mit dem jeweiligen Timer-Ständen (0-8).

 

[DrPils]

Aus dem Bauch heraus - da nur nach der Anzahl der Fische nach X Tagen gefragt ist, interessiert der individuelle Fisch nicht.

Ergo brauch ich nur 8 Zahlen - die Anzahl der Fische mit dem jeweiligen Timer-Ständen (0-8).

Gute Punkt.
Ich habe es mal dementsprechend abgeändert:

public class LanternFishGroup {

    private Map<Integer, Long> fishes;

    public LanternFishGroup(List<Integer> initialStates) {
        fishes = new HashMap<>(initialStates.stream()
                .map(LanternFish::new)
                .collect(Collectors.groupingBy(LanternFish::getState, Collectors.counting()))
        );
    }

    public void evolve() {

        Map<Integer, Long> nextGen = new HashMap<>();
        for (Integer integer : fishes.keySet()) {
            nextGen.put(integer - 1, fishes.get(integer));
        }
        if (nextGen.get(-1) != null) {
            Long currentFishesOn6 = nextGen.getOrDefault(6, 0L);
            nextGen.put(8, nextGen.get(-1));
            nextGen.put(6, nextGen.get(-1) + currentFishesOn6);
            nextGen.remove(-1);
        }

        fishes = nextGen;
    }

    public long countOfFishes() {
        return fishes.values().stream()
                .mapToLong(Long::longValue)
                .sum();
    }
}

Performance ist jetzt 1A
Jedoch stimmt es noch nicht ganz/
TestInput: 3,4,3,1,2

Durchläufe	Erwarteter Wert	Tatsächlicher Wert
80	5934	5934
256	26.984.457.539	28.671.831.483.421

Bei 80 durchlaufen stimmt es noch, bei 256 aber nicht.
Ich habe es zwischenzeitlich es auch mal mit BigInteger probiert, das Ergebniss bleibt aber das gleiche.

 

[LimDul]

Long sollte eigentlich reichen, das geht bis 18 Stellen, da sind nur 14. Aus dem Bauch heraus sehe ich keinen Fehler. Kannst du mal schauen, ob du den erwarteten Wert nach 257 Durchläufen triffst? Eigentlich sehe ich keinen Grund, warum bei 80 das richtige, aber bei 256 das falsche rauskommt, sofern nicht irgendwo bei der Übernahme der 256 ein "1-daneben" Fehler aufgetreten ist.

 

[DrPils]

   public void evolve() {
        long[] tempArray = fishArray.clone();
        for (int i = 0; i < tempArray.length; i++) {
            tempArray[i] = fishArray[ (i + 1) % 9  ];
        }
        tempArray[6] += tempArray[8];
        fishArray = tempArray;
    }

Habe den Code nochmal abgeändert, ich den es ist so sauberer.

Der Fehler war aber, dass ich für beide durchlaufe das gleiche Objekt genutzt habe .
Dann war das halt das ergebniss von 80 + 256 Tage...