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

引用：http://blog.chinaunix.net/uid-540802-id-2881055.html
以下是我用并行算法实现快速排序的类.



下面的是task




package chouy.jdk7;
1.

2.import java.util.Arrays;

3.import java.util.concurrent.RecursiveAction;

4.

5./**

6. * 并行快速排序的task<br>

7. * 算法为如果排序长度小于10,则使用JDK自带的{@link java.util.Arrays#sort(int[] a, int fromIndex, int toIndex)}方法;如果长度大于10,则用第一个数字为中间数,做快速排序.

8. * 分成前后两部分后使用并行框架并行运行.

9. *

10. * @author chouy

11. */

12.public class QuickSortTask extends RecursiveAction

13.{

14.    static int THRESHOLD = 256;

15.    private int[] array;

16.    int start;

17.    int end;

18.

19.    public QuickSortTask(int[] array, int start, int end)

20.    {

21.        this.array = array;

22.        this.start = start;

23.        this.end = end;

24.    }

25.

26.    @Override

27.    protected void compute()

28.    {

29.        if (end - start < THRESHOLD)

30.        {

31.            if (end - start == 1)

32.                return;

33.            Arrays.sort(array, start, end + 1);

34.        }

35.        else

36.        {

37.            int v = array[start];

38.            boolean isAdd = true;

39.            int i, j;

40.            for (i = start, j = end; i < j;)

41.            {

42.                if (isAdd)

43.                {

44.                    if (v > array[j])

45.                    {

46.                        array[i] = array[j];

47.                        array[j] = v;

48.                        isAdd = false;

49.                        i++;

50.                    }

51.                    else

52.                    {

53.                        j--;

54.                    }

55.                }

56.                else

57.                {

58.                    if (v < array[i])

59.                    {

60.                        array[j] = array[i];

61.                        array[i] = v;

62.                        isAdd = true;

63.                        j--;

64.                    }

65.                    else

66.                    {

67.                        i++;

68.                    }

69.                }

70.            }

71.            // 并行执行分成的两部分

72.

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

74.        }

75.    }

76.}

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

1.package chouy.jdk7;

2.

3.import java.util.Arrays;

4.import java.util.Random;

5.import java.util.concurrent.ForkJoinPool;

6.import java.util.concurrent.ForkJoinTask;

7.import java.lang.Runtime;

8.

9./**

10. * quick sort used jdk7's join

11. *

12. * @author chouy

13. */

14.public class QuickSort

15.{

16.    ForkJoinPool pool;

17.

18.    public static void main(String[] args)

19.    {

20.        QuickSort quickSort = new QuickSort();

21.        int arraySize = 40;

22.        int[] array = new int[arraySize];

23.        Random r = new Random();

24.        for (int i = 0; i < array.length; i++)

25.        {

26.            array[i] = r.nextInt(arraySize);

27.        }

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

29.        // Arrays.sort(array, 0, array.length);

30.

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

32.

33.        quickSort.sort(array);

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

35.    }

36.

37.    public QuickSort()

38.    {

39.        pool = new ForkJoinPool(Runtime.getRuntime().availableProcessors());

40.    }

41.

42.    public synchronized void sort(int array[])

43.    {

44.        ForkJoinTask<Void> job = pool.submit(new QuickSortTask(array, 0, array.length - 1));

45.        job.join();

46.    }

47.}

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

1.package chouy.jdk7;

2.

3.import java.util.Arrays;

4.import java.util.Random;

5.

6.import org.junit.Assert;

7.import org.junit.Before;

8.import org.junit.Test;

9.

10.public class QuickSortTest

11.{

12.    QuickSort quickSort;

13.

14.    @Before

15.    public void setUp() throws Exception

16.    {

17.        quickSort = new QuickSort();

18.    }

19.

20.    /**

21.     * 测试结果是否正确

22.     */

23.    @Test

24.    public void testSort()

25.    {

26.        int arraySize = 40;

27.        int[] arrayQuickSort = new int[arraySize];

28.        int[] arrayArraysSort = new int[arraySize];

29.        Random r = new Random();

30.        for (int i = 0; i < arrayQuickSort.length; i++)

31.        {

32.            arrayQuickSort[i] = r.nextInt(arraySize);

33.        }

34.        System.arraycopy(arrayQuickSort, 0, arrayArraysSort, 0, arraySize);

35.

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

37.        quickSort.sort(arrayQuickSort);

38.

39.        Arrays.sort(arrayArraysSort);

40.        for (int i = 0; i < arrayQuickSort.length; i++)

41.        {

42.            Assert.assertEquals(arrayQuickSort[i], arrayArraysSort[i]);

43.        }

44.    }

45.

46.    /**

47.     * 测试快速排序的性能与Arrays.sort()方法的比较

48.     */

49.    @Test

50.    public void testPerformance()

51.    {

52.        int arraySize = 50000000;

53.        int[] arrayQuickSort = new int[arraySize];

54.        int[] arrayArraysSort = new int[arraySize];

55.        Random r = new Random();

56.        for (int i = 0; i < arrayQuickSort.length; i++)

57.        {

58.            arrayQuickSort[i] = r.nextInt(arraySize);

59.        }

60.        System.arraycopy(arrayQuickSort, 0, arrayArraysSort, 0, arraySize);

61.

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

63.

64.        System.out.println("start concurrent");

65.        long start = System.currentTimeMillis();

66.        quickSort.sort(arrayQuickSort);

67.        long end = System.currentTimeMillis();

68.        long spend1 = end - start;

69.

70.        System.out.println("start system quick sort");

71.        start = System.currentTimeMillis();

72.        Arrays.sort(arrayArraysSort);

73.        end = System.currentTimeMillis();

74.        long spend2 = end - start;

75.        System.out.println("concurrent: " + spend1 + ", quickSort: " + spend2);

76.    }

77.

78.    /**

79.     * 用来测试快排方法中,被排序数组长度为5000万时,threshold值不同时运行的时间.

80.     */

81.    @Test

82.    public void testBestThreshold()

83.    {

84.        int arraySize = 50000000;

85.        int[] arrayQuickSort = new int[arraySize];

86.        int[] arrayArraysSort = new int[arraySize];

87.        Random r = new Random();

88.        for (int i = 0; i < arrayQuickSort.length; i++)

89.        {

90.            arrayQuickSort[i] = r.nextInt(arraySize);

91.        }

92.        for (int i = 128; i <= arraySize; i = i * 2)

93.        {

94.            System.arraycopy(arrayQuickSort, 0, arrayArraysSort, 0, arraySize);

95.            QuickSortTask.THRESHOLD = i;

96.            System.out.print("threshold = " + i);

97.            long start = System.currentTimeMillis();

98.            quickSort.sort(arrayArraysSort);

99.            long end = System.currentTimeMillis();

100.            System.out.println(" spends " + (end - start) + " ms");

101.        }

102.    }

103.}