Wie funktioniert RecursiveTask zur Berechnung von Fibonacci-Zahlen?

Question

Ich betrachte das klassische Beispiel für RecursiveTask Berechnung von Fibonacci-Zahlen. Ich habe eine Ausgabe: siehe http://jboston.net/2017/FibonacciOutp.txt, der Code unten

ist, kann immer noch nicht verstehen, wie dies funktioniert, warum zuerst sehen wir alle Zahlen von 12 abnehmen und dann viele Male

Nummer = 2 fcal1.join Wiederholung() (= 1 fcal2.compute) = 0

number = 3 fcal1.join() = 1 fcal2.compute() = 1

der Code:

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

public class RecursiveTaskDemo { 
public static void main(String[] args) { 
    FibonacciCal fibonacciCal = new FibonacciCal(12); 
    ForkJoinPool pool = new ForkJoinPool(); 
    int i = pool.invoke(fibonacciCal); 
    System.out.println(i); 
} 
} 

class FibonacciCal extends RecursiveTask<Integer> { 
private static final long serialVersionUID = 1L; 
final int num; 

FibonacciCal(int num) { 
    this.num = num; 
} 

@Override 
protected Integer compute() { 
    if (num <= 1) { 
     return num; 
    } 
    System.out.println("number=" + num); 
    FibonacciCal fcal1 = new FibonacciCal(num - 1); 
    fcal1.fork(); 
    FibonacciCal fcal2 = new FibonacciCal(num - 2); 
    int fcal1Join = fcal1.join(); 
    int fcal2Compute = fcal2.compute(); 
    System.out.println("number=" + num + " fcal1.join()=" + fcal1Join + " fcal2.compute()=" + fcal2Compute); 
    return fcal2Compute + fcal1Join; 
} 

} 

Answer 1

Bei FibonacciCal::compute wird aufgerufen, es gibt einen Thread zur Berechnung fib(n - 1) Forks ab und berechnet fib(n - 2) im Startthread. Die Verzweigung sieht ein bisschen wie diese (fib(n) einen Thread darstellt, läuft FibonacciCal(n).compute()):

STARTING WITH pool.invoke(new FibonacciCal(5)): 
fib(5) 
A BIT LATER: 
fib(5) === fib(3) // The fibcal2.compute() call, printing num = 3 
     \== fib(4) // The fibcal1.fork() call, printing num = 4 
LATER: 
fib(5) === fib(3) === fib(1) // These fib(0/1)s are base cases and will start folding the tree back up 
     |   \== fib(2) === fib(0) // Will return 1 and not fork 
     |      \== fib(1) // Will return 1 and not fork 
     \== fib(4) === fib(2) === fib(0) 
        |   \== fib(1) 
        \== fib(3) === fib(1) 
          \== fib(2) === fib(0) 
             \== fib(1) 
METHODS START RETURNING: 
fib(5) === fib(3) === 1 
     |   \== fib(2) === 1 
     |      \== 1 
     \== fib(4) === fib(2) === 1 
        |   \== 1 
        \== fib(3) === 1 
          \== fib(2) === 1 
             \== 1 
ADDITIONS START HAPPENING: 
fib(5) === fib(3) === 1 
     |   \== (1 + 1) = 2 // When a thread joins its child, it prints out its number again. 
     |       // Since the tree is now folding instead of unfolding, the printlns appear, approximately, the opposite order 
     \== fib(4) === (1 + 1) = 2 
        \== fib(3) === 1 
          \== (1 + 1) = 2 
LATER: 
fib(5) === (1 + 2) = 3 === 1 
     |    \== 2 
     \== fib(4) === 2 
        \== (1 + 2) = 3 === 1 
            \== 2 
END: 
8 === 3 === 1 
    |  \== 2 
    \== 5 === 2 
     \== 3 === 1 
       \== 2 

Der Grund, warum Sie eine Menge von sich wiederholenden Zahlen zu bekommen ist, weil es keine memoization ist. In diesem Beispiel mit fib(5) sehen Sie, dass Sie 8 Basisterme von fib(0) oder fib(1), 3 Terme fib(2), 2 von fib(3) und eine fib(4) erhalten. Da die Terme niedrigerer Ordnung beginnen, ihren Kindern beizutreten, erhalten Sie viele printlns mit kleinen num s, bis das Ende kommt und sie beginnen, rückwärts zu zählen.