基本上,我已经花了几个小时研究实现递归和多线程快速排序和合并排序的最佳方法(本文仅涉及快速排序)。我的目标是采用给定计算机中的每个逻辑处理器并将其全部固定,以实现最大的快速排序速度。
我在创建线程时采用递归方式分解问题,直到对数组进行排序或达到CPU上的处理器数量为止,在这种情况下,问题的其余部分不会被划分到新线程上,而是其余部分在自己的核心上执行。
在创建了一个仅能在我的计算机上运行的非常基本的解决方案之后,我遇到了下面尝试使用的Fork / Join框架,但实际上我不知道该怎么做。我想到的是,对10000000个随机数(从0到1000)的排序比单线程对应的慢,但我仍然认为它很有趣,因为在其docs中说,它能够从较慢的线程中窃取工作手段。
然后我最近才听说线程池,并最初创建我的所有线程并将其分发出去,因为创建新线程会增加系统负担。但是我从来没有尝试实现这个目标。也许我对Fork / Join的理解是歪曲的,我想知道是否有人可以指出我正确的方向或告诉我在当前程序中我做错了什么。
在下面,您会发现我尝试了多线程快速排序和单线程快速排序,这就是我要转换为多线程快速排序的内容。任何帮助表示赞赏。干杯!!
2812068811464
2812100759880
2812100759880
2812100759880
单线程
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.Recursiveaction;
public class MultithreadedQuicksort {
public static void main(String[] args) {
List<Comparable> nums = new ArrayList<Comparable>();
Random rand = new Random();
for (int i=0; i<10000000; i++) {
nums.add(rand.nextInt(1000));
}
long start = System.currentTimeMillis();
Quicksort quickSort = new Quicksort(nums,nums.size() -1);
ForkJoinPool pool = new ForkJoinPool();
pool.invoke(quickSort);
long end = System.currentTimeMillis();
System.out.println(end - start);
System.out.println(nums.size());
}
}
class Quicksort extends Recursiveaction {
int first;
int last;
private List<Comparable> nums;
Comparable midValue;
int midIndex;
int low;
int high;
public Quicksort(List<Comparable> nums){
this.nums=nums;
this.low = 0;
this.high = nums.size() - 1;
}
public Quicksort(List<Comparable> nums,int first,int last) {
this.first = first;
this.last = last;
this.nums = nums;
this.low = first;
this.high = last;
this.midIndex = (first + last) / 2;
this.midValue = nums.get(midIndex);
}
@Override
protected void compute() {
split();
if (high > first)
invokeAll(new Quicksort(nums,first,high));
if (low < last)
invokeAll(new Quicksort(nums,low,last));
}
public void split() {
while(low < high) {
while (nums.get(low).compareTo(midValue) < 0) {
low++;
}
while (nums.get(high).compareTo(midValue) > 0) {
high--;
}
if (low <= high) {
swap(low,high);
low++;
high--;
}
}
}
public void swap(int index1,int index2)
{
Comparable temp;
temp = nums.get(index1);
nums.set(index1,nums.get(index2));
nums.set(index2,temp);
}
}