Fork/Join Implementation

[Default]

Hallo zusammen!

Ich habe eine Frage und zwar zu folgendem Code, bei welchem ich die maximale Summe eines arrays ausrechnen möchte:

import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveTask;

public class MaxSubArraySum extends RecursiveTask<Integer> {
    private static final long serialVersionUID = 1L;
    int start;
    int length;
    int[]input;
    final int CUTOFF;
    
    public MaxSubArraySum(int start, int length, int[] input, int CUTOFF) {
        this.CUTOFF = CUTOFF;
        this.start = start;
        this.length = length;
        this.input = input;
    }
    
    
    public static class MaxSumHelper {

        public static Integer MaximumSum(int[] input, int start, int i) {
            int max = 0;
            for (int j = 0; j < input.length-1; j++) {
                if (input[i] + input[i + 1] > input[i]) {
                    max = input[i] + input[i + 1];
                }
            }
            return max;
        }
    }

    @Override
    public Integer compute() {
        
        if (length <= CUTOFF) {
            return MaxSumHelper.MaximumSum(input, start, input.length);
        }
        
        
        // Split work:
        int mid = length / 2;
        MaxSubArraySum lm = new MaxSubArraySum(start, mid, input, CUTOFF);
        MaxSubArraySum rm = new MaxSubArraySum(start+mid, length, input, CUTOFF);

        // Run subtasks:
        lm.fork();
        int max2 = rm.compute();
        
        // Find maximum subarray sum crossing right middle border
        int rightMax = 0;
        int sumright = 0;
        for (int i = start+mid; i < input.length-1; i++) {
            sumright += input[i];
            if(sumright > rightMax)
                rightMax = sumright;
        }
        
        // Find maximum subarray sum crossing left middle border
                int leftMax = 0;
                int sumleft = 0;
                for (int i = start+mid - 1; i >= start; i--) {
                    sumleft += input[i];
                    if(sumleft > leftMax)
                        leftMax = sumleft;
                }

        // Combine results:
        try {
            return Math.max(leftMax + rightMax, Math.max(lm.join(), max2));
        } catch (Exception e) {
            return 0;
        }
    
    }
    
    public static void main(String[] args) {
            int[]input = new int[]{2,-4,1,9,-6,7,-3};
            MaxSubArraySum top = new MaxSubArraySum(0, input.length, input, 4);
            ForkJoinPool maxsum = new ForkJoinPool();
            int result = maxsum.invoke(top);       
            try {
                System.out.println(result);
            } catch (Exception e) {
            }
        }
    }

Beim compile erhalte ich folgenden Error bei der Konsole:

Exception in thread "main" java.lang.StackOverflowError
    at java.base/jdk.internal.reflect.NativeConstructorAccessorImpl.newInstance0(Native Method)
    at java.base/jdk.internal.reflect.NativeConstructorAccessorImpl.newInstance(NativeConstructorAccessorImpl.java:62)
    at java.base/jdk.internal.reflect.DelegatingConstructorAccessorImpl.newInstance(DelegatingConstructorAccessorImpl.java:45)
    at java.base/java.lang.reflect.Constructor.newInstance(Constructor.java:490)
    at java.base/java.util.concurrent.ForkJoinTask.getThrowableException(ForkJoinTask.java:603)
    at java.base/java.util.concurrent.ForkJoinTask.reportException(ForkJoinTask.java:678)
    at java.base/java.util.concurrent.ForkJoinTask.join(ForkJoinTask.java:722)
    at java.base/java.util.concurrent.ForkJoinPool.invoke(ForkJoinPool.java:2423)
    at ForkJoin.MaxSubArraySum.main(MaxSubArraySum.java:82)
Caused by: java.lang.StackOverflowError

Was mache ich falsch?

Ich hoffe mir kann jemand weiterhelfen...

Grüsse

Default

 

[VfL_Freak]

Moin,

Du zerschießt Dir den Speicher, weil Du irgendwas zu oft (vermutlich endlos) ausrufst!
Es passiert (so wie die Fehlermeldung besagt) genau hier:
at ForkJoin.MaxSubArraySum.main(MaxSubArraySum.java:82)
Allerdings wissen wir nicht, welche Zeile das ist!

Zudem sind Deine Aufrufe mit den verschachtelten Klassen so adhoc (und ohne Kommentare deinerseits) nur schwer nachvollziehbar!
VG Klaus

 

[kneitzel]

Also was erst einmal auffällt:

        public static Integer MaximumSum(int[] input, int start, int i) {
            int max = 0;
            for (int j = 0; j < input.length-1; j++) {
                if (input[i] + input[i + 1] > input[i]) {
                    max = input[i] + input[i + 1];
                }
            }
            return max;
        }

Dies sieht sehr dubios aus.
a) Du hast eine Schleife mit j, aber j verwendest Du nicht. i ist auch konstant. Daher ist die ganze for Scheife für die Tonne und kann durch ein if ersetzt werden. (0 < input.length - 1)
b) Dann in der vorhandenen if Bedingung prüfst Du nur, ob input[i+1] >0 ist. Das ist bestimmt nicht Dein Wunsch. Da soll bestimmt > max geprüft werden!


Dann das nächste, das auffällt:

        MaxSubArraySum lm = new MaxSubArraySum(start, mid, input, CUTOFF);
        MaxSubArraySum rm = new MaxSubArraySum(start+mid, length, input, CUTOFF);

Der zweite Parameter ist doch die länge und nicht das Endelement!
Wenn du 4 Elemente hast, dann ist die Länge der beiden Teile 2 und nicht 2 und 4!

Das wäre erst einmal, was mir so auffällt. Aber Dein Code ist so nicht wirklich nachvollziehbar, d.h. es kann durchaus sein, dass z.B. der letzte Punkt vom Aufruf her korrekt ist und Du nur die Parameter / Variablen schlecht benannt hast.

 

[Default]

Moin,

Du zerschießt Dir den Speicher, weil Du irgendwas zu oft (vermutlich endlos) ausrufst!
Es passiert (so wie die Fehlermeldung besagt) genau hier:
at ForkJoin.MaxSubArraySum.main(MaxSubArraySum.java:82)
Allerdings wissen wir nicht, welche Zeile das ist!

Zudem sind Deine Aufrufe mit den verschachtelten Klassen so adhoc (und ohne Kommentare deinerseits) nur schwer nachvollziehbar!
VG Klaus

Vielen Dank für deine Hilfe! Das Problem lag beim Aufruf von:
MaxSubArraySum rm = new MaxSubArraySum(start+mid, length, input, CUTOFF);
sollte so sein:
MaxSubArraySum rm = new MaxSubArraySum(start+mid, length-mid, input, CUTOFF);

 

[Default]

Also was erst einmal auffällt:

        public static Integer MaximumSum(int[] input, int start, int i) {
            int max = 0;
            for (int j = 0; j < input.length-1; j++) {
                if (input[i] + input[i + 1] > input[i]) {
                    max = input[i] + input[i + 1];
                }
            }
            return max;
        }

Dies sieht sehr dubios aus.
a) Du hast eine Schleife mit j, aber j verwendest Du nicht. i ist auch konstant. Daher ist die ganze for Scheife für die Tonne und kann durch ein if ersetzt werden. (0 < input.length - 1)
b) Dann in der vorhandenen if Bedingung prüfst Du nur, ob input[i+1] >0 ist. Das ist bestimmt nicht Dein Wunsch. Da soll bestimmt > max geprüft werden!


Dann das nächste, das auffällt:

        MaxSubArraySum lm = new MaxSubArraySum(start, mid, input, CUTOFF);
        MaxSubArraySum rm = new MaxSubArraySum(start+mid, length, input, CUTOFF);

Der zweite Parameter ist doch die länge und nicht das Endelement!
Wenn du 4 Elemente hast, dann ist die Länge der beiden Teile 2 und nicht 2 und 4!

Das wäre erst einmal, was mir so auffällt. Aber Dein Code ist so nicht wirklich nachvollziehbar, d.h. es kann durchaus sein, dass z.B. der letzte Punkt vom Aufruf her korrekt ist und Du nur die Parameter / Variablen schlecht benannt hast.

Vielen Dank für deine Hilfe! Ja bei der Iteration ging was schief da ich die Schleife automatisch durch Eclipse erstellen lies und i bereits in der Methode definiert wurde...habe ich abgeändert! Lag wirklich an den Parametern wie du gesagt hast. Hab ich so abgeändert und alles funktioniert nun: MaxSubArraySum rm = new MaxSubArraySum(start+mid, length-mid, input, CUTOFF);
Vielen Dank!