基本上，我已经花了几个小时研究实现递归和多线程快速排序和合并排序的最佳方法（本文仅涉及快速排序）。我的目标是采用给定计算机中的每个逻辑处理器并将其全部固定，以实现最大的快速排序速度。
我采用了在创建线程时递归分解问题的方法，直到对数组进行排序或达到CPU上的处理器数量为止，在这种情况下，其余问题将不会划分到新线程上，而其余问题将在自己的核心。
创建了只能在我的计算机上运行的非常基本的解决方案后，我遇到了下面尝试使用的Fork / Join框架，但实际上我不知道该怎么做。我想到的是，对10000000个从0到1000的随机数进行排序的速度要比其单线程对应数慢，但是我仍然认为它很有趣，因为在其文档中说，它能够从较慢的线程中窃取工作，这意味着什么。
然后，我最近才听说线程池，并最初创建了我的所有线程并将其分发出去，因为创建新线程会增加系统负担。但是我从来没有尝试实现这个目标。也许我对Fork / Join的理解是歪曲的，我想知道是否有人可以指出我正确的方向或告诉我在当前程序中我做错了什么。
在下面，您会发现我尝试进行多线程快速排序和单线程快速排序，这就是我要转换为多线程快速排序的内容。任何帮助表示赞赏。干杯！。
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, 0, 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);
}
}
单螺纹
public static void quickSort(List<Comparable> nums, int first, int last) {
int low = first;
int high = last;
int midIndex = (first + last) / 2;
Comparable midValue = nums.get(midIndex);
while(low < high) {
while (nums.get(low).compareTo(midValue) < 0) {
low++;
}
while (nums.get(high).compareTo(midValue) > 0) {
high--;
}
if (low <= high) {
swap(nums, low, high);
low++;
high--;
}
}
if (high > first)
quickSort(nums, first, high);
if (low < last)
quickSort(nums, low, last);
}
我不太了解Java，因此下面的示例代码可能对多个线程的runnable用法很笨拙。此示例代码使用8个线程，qsortmt（）进行分区，并启动qsort0（）的两个实例。qsort0（）的每个实例都进行分区，并调用qsort1（）的两个实例。qsort1（）的每个实例都进行分区，并调用qsort2（）的两个实例。qsort2（）的每个实例都调用qsort（）。对于本示例中使用的1600万个整数，使用8线程排序大约需要1秒，而使用非线程排序大约需要1.6秒，因此节省不了多少。问题的一部分是分区步骤是在调用线程以对子分区进行操作之前完成的。
切换到C ++和Windows本机线程后，8个线程花费了大约0.632秒，非线程花费了1.352秒。切换到合并排序，将数组分为8个部分，对每个部分进行排序，然后合并这8个部分大约需要0.40秒，而单线程大约需要1.45秒。
package x;
import java.util.Random;
public class x {
class qsort0 implements Runnable
{
int[] a;
int lo;
int hi;
private qsort0(int[] a, int lo, int hi)
{
this.a = a;
this.lo = lo;
this.hi = hi;
}
@Override
public void run()
{
if(this.lo >= this.hi)
return;
int pi = partition(this.a, this.lo, this.hi);
Thread lt = new Thread(new qsort1(a, this.lo, pi));
Thread rt = new Thread(new qsort1(a, pi+1, this.hi));
lt.start();
rt.start();
try {lt.join();} catch (InterruptedException ex){}
try {rt.join();} catch (InterruptedException ex){}
}
}
class qsort1 implements Runnable
{
int[] a;
int lo;
int hi;
private qsort1(int[] a, int lo, int hi)
{
this.a = a;
this.lo = lo;
this.hi = hi;
}
@Override
public void run()
{
if(this.lo >= this.hi)
return;
int pi = partition(this.a, this.lo, this.hi);
Thread lt = new Thread(new qsort2(a, this.lo, pi));
Thread rt = new Thread(new qsort2(a, pi+1, this.hi));
lt.start();
rt.start();
try {lt.join();} catch (InterruptedException ex){}
try {rt.join();} catch (InterruptedException ex){}
}
}
class qsort2 implements Runnable
{
int[] a;
int lo;
int hi;
private qsort2(int[] a, int lo, int hi)
{
this.a = a;
this.lo = lo;
this.hi = hi;
}
@Override
public void run() {
if(this.lo >= this.hi)
return;
qsort(this.a, this.lo, this.hi);
}
}
// quicksort multi-threaded
@SuppressWarnings("empty-statement")
public static void qsortmt(int[] a, int lo, int hi)
{
if(lo >= hi)
return;
int pi = partition(a, lo, hi);
Thread lt = new Thread(new x().new qsort0(a, lo, pi));
Thread rt = new Thread(new x().new qsort0(a, pi+1, hi));
lt.start();
rt.start();
try {lt.join();} catch (InterruptedException ex){}
try {rt.join();} catch (InterruptedException ex){}
}
@SuppressWarnings("empty-statement")
public static int partition(int []a, int lo, int hi)
{
int md = lo+(hi-lo)/2;
int ll = lo-1;
int hh = hi+1;
int t;
int p = a[md];
while(true){
while(a[++ll] < p);
while(a[--hh] > p);
if(ll >= hh)
break;
t = a[ll];
a[ll] = a[hh];
a[hh] = t;
}
return hh;
}
@SuppressWarnings("empty-statement")
public static void qsort(int[] a, int lo, int hi)
{
while(lo < hi){
int ll = partition(a, lo, hi);
int hh = ll+1;
// recurse on smaller part, loop on larger part
if((ll - lo) <= (hi - hh)){
qsort(a, lo, ll);
lo = hh;
} else {
qsort(a, hh, hi);
hi = ll;
}
}
}
public static void main(String[] args)
{
int[] a = new int[16*1024*1024];
Random r = new Random(0);
for(int i = 0; i < a.length; i++)
a[i] = r.nextInt();
long bgn, end;
bgn = System.currentTimeMillis();
qsortmt(a, 0, a.length-1);
end = System.currentTimeMillis();
for(int i = 1; i < a.length; i++){
if(a[i-1] > a[i]){
System.out.println("failed");
break;
}
}
System.out.println("milliseconds " + (end-bgn));
}
}
本文收集自互联网，转载请注明来源。
如有侵权，请联系 [email protected] 删除。
我来说两句