jdk1.7 并行工具类库用法测试

以下是我用并行算法实现快速排序的类.

 

下面的是task

 

import java.util.Arrays;
import java.util.concurrent.RecursiveAction;

/**
 * 并行快速排序的task
 * 算法为如果排序长度小于10,则使用JDK自带的{@link java.util.Arrays#sort(int[] a, int fromIndex, int toIndex)}方法;如果长度大于10,则用第一个数字为中间数,做快速排序.
 * 分成前后两部分后使用并行框架并行运行.
 *
 * @author chouy
 */
public class QuickSortTask extends RecursiveAction
{
    static int THRESHOLD = 256;
    private int[] array;
    int start;
    int end;

    public QuickSortTask(int[] array, int start, int end)
    {
        this.array = array;
        this.start = start;
        this.end = end;
    }

    @Override
    protected void compute()
    {
        if (end - start < THRESHOLD)
        {
            if (end - start == 1)
                return;
            Arrays.sort(array, start, end + 1);
        }
        else
        {
            int v = array[start];
            boolean isAdd = true;
            int i, j;
            for (i = start, j = end; i < j;)
            {
                if (isAdd)
                {
                    if (v > array[j])
                    {
                        array[i] = array[j];
                        array[j] = v;
                        isAdd = false;
                        i++;
                    }
                    else
                    {
                        j--;
                    }
                }
                else
                {
                    if (v < array[i])
                    {
                        array[j] = array[i];
                        array[i] = v;
                        isAdd = true;
                        j--;
                    }
                    else
                    {
                        i++;
                    }
                }
            }
            // 并行执行分成的两部分

            invokeAll(new QuickSortTask(array, start, i - 1), new QuickSortTask(array, i + 1, end));
        }
    }
}

这是快速排序的工具类,里面有main方法用来测试.

package chouy.jdk7;

import java.util.Arrays;
import java.util.Random;
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.ForkJoinTask;
import java.lang.Runtime;

/**
 * quick sort used jdk7's join
 *
 * @author chouy
 */
public class QuickSort
{
    ForkJoinPool pool;

    public static void main(String[] args)
    {
        QuickSort quickSort = new QuickSort();
        int arraySize = 40;
        int[] array = new int[arraySize];
        Random r = new Random();
        for (int i = 0; i < array.length; i++)
        {
            array[i] = r.nextInt(arraySize);
        }
        System.out.println(Arrays.toString(array));
        // Arrays.sort(array, 0, array.length);

        // System.out.println(Arrays.toString(array));

        quickSort.sort(array);
        System.out.println(Arrays.toString(array));
    }

    public QuickSort()
    {
        pool = new ForkJoinPool(Runtime.getRuntime().availableProcessors());
    }

    public synchronized void sort(int array[])
    {
        ForkJoinTask<Void> job = pool.submit(new QuickSortTask(array, 0, array.length - 1));
        job.join();
    }
}

最后再提供一个junit测试类,用于测试正确性,性能等.

package chouy.jdk7;

import java.util.Arrays;
import java.util.Random;

import org.junit.Assert;
import org.junit.Before;
import org.junit.Test;

public class QuickSortTest
{
    QuickSort quickSort;

    @Before
    public void setUp() throws Exception
    {
        quickSort = new QuickSort();
    }

    /**
     * 测试结果是否正确
     */
    @Test
    public void testSort()
    {
        int arraySize = 40;
        int[] arrayQuickSort = new int[arraySize];
        int[] arrayArraysSort = new int[arraySize];
        Random r = new Random();
        for (int i = 0; i < arrayQuickSort.length; i++)
        {
            arrayQuickSort[i] = r.nextInt(arraySize);
        }
        System.arraycopy(arrayQuickSort, 0, arrayArraysSort, 0, arraySize);

        System.out.println(Arrays.toString(arrayQuickSort));
        quickSort.sort(arrayQuickSort);

        Arrays.sort(arrayArraysSort);
        for (int i = 0; i < arrayQuickSort.length; i++)
        {
            Assert.assertEquals(arrayQuickSort[i], arrayArraysSort[i]);
        }
    }

    /**
     * 测试快速排序的性能与Arrays.sort()方法的比较
     */
    @Test
    public void testPerformance()
    {
        int arraySize = 50000000;
        int[] arrayQuickSort = new int[arraySize];
        int[] arrayArraysSort = new int[arraySize];
        Random r = new Random();
        for (int i = 0; i < arrayQuickSort.length; i++)
        {
            arrayQuickSort[i] = r.nextInt(arraySize);
        }
        System.arraycopy(arrayQuickSort, 0, arrayArraysSort, 0, arraySize);

        // System.out.println(Arrays.toString(arrayQuickSort));

        System.out.println("start concurrent");
        long start = System.currentTimeMillis();
        quickSort.sort(arrayQuickSort);
        long end = System.currentTimeMillis();
        long spend1 = end - start;

        System.out.println("start system quick sort");
        start = System.currentTimeMillis();
        Arrays.sort(arrayArraysSort);
        end = System.currentTimeMillis();
        long spend2 = end - start;
        System.out.println("concurrent: " + spend1 + ", quickSort: " + spend2);
    }

    /**
     * 用来测试快排方法中,被排序数组长度为5000万时,threshold值不同时运行的时间.
     */
    @Test
    public void testBestThreshold()
    {
        int arraySize = 50000000;
        int[] arrayQuickSort = new int[arraySize];
        int[] arrayArraysSort = new int[arraySize];
        Random r = new Random();
        for (int i = 0; i < arrayQuickSort.length; i++)
        {
            arrayQuickSort[i] = r.nextInt(arraySize);
        }
        for (int i = 128; i <= arraySize; i = i * 2)
        {
            System.arraycopy(arrayQuickSort, 0, arrayArraysSort, 0, arraySize);
            QuickSortTask.THRESHOLD = i;
            System.out.print("threshold = " + i);
            long start = System.currentTimeMillis();
            quickSort.sort(arrayArraysSort);
            long end = System.currentTimeMillis();
            System.out.println(" spends " + (end - start) + " ms");
        }
    }
}

总结: threshold的值对程序性能影响还是比较大的,核心数量也是一个关键参数.不同的排序大小,threshold的最优值不同.这个需要多测试才能知道.我觉得最好是arraySize / coreNumber.

我大概测了一下运行效率,我两核的机器运行时间是使用Arrays.sort()的一半多一点,这也在预料之中.