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

}

有人可以帮忙吗？谢谢。

标签： javamultithreading

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 );
                }
            }
        }
    }
}

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