用Fork And Join框架计算Fibonacci数列

发表于 | | 阅读次数

Fork And Join 的并发框架对与大型任务的分解计算是十分方便的。主要是将任务分割（fork）最后再合并（join）得到结果。
实际上使用了分治的思想。其中涉及到任务窃取算法等。

以下是一个计算Fibonacci数列的Demo,使用BigInteger是为了避免溢出，但是计算效率大大降低，可以用Long类型代替。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
package com.tw;
import java.math.BigInteger;
import java.util.HashMap;
import java.util.Map;
import java.util.concurrent.RecursiveTask;
/**
 * Created by Rick on 2017/2/27.
 */
public class ForkAndJoinTest extends RecursiveTask<BigInteger> {
    private int num;
    private Map<BigInteger, BigInteger> intermediateResult;
    public ForkAndJoinTest(int num, Map<BigInteger, BigInteger> map) {
        this.num = num;
        intermediateResult = map;
    }
    @Override
    protected BigInteger compute() {
        if (num == 2)
            return BigInteger.valueOf(1);
        if (num == 1)
            return BigInteger.valueOf(1);
        if (num == 0)
            return BigInteger.valueOf(0);
        BigInteger lr, rr;
        int i = num - 1;
        int i1 = num - 2;
        lr = getBigInteger(i);
        rr = getBigInteger(i1);
        return lr.add(rr);
    }
    /**
    * 使用map缓存计算结果
    */
    private BigInteger getBigInteger(int i) {
        BigInteger lr;
        if (null != intermediateResult.get(i))
            lr = intermediateResult.get(i);//cacha number
        else {
            ForkAndJoinTest join1 = new ForkAndJoinTest(i, intermediateResult);
            join1.fork();
            lr = join1.join();
            intermediateResult.put(BigInteger.valueOf(i), lr);
        }
        return lr;
    }
    public ForkAndJoinTest() {
    }
    public static void main(String[] args) {
//        1,1,2,3,5,8,13,21
        Map<BigInteger, BigInteger> map = new HashMap<>();
        for (int i = 0; i < 90; i++) {
            ForkAndJoinTest faj = new ForkAndJoinTest(i, map);
			ForkJoinPool pool = new ForkJoinPool();
			BigInteger rs = pool.invoke(faj);
            System.out.println("#" + i + " " + rs);
        }
    }
}

举一反三，例如计算1+2+…+n就可以使用这种多线程模型，假设1+2比较耗时的话。