java - Java 中的多线程快速排序

Question

你能帮我用 Java 实现多线程 QuickSort 吗？

我有下一个问题: 1 个线程的快速排序的工作时间比 2 或 3 个线程的快速排序要少。我做错了什么？

我为 worker 编写了下一个代码:

public class QuickSortWorker extends Thread {

    private int workerId;
    private double[] array;
    private int low;
    private int high;

    public QuickSortWorker(double[] array, int low, int high) {
        this.array = array;
        this.low = low;
        this.high = high;
        this.workerId = WorkerManager.workersCount++;
    }

    public void run() {
        System.out.println("Run new worker. ID: " + this.workerId);
        System.out.println("Worker status: " + this.isAlive());

        this.quickSort(this.array, this.low, this.high);

        System.out.println("Stop worker. ID: " + this.workerId);
        WorkerManager.workersCount--;
    }

    protected void quickSort(double[] array, int low, int high) {
        /*int i = low, j = high;
        double pivot = array[low + (high - low) / 2];

        while (i <= j) {
            while (array[i] < pivot) {
                i++;
            }

            while (array[j] > pivot) {
                j--;
            }

            if (i <= j) {
                this.exchange(array, i, j);
                i++;
                j--;
            }
        }

        if (low < j) {
            quickSort(array, low, j);
        }

        if (i < high) {
            sort(array, i, high);
        }*/

        int len = high - low + 1;
        if (len <= 1) {
            return;
        }

        double pivot = array[low + (high - low) / 2];
        exchange(array, low + (high - low) / 2, high);

        int storeIndex = low;
        for (int i = low; i < high; i++) {
            if (array[i] < pivot) {
                exchange(array, i, storeIndex);
                storeIndex++;
            }
        }

        exchange(array, storeIndex, high);

        sort(array, low, storeIndex - 1);
        quickSort(array, storeIndex + 1, high);
    }

    protected void exchange(double[] array, int i, int j) {
        double tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

    protected void sort(double[] array, int low, int high) {
        if (WorkerManager.workersCount < WorkerManager.WORKERS_LIMIT) {
            try {
                WorkerManager.createWorker(array, low, high);
            } catch (InterruptedException e) {
                System.out.println("QuickSort worker was down. Reason: " + e.getMessage() + "\n");
                e.printStackTrace();
            }
        } else {
            this.quickSort(array, low, high);
        }
    }
}

WorkerManager 的下一个代码:

public class WorkerManager {

    public static final int MAX_WORKER_COUNT = 10;
    public static int WORKERS_LIMIT = 0;
    public static int workersCount = 0;

    private double _startTime = 0;
    private double _stopTime = 0;
    private double _workTime = 0;

    public void createTask(double[] data, int workerCount) throws WorkerManagerException {  
        if (workerCount > MAX_WORKER_COUNT) {
            throw new WorkerManagerException("Worker count cant be more than " + MAX_WORKER_COUNT);
        }

        try {
            WORKERS_LIMIT = workerCount;
            this.startTimer();
            WorkerManager.createWorker(data, 0, data.length - 1);
            this.stopTimer();

            System.out.println("\nWorktime: " + this.getWorkTime() + " milliseconds.");
        } catch (InterruptedException e) {
            System.out.println("QuickSort worker was down. Reason: " + e.getMessage() + "\n");
            e.printStackTrace();
        }
    }

    public static void createWorker(double[] array, int low, int high) throws InterruptedException {
        QuickSortWorker worker = new QuickSortWorker(array, low, high);
        worker.start();
        worker.join();
    }

    protected void startTimer() {
        this._startTime = System.currentTimeMillis(); 
    }

    protected void stopTimer() {
        this._stopTime = System.currentTimeMillis();
    }

    private void setWorkTime() {
        this._workTime = (this._startTime == 0)
                ? 0
                : this._stopTime - this._startTime;
    }

    private double getWorkTime() {
        if (this._workTime == 0) {
            this.setWorkTime();
        }
        return this._workTime;
    }
}

Answer 1

您在主线程中创建工作线程，一旦开始，您就会阻塞主线程(加入)并等待工作线程完成:

 QuickSortWorker worker = new QuickSortWorker(array, low, high);
 worker.start();
 worker.join();

这不会为您提供所需的并行性。在任何给定时间都只有一个线程在工作 - 这就是没有性能提升的原因。