RecursiveTask可递归的多线程(多线程快速排序)

发布于 2022年 05月 04日 05:25

「这是我参与2022首次更文挑战的第26天,活动详情查看:2022首次更文挑战

前言

首先这个灵感来源于查找API文档的时候,我找到了这个东西

然后我想起来先前经典小算法之快排的时候我说过,你就是左右两边开线程也是可以没有影响滴,所以现在我们就是用这个来实现一个多线程的快速排序。

那么在这里我们先简单说一下这个RecursiveTask 有哪些注意点。

RecursiveTask使用

这个其实没啥就两个,Fork与Join,当然还有Compute。

使用结构

我们先来看看这个玩意使用的结构,官方给的是一个斐波那契的例子。

调用

现在我们可以尝试调用了,这个调用稍微复杂一点。 我们需要使用这个玩意

ForkJoinPool();
ForkJoinPool forkJoinPool = new ForkJoinPool(); 创建池

ForkJoinTask<Void> submit = forkJoinPool.submit(manyFastSort); 提交
submit.get()获取你的结果
forkJoinPool.shutdown(); 关闭

这里有个细节 get是个堵塞的方法

他会等待你的结果 如果你没有返回值,你可以使用

submit.join()

代替。

那么到这里我们就可以动手了。

单线程写法

我们还是来看看原来的单线程写法,然后对比这个多线程写法



public class FastSortOneThread {
    public static void main(String[] args) {

        int[] a = {12,20,5,16,15,1,30,45,23,9};
        long starttime = System.currentTimeMillis();
        sort(a);
        long endtime = System.currentTimeMillis();
        for (int j : a) {
            System.out.println(j);
        }

        System.out.println("用时:"+(endtime-starttime));
    }



    public static void sort(int[] a) {
        int low = 0;
        int height = a.length - 1;
        sort(a, low, height);
    }

    public static void sort(int[] a, int low, int high) {
        int start = low;
        int end = high;
        int key = a[low];


        while (end > start) {
            //从后往前比较
            while (end > start && a[end] >= key)
                end--;
            if (a[end] <= key) {
                swap(a, start, end);
            }
            //从前往后比较
            while (end > start && a[start] <= key)
                start++;
            if (a[start] >= key) {
                swap(a, start, end);
            }
            //此时第一次循环比较结束,关键值的位置已经确定了。左边的值都比关键值小,右边的值都比关键值大,但是两边的顺序还有可能是不一样的,进行下面的递归调用
        }
        //递归
        if (start > low)
            sort(a, low, start - 1);//左边序列。第一个索引位置到关键值索引-1
        if (end < high)
            sort(a, end + 1, high);//右边序列。从关键值索引+1到最后一个
    }

    public static void swap(int[] a, int start, int end) {
        int temp = a[start];
        a[start] = a[end];
        a[end] = temp;
    }

}

多线程写法


public class ManyFastSort extends RecursiveTask<Void> {
    private CopyOnWriteArrayList<Integer> a;
    private int low;
    private int height;
    private int start;
    private int end;

    public ManyFastSort(CopyOnWriteArrayList<Integer> a, int low, int height) {
        this.a = a;
        this.low = low;
        this.height = height;
    }

    public void swap(CopyOnWriteArrayList<Integer> a, int start, int end) {
        int temp = a.get(start);
        a.set(start,a.get(end));
        a.set(end,temp);
    }

    public void sortonece(CopyOnWriteArrayList<Integer>a,int start,int end){
        int key = a.get(start);
        while (end > start) {
            //从后往前比较
            while (end > start && a.get(end) >= key)
                end--;
            if (a.get(end) <= key) {
                swap(a, start, end);
            }
            //从前往后比较
            while (end > start && a.get(start) <= key)
                start++;
            if (a.get(start) >= key) {
                swap(a, start, end);
            }

        }
        this.start = start;
        this.end = end;

    }

    @Override
    protected Void compute() {
        start = low;
        end = height;
        ManyFastSort rightsort=null;
        ManyFastSort leftsort = null;

        sortonece(a,start,end);

        if(start>low){

            leftsort = new ManyFastSort(a, low, start - 1);
        }
        if(end<height){

            rightsort = new ManyFastSort(a, end + 1, height);
         }


        if(rightsort!=null){
            rightsort.fork();
            rightsort.join();
        }
        if(leftsort!=null){
            leftsort.fork();
            leftsort.join();
        }

        return null;
    }

}

class TestManyFastSort{
    public static void main(String[] args) {
        int[] a = {12,20,5,16,15,1,30,45,23,9};

        ArrayList<Integer> integerArray = (ArrayList<Integer>) Arrays.stream(a).boxed().collect(Collectors.toList());
        CopyOnWriteArrayList<Integer> integers = new CopyOnWriteArrayList<>(integerArray);
        ManyFastSort manyFastSort = new ManyFastSort(integers, 0, integers.size()- 1);
        ForkJoinPool forkJoinPool = new ForkJoinPool();

        long starttime = System.currentTimeMillis();

        ForkJoinTask<Void> submit = forkJoinPool.submit(manyFastSort);
        submit.join();

        long endtime = System.currentTimeMillis();
        for (int j : integers) {
            System.out.println(j);
        }
        System.out.println("用时:"+(endtime-starttime));
        forkJoinPool.shutdown();
    }
}

效率分析

现在分别运行,我们来查看效果

单线程

多线程

我们其实不难发现,这个多线程的明显更慢。其实这里我们可以简单分析一下。

首先我们正常情况了的时间复杂度为nlogn在执行多线程的时候,我们其实只是让左右同时比较,也就是假设,左边右边分别比较一次都只需要1秒,那么多线程递归是2秒结束,但是多线程是同时进行也就是1秒。但是这里有个问题,线程的创建是需要时间的,正常情况下的查找时间为nlogn,找到一个我就开两个线程,那么我一共会开出2nlogn次线程(同一时间只有两个子线程),所以我们可以发现只有一种情况下,数据量足够多,数据足够无序,这样单次的查找时间增加就可以最大化地抵消我们创建线程的消耗,此外我们还不考虑资源的消耗。所以你会发现为什么,在官方举例子(斐波那契数列)的时候,有这样一句话。

所以只要在前面说的那种情况下才有可能好起来,但是大多数情况下这个不是个好的解决方法,顶多和面试官聊聊。而且你也发现了,我这里为了保护数据安全,我还是使用了复制写入列表

CopyOnWriteArrayList

总结

这个其实主要还是看看这个RecusiveTask的用法,具体要不要用,看你的实际情况。多线程的开销不小,并且有时候并不会提高你想要的速度。

推荐文章