Java 线程 CPU 用法

Question

我目前正在尝试使用线程在 Java 中编写快速排序算法。但是 CPU 利用率永远不会是 100%，无论数组的长度如何。你能帮我找出问题所在吗？这是我的代码：

import java.util.Random;

public class Main {

    public static void main(String[] args) {
        int[] arr;
        Random random = new Random();
        arr = new int[53000000];
        for (int i = 0; i < arr.length; i++){
            arr[i] = random.nextInt();
        }
        SortThread sortThread = new SortThread(arr, 0, arr.length - 1);
        Thread threadSort = new Thread(sortThread);
        threadSort.start();
    }

}
public class SortThread implements Runnable {

    private int[] arr;
    private int start;
    private int end;

    public SortThread(int[] arr, int start, int end) {
        this.arr = arr;
        this.start = start;
        this.end = end;
    }

    @Override
    public void run() {

        if (start < end){
            int partitionIndex = partition(arr, start, end);
            SortThread sortThreadLeft = new SortThread(arr, start, partitionIndex - 1);
            SortThread sortThreadRight = new SortThread(arr, partitionIndex + 1, end);
            Thread sortLeft = new Thread(sortThreadLeft);
            Thread sortRight = new Thread(sortThreadRight);
            sortLeft.start();
            sortRight.start();
        }
    }

    private int partition(int arr[], int begin, int end){

        int pivot = arr[end];
        int i = (begin - 1);

        for (int j = begin; j < end; j++){
            if (arr[j] <= pivot ){
                i++;
                int swpTemp = arr[i];
                arr[i] = arr[j];
                arr[j] = swpTemp;
            }
        }

        int swapTemp = arr[i + 1];
        arr[i + 1] = arr[end];
        arr[end] = swapTemp;
        return i + 1;
    }
}

在 Main class 中我定义了带有随机元素的数组。在 SortThread class 中，我使用快速排序算法对数组进行排序。每个子数组在不同的线程中分别排序。理论上这应该占据每个 CPU 的所有处理能力。但实际上只使用了 40%，无论数组的长度如何。

Answer 1

我是怎么解决的：

import java.util.concurrent.Executors;
import java.util.concurrent.ThreadPoolExecutor;

public class Main {

    static long start;

    public static void main(String[] args) {
        int numOfThreads = 8;
        try {
            numOfThreads = Integer.parseInt(args[0]);
            System.out.println("Number of threads: " + numOfThreads);
        } catch (Exception e) {
            System.out.println("Invalid number of threads: Default 8");
        }

        SortThread.executor = (ThreadPoolExecutor) Executors.newFixedThreadPool(numOfThreads);

        int[] arr = new int[Integer.parseInt(args[1])];
        for (int i = 0; i < arr.length; i++){
            arr[i] = (int)(Math.random() * 256) + 1;
        }

        SortThread sortThread = new SortThread(arr, 0, arr.length - 1);
        Thread threadSort = new Thread(sortThread);
        start = System.nanoTime();
        threadSort.start();
    }

}

class SortThread implements Runnable {
    static ThreadPoolExecutor executor;

    private int[] arr;
    private int start;
    private int end;

    public SortThread(int[] arr, int start, int end) {

        this.arr = arr;
        this.start = start;
        this.end = end;

    }

    @Override
    public void run() {

        if (start < end){
            int partitionIndex = partition(arr, start, end);

            SortThread sortThreadLeft = new SortThread(arr, start, partitionIndex - 1);
            SortThread sortThreadRight = new SortThread(arr, partitionIndex + 1, end);

            Thread sortLeft = new Thread(sortThreadLeft);
            Thread sortRight = new Thread(sortThreadRight);

            SortThread.executor.execute(sortLeft);
            SortThread.executor.execute(sortRight);
        } else {
            if (SortThread.executor.getQueue().size() == 0 && SortThread.executor.getActiveCount() == 1) {
                System.out.println((System.nanoTime() - Main.start)/1000000);
                SortThread.executor.shutdown();
            }
        }
    }

    private static int partition(int[] arr, int begin, int end){

        int pivot = arr[end];
        int i = (begin - 1);

        for (int j = begin; j < end; j++){
            if (arr[j] <= pivot ){

                i++;
                int swpTemp = arr[i];
                arr[i] = arr[j];
                arr[j] = swpTemp;

            }
        }

        int swapTemp = arr[i + 1];
        arr[i + 1] = arr[end];
        arr[end] = swapTemp;

        return i + 1;
    }
}

刚刚创建了执行器并将它们全部添加到池中。

Java 线程 CPU 用法

Java Thread CPU usage

java

multithreading

quicksort