pp.12.01-ForkJoinArrayFilter

in-situ Filterung als divide and conquer

• Projekt: pp.12.01-ForkJoinArrayFilter
• Bearbeitungszeit: 25 Minuten
• Musterlösung: 15 Minuten
• Kompatibilität: mindestens Java SE 10

 

• Das Fork-Join Framework eignet sich besonders gut zur Implementierung von Array-Algorithmen.
• Alle Werte eines Arrays mit MAX überschreiben, die > MAX sind.
• Das Array soll halbiert werden, bis \(\le\) 4 Elemente übrig sind, wie in folgendem Schaubild:

Hettel und Tran (2016, 191 (modifiziert))

Quellcode von pp.FilterTask

public class FilterTask extends RecursiveAction {

    private static final int ARRAY_LEN = 16;
    private static final int SLICE_LEN = 4;
    private static final int MAX = 10;
    private static int instanceCounter = 0;

    private final ArrayList<Integer> array;
    private final int start;
    private final int end;

    FilterTask(ArrayList<Integer> array, int start, int end) {
        this.array = array;
        this.start = start;
        this.end = end;
        synchronized(FilterTask.class) {
            FilterTask.instanceCounter++;
        }
    }

    @Override
    protected void compute() {

        // Fallunterscheidung einführen, die prüft, ob weiter rekursiv halbiert
        // werden muss oder ob nun der Rekursionsanker erreicht ist

        // Rekursionsanker: über Array-Elemente mit einer for-Schleife iterieren
        // und Filter-Aktion anwenden (muss noch implementiert werden)

        // Array in zwei Hälften aufteilen und beide Hälften rekursiv behandeln:
        var mid = this.start + ((this.end - this.start) / 2);
        var left = new FilterTask(this.array, this.start, mid);
        var right = new FilterTask(this.array, mid, this.end);
        left.fork();
        right.fork();
        right.join();
        left.join();
    }

    public static void main(String... args) {
        // Array initialisieren

        // initialen FilterTask erzeugen und
        // FilterTask im *Common Thread Pool* starten:
        // ForkJoinPool.commonPool().invoke(...);

        // auf das Ende warten
        // gefiltertes Array ausgeben
    }
}

Aufgaben

• Vervollständigen Sie die Methode compute:
  • führen Sie eine neue Fallunterscheidung ein, die prüft, ob weiter rekursiv halbiert werden muss oder ob nun der Rekursionsanker erreicht ist (das Array soll halbiert werden, bis \(\le\) 4 Elemente übrig sind).
  • implementieren Sie die Aktion für den Rekursionsanker: Iterieren Sie dazu mit einer for-Schleife über die Array-Elemente und wenden Sie auf jedes Element die Filter-Aktion an (Element mit MAX überschreiben, falls Element \(>\) MAX ist.)
• Schreiben Sie ein Hauptprogramm, mit dem Sie den FilterTask im Common Thread Pool ausprobieren.
• Wie oft wird bei einem Array mit \(n\) Elementen geforkt?

Literatur

Hettel, Jörg und Manh Tien Tran. 2016. Nebenläufige Programmierung mit Java. Konzepte und Programmiermodelle für Multicore-Systeme. Heildelberg: dpunkt.verlag.