2
回答
快速排序采用多线程后更耗时,问题出在哪里?
利用AWS快速构建适用于生产的无服务器应用程序,免费试用12个月>>>   

今天写了下快速排序,在写的过程中发现,既然每次都会把数组拆分成两个子数组进行处理,那么对每个子数组的处理是不是可以由一个线程来单独处理呢? 这样是不是会更快呢?  抱着这个方法测试了一下,结果雷到我了,或者是我多线程的处理行有问题,大家看看,帮我找下问题。

//这个是没有采用多线程的快排

public class QuickSort2{

 public void quickSort(double[] arr, Integer low, Integer hight) {
  double temp;
  if(null == low || hight == null) {
   //初始化情况
   low = 0;
   hight = arr.length - 1;
  }
  int i = low, j = hight;//i是低端,j是高端
  if(i >= j) {
   return;
  }
  //一趟排序
  temp = arr[i];//区基数
  while(i < j) {
   //在高区找到比基数小的
   while(i < j) {
    if(arr[j] >= temp) {
     j-- ;
    }else {
     //找到比基数小的,那就放到基数的位置去
     arr[i] = arr[j]; //此时大端位子空了出来
     //i++;   //此时的arr[i] 已经比temp小了,所以i++
     break;
    }
   }
   
   //去低端找比基数大的,然后放到大段去
   while(i < j) {
    if(arr[i] <= temp) {
     i ++;
    }else {
     arr[j] = arr[i];
     //j -- ;
     break;
    }
   }
  }
  arr[i] = temp;  //此时i应该=j ,因为跳出循环的情况就是i>=j

  quickSort(arr, low, i-1);
  quickSort(arr, j+1, hight);
 }
}

//采用多线程的快排

public class QuickSort implements Callable<double[]>{
 private double[] arr;
 private Integer low;
 private Integer hight;
 public QuickSort(double[] arr, Integer low, Integer hight) {
  this.arr = arr;
  this.low = low;
  this.hight = hight;
 }
 
 
 public void quickSort() {
  double temp;
  if(null == low || hight == null) {
   //初始化情况
   low = 0;
   hight = arr.length - 1;
  }
  int i = low, j = hight;//i是低端,j是高端
  if(i >= j) {
   return;
  }
  //一趟排序
  temp = arr[i];//区基数
  while(i < j) {
   //在高区找到比基数小的
   while(i < j) {
    if(arr[j] >= temp) {
     j-- ;
    }else {
     //找到比基数小的,那就放到基数的位置去
     arr[i] = arr[j]; //此时大端位子空了出来
     //i++;   //此时的arr[i] 已经比temp小了,所以i++
     break;
    }
   }
   
   //去低端找比基数大的,然后放到大段去
   while(i < j) {
    if(arr[i] <= temp) {
     i ++;
    }else {
     arr[j] = arr[i];
     //j -- ;
     break;
    }
   }
  }
  arr[i] = temp;  //此时i应该=j ,因为跳出循环的情况就是i>=j
  
  QuickSort q1 = new QuickSort(arr, low, i-1);
  QuickSort q2 = new QuickSort(arr, j+1, hight);
  
  try {
   FutureTask<double[]> f1 = new FutureTask<double[]>(q1);
   FutureTask<double[]> f2 = new FutureTask<double[]>(q2);
   Thread t1 = new Thread(f1);
   Thread t2 = new Thread(f2);
   t1.start();
   t2.start();
   f1.get();
   f2.get();
  } catch (Exception e) {
   e.printStackTrace();
  }
 }

 public double[] call() throws Exception {
  quickSort();
  return arr;
 }
}

我用一个10000长度的数组来测试了一下,结果吓死人,那差距之大。不要多线程那个只需要28毫秒,用了多线程那个竟然花了5000毫秒左右,相差基本上20倍了,大家看下那个多线程那里处理是不是有问题啊? 咋会出现这样的情况呢。  或者说如果没有问题的话,那就是提交一个线程到该线程启动,这段时间花得太多了 ?

 

举报
共有2个答案 最后回答: 3年前

对于cpu密集型的程序,多线程反而更慢,因为线程上下文切换是要耗系统性能的

理论上对于cpu密集型程序,线程数=核数才是最快的

快排是一个递归的过程, 在每一次都启动两个线程的方法来实现完全不可取, 会随着递归的层级产生2的n次方个线程,多次的创建,启动线程,明显会耗费太多的性能,线程太多之后,线程间上下文切换也是一个性能杀手。
--- 共有 1 条评论 ---
可不可以不要昵称不知道你有没有看我写的那段程序哈。 其实我想问的是那段程序有没有问题。 你的意思其实就是说是线程切换耗费了太多时间嘛? 3年前 回复
顶部