Java并发编程——分治编程

超、凢脫俗 2022-06-02 01:46 135阅读 0赞

分治算法是五大常用算法之一，本来不应该在这个时间写这篇博客，因为之前的线程池还没有写完，有些知识点也是需要用到的线程池的，但是架不住现在的项目里有个坑队友，名曰大乒乓，他好像是批量注册用户还是什么（暂时就先当做是批量注册吧~），反正就是很多很多用户，每个用户大概0.5秒左右的注册时间，要睡觉时我问他，你的电脑怎么还开着啊，他说在那注册用户呢，得跑一宿···几千条还是几万条，就一个主线程for循环在那跑着······所以先写个博客，也算是给他写的，看看用分治算法怎么来解决这个问题。

一、Fork/Join框架分治算法的概念：  
直接百度上搜的图片：  
流程图

Fork/Join框架直白点说，就是把一个大任务分解成若干个小任务，小任务可以继续无限的分解成小小任务、小小小任务，每个子线程处理这些分解后的任务，然后将处理完成后的结果合并，最后合并成一个完整的处理结果，然后返回结果。

二、Fork/Join框架简介  
首先我们需要一个处理任务的线程池：

ForkJoinPool pool = new ForkJoinPool();  
1  
线程池可以执行一个简单的任务：

pool.submit(Callable);
        pool.submit(Runnable);
        pool.submit(ForkJoinTask);
        pool.execute(Runnable);
        pool.execute(ForkJoinTask);

1  
2  
3  
4  
5  
因为线程池还没有写完，所以execute方法和submit方法的区别，大家有兴趣可以先在网上搜索下，我这里简单说下：  
区别1：submit方法执行后有返回值，返回任务的结果，而execute方法没有返回值。  
区别2（延伸）：submit提交的任务在线程池ThreadPoolExecutor中是不可以remove掉的，而execute提交的任务可移除（ForkJoinPool 没有reove方法）。  
区别3：其他（比如捕获异常什么的，大家自行搜索吧）

我们现在只看 pool.submit(ForkJoinTask)和pool.execute(ForkJoinTask)，他们都接收一个ForkJoinTask任务，我们来看下ForkJoinTask：  
这里写图片描述  
我们可以看到，ForkJoinTask是继承Object类的，下面还有好好多多子类，我们接着看他的子类：RecursiveTask和RecursiveAction，这也是今天我们要用到的两个任务类。

三、用小例子讲解RecursiveAction的用法  
直接上一个小demo：

public class TestTask extends RecursiveAction \{

private int start;
    private int end;
    /**
     * 分解成小任务的最小数量，也就是说，如果数量小于这个值，就不用再分解了
     */
    private static final int MAX = 5;
    
    public TestTask(int start, int end) {
        this.start = start;
        this.end = end;
    }
    
    @Override
    protected void compute() {
        //判断当前数量和MAX做对比，如果大于MAX，分解成小任务
        if (end - start > MAX) {
            int num = (start + end) / 2;
            //把当前的大任务TestTask分解成两个新的小任务testTask1和testTask2
            TestTask testTask1 = new TestTask(start, num);
            TestTask testTask2 = new TestTask(num + 1, end);
            //fork方法，分解形成小任务并执行
            testTask1.fork();
            testTask2.fork();
        } else {
            //如果满足小任务的数量（没超过MAX）
            for (int i = start; i <= end; i++) {
                System.out.println(i);
            }
        }
    }

\}  
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  
这里可能需要讲解一下，然后就直接写在注释里面了。这里值得注意一下的就是fork()方法，这是核心方法。运行代码：

public static void main(String[] args) {
        TestTask task = new TestTask(0, 20);
        ForkJoinPool pool = new ForkJoinPool();
        pool.submit(task);
    }

1  
2  
3  
4  
5  
看下log：

12-27 13:50:55.540 5068-8650/lbx.myapplication I/System.out: 16  
12-27 13:50:55.540 5068-8650/lbx.myapplication I/System.out: 17  
12-27 13:50:55.540 5068-8650/lbx.myapplication I/System.out: 18  
12-27 13:50:55.540 5068-8650/lbx.myapplication I/System.out: 19  
12-27 13:50:55.540 5068-8650/lbx.myapplication I/System.out: 20  
12-27 13:50:55.540 5068-8652/lbx.myapplication I/System.out: 11  
12-27 13:50:55.540 5068-8652/lbx.myapplication I/System.out: 12  
12-27 13:50:55.540 5068-8652/lbx.myapplication I/System.out: 13  
12-27 13:50:55.540 5068-8652/lbx.myapplication I/System.out: 14  
12-27 13:50:55.540 5068-8652/lbx.myapplication I/System.out: 15  
12-27 13:50:55.540 5068-8651/lbx.myapplication I/System.out: 6  
12-27 13:50:55.540 5068-8651/lbx.myapplication I/System.out: 7  
12-27 13:50:55.540 5068-8651/lbx.myapplication I/System.out: 8  
12-27 13:50:55.540 5068-8651/lbx.myapplication I/System.out: 9  
12-27 13:50:55.540 5068-8651/lbx.myapplication I/System.out: 10  
12-27 13:50:55.540 5068-8652/lbx.myapplication I/System.out: 0  
12-27 13:50:55.540 5068-8652/lbx.myapplication I/System.out: 1  
12-27 13:50:55.540 5068-8652/lbx.myapplication I/System.out: 2  
12-27 13:50:55.540 5068-8652/lbx.myapplication I/System.out: 3  
12-27 13:50:55.540 5068-8652/lbx.myapplication I/System.out: 4  
12-27 13:50:55.540 5068-8652/lbx.myapplication I/System.out: 5  
1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
四、RecursiveTas的用法,用RecursiveTas实现查找数组最大数的功能  
RecursiveTas和RecursiveAction的区别就是， RecursiveTas需要传入一个泛型，重写compute()方法后，返回值是这个泛型。RecursiveAction的compute()方法返回值是void。  
看下栗子：

public class MaxTask extends RecursiveTask \{

private int[] ints;
    /**
     * 两个两个作比较
     */
    public static final int MAX = 2;
    
    public MaxTask(int[] ints) {
        this.ints = ints;
    }
    
    @Override
    protected Integer compute() {
        int length = ints.length;
        if (length > MAX) {
            int num = length / 2;
            int[] ints1 = new int[num];
            int[] ints2 = new int[length - num];
            //拷贝数组
            System.arraycopy(ints, 0, ints1, 0, ints1.length);
            System.arraycopy(ints, num, ints2, 0, ints2.length);
            MaxTask testTask1 = new MaxTask(ints1);
            MaxTask testTask2 = new MaxTask(ints2);
            ForkJoinTask<Integer> fork1 = testTask1.fork();
            ForkJoinTask<Integer> fork2 = testTask2.fork();
            try {
                return Math.max(fork1.get(), fork2.get());
            } catch (InterruptedException e) {
                e.printStackTrace();
            } catch (ExecutionException e) {
                e.printStackTrace();
            }
        } else {
            //有的时候传进来的数组是单数，所以从“两两比较”变成“只有一个数的数组”
            return ints.length == 1 ? ints[0] : Math.max(ints[0], ints[1]);
        }
        return -1;
    }

\}  
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  
这里有两行代码：System.arraycopy()，这个方法的作用是拷贝数组，不会用的童鞋去网上搜索下，篇幅有限就不在这讲解了。get()方法会在下一段代码后的文字中说明。  
调用代码：

public static void main(String[] args) {
        int[] ints = new int[]{0, -1, -2, 100, 98, 7, 0};
        MaxTask task = new MaxTask(ints);
        ForkJoinPool pool = new ForkJoinPool();
        ForkJoinTask<Integer> submit = pool.submit(task);
        try {
            Integer integer = submit.get();
            System.out.println("最大值:" + integer);
        } catch (InterruptedException e) {
            e.printStackTrace();
        } catch (ExecutionException e) {
            e.printStackTrace();
        }
    }

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
接下来看log：  
注意下这行代码：Integer integer = submit.get(); get方法具有阻塞效果，也就是说，如果任务没有发完成的时候，会在get()这里阻塞住，直到任务完成，才会释放阻塞并返回结果，若已经完成任务，那么get()方法直接回返回结果。

12-27 14:18:08.600 28736-28736/lbx.myapplication I/System.out: 最大值:100  
1  
五、实战！用RecursiveTas解决坑队友的注册问题！注意，这不是单线程！不是单线程！  
首先，我们只知道用户的昵称，但是没有账号密码，需要注册，新建一个用户实体类：

public class AccountBean \{  
public String account;  
public String password;  
public String nickName;

public AccountBean(String nickName) {
        this.nickName = nickName;
    }
    
    @Override
    public String toString() {
        return "AccountBean{" +
                "account='" + account + '\'' +
                ", password='" + password + '\'' +
                ", nickName='" + nickName + '\'' +
                '}';
    }

\}  
1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
然后创建一个Task：

public class SignUpTask extends RecursiveTask