使用多线程查找数组中的 N 个最大元素

Question

我有一个简单的问题：给定一个数字数组，找到数组的 N 个最大数字，但我需要使用多线程来解决这个问题，比如使用 10 个线程。我不想对数组进行排序：只需遍历它，并将每个元素与大小为 N 的结果数组的最小值进行比较（用 初始化Double.MIN_VALUE）。遍历数组后，结果数组将包含我输入数组的最大 N 个元素。

对于多线程，我不希望每个线程都有一个结果数组，这样我以后就不必合并它们。这就是为什么我希望所有线程都对共享结果数组进行操作。我意识到这不是最好的解决方案，但我仍然想了解我应该如何实现它。我试过这个，但它不起作用：

public class Problem {

private static final int MY_THREADS = 10;

public static void main(String[] args) {

    double[] array = {...};

    double[] maximums = new double[3];

    for (int i = 0; i < maximums.length; ++i) {

        maximums[i] = Double.MIN_VALUE;

    }

    ExecutorService executor = Executors.newFixedThreadPool(MY_THREADS);

    Runnable worker = new MyRunnable(array, maximums);

    executor.execute(worker);

    executor.shutdown();

    while (!executor.isTerminated()) {

    }

    System.out.println(Arrays.toString(maximums));

}

public static class MyRunnable implements Runnable {

    private double[] array;

    private double[] maximums;

    MyRunnable(double[] array, double[] maximums) {

        this.array = array;

        this.maximums = maximums;

    }

    @Override

    public void run() {

        int i = 0;

        while (i < array.length) {

            if (array[i] > maximums[getMinIndex(maximums)]) {

                maximums[getMinIndex(maximums)] = array[i];

            }

            ++i;

        }

    }

}

private static int getMinIndex(double[] array) {

    int minIndex = -1;

    double min = Double.MAX_VALUE;

    for (int i = 0; i < array.length; ++i) {

        if (array[i] < min) {

            min = array[i];

            minIndex = i;

        }

    }

    return minIndex;

}

}

有人可以帮忙吗？谢谢。

Answer 1

我不知道你为什么要多线程这样的东西，然后还要避免排序 - 但是suuuuuuureeeee。你可以这样做：class Problem {&nbsp; &nbsp; private static final int MY_THREADS = 10;&nbsp; &nbsp; private static final double[] maximums = new double[3];&nbsp; &nbsp; public static void main(String[] args) {&nbsp; &nbsp; &nbsp; &nbsp; double[] array = {...};&nbsp; &nbsp; &nbsp; &nbsp; for ( int i = 0; i < maximums.length; ++i) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; maximums[i] = Double.MIN_VALUE; //Remember that this won't work with negative values in array&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; ExecutorService executor = Executors.newFixedThreadPool(MY_THREADS);&nbsp; &nbsp; &nbsp; &nbsp; int start = 0;&nbsp; &nbsp; &nbsp; &nbsp; int length = array.length/MY_THREADS;&nbsp; &nbsp; &nbsp; &nbsp; for( int i = 0; i < MY_THREADS; i++ )&nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; //You probably want to give it only part of array to consider,&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; //otherwise you are wasting resources and might even try to insert same element more than once.&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; Runnable worker = new MyRunnable(Arrays.copyOfRange( array, start, start + length ) );&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; executor.execute(worker);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; start += length;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; executor.shutdown();&nbsp; &nbsp; &nbsp; &nbsp; while (!executor.isTerminated()) {&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; System.out.println( Arrays.toString( maximums ));&nbsp; &nbsp; }&nbsp; &nbsp; //This is unsynchronized - but with this problem - it will at worst cause unnecessary insert attempt.&nbsp; &nbsp; private static int getMinIndex() {&nbsp; &nbsp; &nbsp; &nbsp; int minIndex = -1;&nbsp; &nbsp; &nbsp; &nbsp; double min = Double.MAX_VALUE;&nbsp; &nbsp; &nbsp; &nbsp; for (int i = 0; i < maximums.length; ++i) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (maximums[i] < min) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; min = maximums[i];&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; minIndex = i;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; return minIndex;&nbsp; &nbsp; }&nbsp; &nbsp; //You have to synchronize the insertion somehow,&nbsp; &nbsp; // otherwise you might insert two values into same spot losing one of max.&nbsp; &nbsp; private static synchronized void insertIntoMaximum( double k ){&nbsp; &nbsp; &nbsp; &nbsp; int minIndex = getMinIndex();&nbsp; &nbsp; &nbsp; &nbsp; if( maximums[minIndex] < k ){&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; maximums[minIndex] = k;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; public static class MyRunnable implements Runnable {&nbsp; &nbsp; &nbsp; &nbsp; private double[] array;&nbsp; &nbsp; &nbsp; &nbsp; //Since its inner class, I didn't think passing maximums into it was necessary.&nbsp; &nbsp; &nbsp; &nbsp; // You could pass it here, but you would still probably need to call parent for insertion.&nbsp; &nbsp; &nbsp; &nbsp; MyRunnable(double[] array) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; this.array = array;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; @Override&nbsp; &nbsp; &nbsp; &nbsp; public void run() {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; //this while was an interesting attempt at making indexed for, that doesn't even need to be indexed.&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; for( double v : array )&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if( v > maximums[getMinIndex()] )&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; insertIntoMaximum( v );&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }}我仍然可能会避免使用多线程，创建一个新线程可能非常昂贵 - 所以它很可能甚至不会节省时间，特别是考虑到您仍然需要同步插入。