使用多线程查找数组中的 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 {

    private static final int MY_THREADS = 10;

    private static final double[] maximums = new double[3];

    public static void main(String[] args) {

        double[] array = {...};

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

            maximums[i] = Double.MIN_VALUE; //Remember that this won't work with negative values in array

        }

        ExecutorService executor = Executors.newFixedThreadPool(MY_THREADS);

        int start = 0;

        int length = array.length/MY_THREADS;

        for( int i = 0; i < MY_THREADS; i++ )

        {

            //You probably want to give it only part of array to consider,

            //otherwise you are wasting resources and might even try to insert same element more than once.

            Runnable worker = new MyRunnable(Arrays.copyOfRange( array, start, start + length ) );

            executor.execute(worker);

            start += length;

        }

        executor.shutdown();

        while (!executor.isTerminated()) {

        }

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

    }

    //This is unsynchronized - but with this problem - it will at worst cause unnecessary insert attempt.

    private static int getMinIndex() {

        int minIndex = -1;

        double min = Double.MAX_VALUE;

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

            if (maximums[i] < min) {

                min = maximums[i];

                minIndex = i;

            }

        }

        return minIndex;

    }

    //You have to synchronize the insertion somehow,

    // otherwise you might insert two values into same spot losing one of max.

    private static synchronized void insertIntoMaximum( double k ){

        int minIndex = getMinIndex();

        if( maximums[minIndex] < k ){

            maximums[minIndex] = k;

        }

    }

    public static class MyRunnable implements Runnable {

        private double[] array;

        //Since its inner class, I didn't think passing maximums into it was necessary.

        // You could pass it here, but you would still probably need to call parent for insertion.

        MyRunnable(double[] array) {

            this.array = array;

        }

        @Override

        public void run() {

            //this while was an interesting attempt at making indexed for, that doesn't even need to be indexed.

            for( double v : array )

            {

                if( v > maximums[getMinIndex()] )

                {

                    insertIntoMaximum( v );

                }

            }

        }

    }

}

我仍然可能会避免使用多线程，创建一个新线程可能非常昂贵 - 所以它很可能甚至不会节省时间，特别是考虑到您仍然需要同步插入。