Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1898401
  • 博文数量: 219
  • 博客积分: 8963
  • 博客等级: 中将
  • 技术积分: 2125
  • 用 户 组: 普通用户
  • 注册时间: 2005-10-19 12:48
个人简介

文章分类

全部博文(219)

文章存档

2021年(1)

2020年(3)

2015年(4)

2014年(5)

2012年(7)

2011年(37)

2010年(40)

2009年(22)

2008年(17)

2007年(48)

2006年(31)

2005年(4)

分类: Java

2011-09-20 16:51:16

以下是我用并行算法实现快速排序的类.
 
下面的是task
 
    package chouy.jdk7;

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

  3. /**
  4.  * 并行快速排序的task

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

  16.     public QuickSortTask(int[] array, int start, int end)
  17.     {
  18.         this.array = array;
  19.         this.start = start;
  20.         this.end = end;
  21.     }

  22.     @Override
  23.     protected void compute()
  24.     {
  25.         if (end - start < THRESHOLD)
  26.         {
  27.             if (end - start == 1)
  28.                 return;
  29.             Arrays.sort(array, start, end + 1);
  30.         }
  31.         else
  32.         {
  33.             int v = array[start];
  34.             boolean isAdd = true;
  35.             int i, j;
  36.             for (i = start, j = end; i < j;)
  37.             {
  38.                 if (isAdd)
  39.                 {
  40.                     if (v > array[j])
  41.                     {
  42.                         array[i] = array[j];
  43.                         array[j] = v;
  44.                         isAdd = false;
  45.                         i++;
  46.                     }
  47.                     else
  48.                     {
  49.                         j--;
  50.                     }
  51.                 }
  52.                 else
  53.                 {
  54.                     if (v < array[i])
  55.                     {
  56.                         array[j] = array[i];
  57.                         array[i] = v;
  58.                         isAdd = true;
  59.                         j--;
  60.                     }
  61.                     else
  62.                     {
  63.                         i++;
  64.                     }
  65.                 }
  66.             }
  67.             // 并行执行分成的两部分

  68.             invokeAll(new QuickSortTask(array, start, i - 1), new QuickSortTask(array, i + 1, end));
  69.         }
  70.     }
  71. }

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

  1. package chouy.jdk7;

  2. import java.util.Arrays;
  3. import java.util.Random;
  4. import java.util.concurrent.ForkJoinPool;
  5. import java.util.concurrent.ForkJoinTask;
  6. import java.lang.Runtime;

  7. /**
  8.  * quick sort used jdk7's join
  9.  *
  10.  * @author chouy
  11.  */
  12. public class QuickSort
  13. {
  14.     ForkJoinPool pool;

  15.     public static void main(String[] args)
  16.     {
  17.         QuickSort quickSort = new QuickSort();
  18.         int arraySize = 40;
  19.         int[] array = new int[arraySize];
  20.         Random r = new Random();
  21.         for (int i = 0; i < array.length; i++)
  22.         {
  23.             array[i] = r.nextInt(arraySize);
  24.         }
  25.         System.out.println(Arrays.toString(array));
  26.         // Arrays.sort(array, 0, array.length);

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

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

  31.     public QuickSort()
  32.     {
  33.         pool = new ForkJoinPool(Runtime.getRuntime().availableProcessors());
  34.     }

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

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

  1. package chouy.jdk7;

  2. import java.util.Arrays;
  3. import java.util.Random;

  4. import org.junit.Assert;
  5. import org.junit.Before;
  6. import org.junit.Test;

  7. public class QuickSortTest
  8. {
  9.     QuickSort quickSort;

  10.     @Before
  11.     public void setUp() throws Exception
  12.     {
  13.         quickSort = new QuickSort();
  14.     }

  15.     /**
  16.      * 测试结果是否正确
  17.      */
  18.     @Test
  19.     public void testSort()
  20.     {
  21.         int arraySize = 40;
  22.         int[] arrayQuickSort = new int[arraySize];
  23.         int[] arrayArraysSort = new int[arraySize];
  24.         Random r = new Random();
  25.         for (int i = 0; i < arrayQuickSort.length; i++)
  26.         {
  27.             arrayQuickSort[i] = r.nextInt(arraySize);
  28.         }
  29.         System.arraycopy(arrayQuickSort, 0, arrayArraysSort, 0, arraySize);

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

  32.         Arrays.sort(arrayArraysSort);
  33.         for (int i = 0; i < arrayQuickSort.length; i++)
  34.         {
  35.             Assert.assertEquals(arrayQuickSort[i], arrayArraysSort[i]);
  36.         }
  37.     }

  38.     /**
  39.      * 测试快速排序的性能与Arrays.sort()方法的比较
  40.      */
  41.     @Test
  42.     public void testPerformance()
  43.     {
  44.         int arraySize = 50000000;
  45.         int[] arrayQuickSort = new int[arraySize];
  46.         int[] arrayArraysSort = new int[arraySize];
  47.         Random r = new Random();
  48.         for (int i = 0; i < arrayQuickSort.length; i++)
  49.         {
  50.             arrayQuickSort[i] = r.nextInt(arraySize);
  51.         }
  52.         System.arraycopy(arrayQuickSort, 0, arrayArraysSort, 0, arraySize);

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

  54.         System.out.println("start concurrent");
  55.         long start = System.currentTimeMillis();
  56.         quickSort.sort(arrayQuickSort);
  57.         long end = System.currentTimeMillis();
  58.         long spend1 = end - start;

  59.         System.out.println("start system quick sort");
  60.         start = System.currentTimeMillis();
  61.         Arrays.sort(arrayArraysSort);
  62.         end = System.currentTimeMillis();
  63.         long spend2 = end - start;
  64.         System.out.println("concurrent: " + spend1 + ", quickSort: " + spend2);
  65.     }

  66.     /**
  67.      * 用来测试快排方法中,被排序数组长度为5000万时,threshold值不同时运行的时间.
  68.      */
  69.     @Test
  70.     public void testBestThreshold()
  71.     {
  72.         int arraySize = 50000000;
  73.         int[] arrayQuickSort = new int[arraySize];
  74.         int[] arrayArraysSort = new int[arraySize];
  75.         Random r = new Random();
  76.         for (int i = 0; i < arrayQuickSort.length; i++)
  77.         {
  78.             arrayQuickSort[i] = r.nextInt(arraySize);
  79.         }
  80.         for (int i = 128; i <= arraySize; i = i * 2)
  81.         {
  82.             System.arraycopy(arrayQuickSort, 0, arrayArraysSort, 0, arraySize);
  83.             QuickSortTask.THRESHOLD = i;
  84.             System.out.print("threshold = " + i);
  85.             long start = System.currentTimeMillis();
  86.             quickSort.sort(arrayArraysSort);
  87.             long end = System.currentTimeMillis();
  88.             System.out.println(" spends " + (end - start) + " ms");
  89.         }
  90.     }
  91. }

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

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

阅读(1979) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~