时间戳

首页 > 解决方案 > 尝试并行化快速排序以在 Java 中的多个线程上运行

java - 尝试并行化快速排序以在 Java 中的多个线程上运行

问题描述

我有一个运行良好的快速排序算法，但是当我尝试并行化它时，只有数组的后半部分正在排序，另一半几乎没有变化。而且由于我是并行编程的新手，我不知道为什么。我的解决方案是从网上找到的不同代码组合而成的。如何改进它以便对整个数组进行排序？

public class foo {

  private static final int N_THREADS = Runtime.getRuntime().availableProcessors();
  private static final int FALLBACK = 2;
  private static Executor pool = Executors.newFixedThreadPool(N_THREADS);

  public static <T extends Comparable<T>> void sort(int[] numberArray){
    if(numberArray == null && numberArray.length == 0){
      return;
    }

    final AtomicInteger count = new AtomicInteger(1);
    pool.execute(new QuicksortRunnable<T>(numberArray, 0, numberArray.length-1, count));
  }

private static class QuicksortRunnable<T extends Comparable<T>> implements Runnable {

    private final int[] values;
    private final int left;
    private final int right;
    private final AtomicInteger count;

public QuicksortRunnable(int[] values, int left, int right, AtomicInteger count) {

      this.values = values;
      this.left = left;
      this.right = right;
      this.count = count;
    }

    @Override
    public void run() {
      quicksort(left, right);
      synchronized (count) {
        if (count.getAndDecrement() == 1)
          count.notify();
      }
    }

    private void quicksort(int pLeft, int pRight) {
      int pivotIndex = (pRight - pLeft) / 2 + pLeft;
      int pivot = values[pivotIndex];
      int j = pRight;
      int i = pLeft;

      while (i < j) {
        while (values[i] > pivot) {
          i++;
        }
        while (values[j] < pivot) {
          j--;
        }
        if (i <= j) {
          int temp = values[i];
          values[i] = values[j];
          values[j] = temp;
          i++;
          j--;
        }
      }
      if (count.get() >= FALLBACK * N_THREADS) {
        if (pLeft < j)
          quicksort(pLeft, j);
        if (i < pRight)
          quicksort(i, pRight);
      } else {


        if (pLeft < j) {
          count.getAndAdd(1);
          pool.execute(new QuicksortRunnable<T>(values, pLeft, j, count));
        }
        if (i < pRight) {
          count.getAndAdd(1);
          pool.execute(new QuicksortRunnable<T>(values, i, pRight, count));
        }
      }
    }
  }
~~~
My main function:
public static void main(String[] arg) {
    Random rand = new Random();
    int length = 1000;
    int[] toSort = new int[length];
    for(int i = 0; i<length; i++){
      toSort[i] = rand.nextInt(length);
    }

    sort(toSort);

    boolean sortedFH = true;
    boolean sortedSH = true;

    for(int i = 0; i<length/2; i++) {      
      if (toSort[i] < toSort[i + 1]) {
        sortedFH = false;
      }
    }
    for(int i = length/2; i<length-1; i++) {
      if (toSort[i] < toSort[i + 1]) {
        sortedSH = false;
      }
    }

    System.out.println();
    System.out.println("First half :" + sortedFH);
    System.out.println("Second half :" + sortedSH);
  }
}

Returns:
First half :false
Second half :true

编辑：删除了程序的一部分。我尝试了一些东西，但没有用，发布问题时忘记将其删除。

标签： javaparallel-processingquicksort

解决方案

首先，我认为您看到的结果主要是因为您在排序线程完成之前打印出结果。在检查结果之前，您需要等待所有线程完成。

根据您的代码，您可以很容易地做到这一点，使用您的AtomicInteger计数来阻止sort()返回，直到所有线程都完成。

    public static <T extends Comparable<T>> void sort(int[] numberArray) {
        if (numberArray == null || numberArray.length == 0) {
            return;
        }

        final AtomicInteger count = new AtomicInteger(1);
        pool.execute(new QuicksortRunnable<T>(numberArray, 0, numberArray.length - 1, count));

        while (count.get() > 0) {
            synchronized (count) {
                count.wait();
            }
        }
    }

顺便说一句，除非是故意的，否则您的算法看起来像是要按降序对数组进行排序。我认为你需要翻转

        while (values[i] > pivot) {
          i++;
        }
        while (values[j] < pivot) {
          j--;
        }

至

        while (values[i] < pivot) {
          i++;
        }
        while (values[j] > pivot) {
          j--;
        }

这同样适用于您在 main 方法末尾的检查。

您对 null 或空数组的检查应由 OR 而非 AND 分隔

        if (numberArray == null || numberArray.length == 0) {
           return;
        }

推荐阅读