Comment RecursiveTask fonctionne pour calculer les nombres de Fibonacci?

Question

Je regarde l'exemple classique pour RecursiveTask calculant des nombres de Fibonacci. Je glissai sortie: voir http://jboston.net/2017/FibonacciOutp.txt, le code est ci-dessous

ne comprends toujours pas comment cela fonctionne, pourquoi d'abord, nous voyons tous les nombres diminuant de 12, puis de répéter plusieurs fois

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

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

Le 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

Lorsque FibonacciCal::compute est appelé, il fend un fil pour calculer fib(n - 1) et calcule fib(n - 2) dans le thread de départ. La ramification ressemble un peu à ce (fib(n) représente un fil conducteur 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 

La raison pour laquelle vous obtenez beaucoup de chiffres répétitifs est parce qu'il n'y a pas de memoization. Dans cet exemple avec fib(5), vous voyez que vous obtenez 8 termes de base de fib(0) ou fib(1), 3 termes de fib(2), 2 de fib(3) et un fib(4). A mesure que les termes inférieurs commencent à rejoindre leurs enfants, vous obtenez beaucoup d'imprimés avec de petits num, jusqu'à la fin et ils recommencent à compter.