RecursiveTask 如何计算斐波那契数列？

Question

我正在查看 RecursiveTask 计算斐波那契数的经典示例。我添加了一些输出：见http://jboston.net/2017/FibonacciOutp.txt，代码如下

仍然无法理解这是如何工作的，为什么首先我们看到所有数字都从 12 开始减少，然后重复多次

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

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

代码：

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

当调用FibonacciCal::compute时，它分出一个线程来计算fib(n - 1)，并在起始线程中计算fib(n - 2)。分支看起来有点像这样（fib(n)代表一个线程运行 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

你得到很多重复数字的原因是没有任何记忆。在这个使用 fib(5) 的示例中，您会看到 fib(0) 或 fib(1) 的 8 个基本术语、fib(2) 的 3 个术语、fib(3) 的 2 个术语和一个 fib(4)。随着低阶项开始加入它们的 children 你会得到很多带有小 nums 的 printlns，直到结束并且它们开始倒计时。

RecursiveTask 如何计算斐波那契数列？

How RecursiveTask works for calculating Fibonacci numbers?

recursion

java-8

fork-join