WissensdatenbankPrüfungszentrum
DEDeutsch
Sprache wählen13

CKTIS / Java

RecursiveTask — eine rekursive Aufgabe mit Ergebnis

RecursiveTask<V> steht für eine Fork/Join-Aufgabe, die ein Ergebnis vom Typ V zurückgibt. Die Methode compute() beschreibt die Berechnung: Sie löst ein kleines Problem direkt oder teilt es in Teilaufgaben auf und führt deren Ergebnisse zusammen.

Version: Java SE 21; repository runtime, production runtime not attested

Syntax

class Task extends RecursiveTask<Result> {
    @Override
    protected Result compute() {
        // Replace this placeholder with a base-case return or a return that combines subtask results.
        throw new UnsupportedOperationException("Implement compute()");
    }
}

RecursiveTask<V> ist eine abstrakte Klasse aus java.util.concurrent, die ForkJoinTask<V> erweitert. Sie eignet sich für Teile-und-herrsche-Berechnungen, die ein Ergebnis vom Typ V zurückgeben. Für Aufgaben ohne Ergebnis ist RecursiveAction das Gegenstück.

RecursiveTask.compute hat die Signatur protected abstract V compute(). Eine Unterklasse implementiert den Basisfall und die Aufteilung der Arbeit. Ein direkter Aufruf von compute() ist ein gewöhnlicher Methodenaufruf: Er übermittelt die Aufgabe nicht an einen Pool. Im Beispiel startet pool.invoke(...) die Hauptaufgabe und gibt ihr Ergebnis zurück.

Ein typisches Muster ist left.fork(), ein direkter Aufruf von right.compute() und anschließend left.join(). fork() veranlasst die asynchrone Ausführung; join() wartet bei Bedarf und gibt das Ergebnis zurück. Das bedeutet nicht, dass für jede Aufgabe ein eigener Thread gestartet wird. Wartende Abhängigkeiten müssen azyklisch sein, um Deadlocks zu vermeiden.

Das Beispiel summiert disjunkte Bereiche [from, to), ohne das Array zu verändern. Der Schwellenwert 2 veranschaulicht die Aufteilung, ist aber keine Leistungsempfehlung: Zu kleine Aufgaben erhöhen den Aufwand. Vermeide blockierende Ein-/Ausgabe in solchen Berechnungen. Der Code ist für Java SE 21 vorgesehen; die Kompatibilität mit einer Produktionslaufzeit wurde nicht bestätigt.

Beispiele

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

public class RecursiveTaskDemo {
    static final class SumTask extends RecursiveTask<Long> {
        private final int[] values;
        private final int from;
        private final int to;

        SumTask(int[] values, int from, int to) {
            this.values = values;
            this.from = from;
            this.to = to;
        }

        @Override
        protected Long compute() {
            if (to - from <= 2) {
                long sum = 0;
                for (int i = from; i < to; i++) {
                    sum += values[i];
                }
                return sum;
            }
            int mid = from + (to - from) / 2;
            SumTask left = new SumTask(values, from, mid);
            SumTask right = new SumTask(values, mid, to);
            left.fork();
            long rightSum = right.compute();
            return rightSum + left.join();
        }
    }

    public static void main(String[] args) {
        int[] values = {1, 2, 3, 4, 5, 6, 7, 8};
        try (ForkJoinPool pool = new ForkJoinPool(2)) {
            System.out.println(pool.invoke(new SumTask(values, 0, values.length)));
        }
    }
}

Ergebnis

36

Der angezeigte Code und das angegebene Ergebnis wurden in einer isolierten Umgebung mit der im Prüfnachweis für genau diese Version dokumentierten Methode verifiziert.

Quellen