Каков самый быстрый способ получить k наименьших (или наибольших) элементов массива в Java?

Во-первых, ваш метод бенчмаркинга неверен. Вы измеряете создание входных данных вместе с производительностью алгоритма, и вы не разогреваете JVM перед измерением. Результаты для вашего кода, при тестировании через JMH:

Benchmark                     Mode  Cnt      Score   Error  Units
CounterBenchmark.testHeap    thrpt    2  18103,296          ops/s
CounterBenchmark.testSimple  thrpt    2  59490,384          ops/s

Модифицированный бенчмаркпастебин .

Относительно 3-кратной разницы между двумя предоставленными решениями. В терминах Big-O нотации ваш первый алгоритм может показаться лучше, но на самом деле Big-O нотация только говорит вам, как алгоритм хорош с точки зрения масштабирования, он никогда не говорит вам, как быстро он работает (см. Также этот вопрос ). И в вашем случае масштабирование не является проблемой, так как ваш numNeighbours ограничен 20. Другими словами, обозначение big-O описывает, сколько тиков алгоритма необходимо для его завершения, но оно не ограничивает длительность тика, а просто говорит, что длительность тика не меняется при изменении входных данных. И с точки зрения сложности тика ваш второй алгоритм, безусловно, выигрывает.

Каков самый быстрый способ вычисления k наименьших элементов?

Я придумал следующее решение, которое, как я считаю, позволяет предсказанию ветвей делать свою работу:

@Benchmark
public void testModified(Blackhole bh) {
    final double[] scores = sampleData;
    int[] candidates = new int[numberNeighbours];
    for (int i = 0; i < numberNeighbours; i++) {
        candidates[i] = i;
    }
    // sorting candidates so scores[candidates[0]] is the largest
    for (int i = 0; i < numberNeighbours; i++) {
        for (int j = i+1; j < numberNeighbours; j++) {
            if (scores[candidates[i]] < scores[candidates[j]]) {
                int temp = candidates[i];
                candidates[i] = candidates[j];
                candidates[j] = temp;
            }
        }
    }
    // processing other scores, while keeping candidates array sorted in the descending order
    for (int i = numberNeighbours; i < numberExamples; i++) {
        if (scores[i] > scores[candidates[0]]) {
            continue;
        }
        // moving all larger candidates to the left, to keep the array sorted
        int j; // here the branch prediction should kick-in
        for (j = 1; j < numberNeighbours && scores[i] < scores[candidates[j]]; j++) {
            candidates[j - 1] = candidates[j];
        }
        // inserting the new item
        candidates[j - 1] = i;
    }
    bh.consume(candidates);
}

Результаты бенчмарка (в 2 раза быстрее, чем ваше текущее решение):

(10 neighbours) CounterBenchmark.testModified    thrpt    2  136492,151          ops/s
(20 neighbours) CounterBenchmark.testModified    thrpt    2  118395,598          ops/s

Другие упоминали быстрый выбор , но, как и следовало ожидать, сложность этого алгоритма пренебрегает его сильными сторонами в вашем случае:

@Benchmark
public void testQuickSelect(Blackhole bh) {
    final int[] candidates = new int[sampleData.length];
    for (int i = 0; i < candidates.length; i++) {
        candidates[i] = i;
    }
    final int[] resultIndices = new int[numberNeighbours];
    int neighboursToAdd = numberNeighbours;

    int left = 0;
    int right = candidates.length - 1;
    while (neighboursToAdd > 0) {
        int partitionIndex = partition(candidates, left, right);
        int smallerItemsPartitioned = partitionIndex - left;
        if (smallerItemsPartitioned <= neighboursToAdd) {
            while (left < partitionIndex) {
                resultIndices[numberNeighbours - neighboursToAdd--] = candidates[left++];
            }
        } else {
            right = partitionIndex - 1;
        }
    }
    bh.consume(resultIndices);
}

private int partition(int[] locations, int left, int right) {
    final int pivotIndex = ThreadLocalRandom.current().nextInt(left, right + 1);
    final double pivotValue = sampleData[locations[pivotIndex]];
    int storeIndex = left;
    for (int i = left; i <= right; i++) {
        if (sampleData[locations[i]] <= pivotValue) {
            final int temp = locations[storeIndex];
            locations[storeIndex] = locations[i];
            locations[i] = temp;

            storeIndex++;
        }
    }
    return storeIndex;
}

Результаты бенчмарка довольно расстраивают в этом корпус:

CounterBenchmark.testQuickSelect  thrpt    2   11586,761          ops/s