Найти топ N элементов в массиве

Question

Какое было бы наилучшее решение, чтобы найти верхние N (скажем, 10) элементов в неупорядоченном списке (скажем, 100).

Решение, которое пришло мне в голову, состояло в том, чтобы 1. отсортировать его с помощью быстрой сортировки2. получить топ 10.

Но есть ли лучшая альтернатива?

Answer 1

Время может быть уменьшено до линейного:

1. Используйте алгоритм выбора , который эффективно находит k-й элемент в несортированном массиве влинейное времяВы можете использовать вариант быстрой сортировки или более надежные алгоритмы.

2. Получите вершину k, используя пивот, полученный на шаге 1.

Answer 2

Как насчет делегирования всего Java;)

function findTopN(Array list, int n)
{
    Set sortedSet<Integer> = new TreeSet<>(Comparators.naturalOrder());

    // add all elements from list to sortedSet

    // return the first n from sortedSet
}

Я не пытаюсь сказать, что это лучший способ. Я все еще думаю, что метод Инь Чжу по нахождению k-го наибольшего элемента - лучший ответ.

Answer 3

Если вы имеете дело с простыми элементами, такими как целые числа фиксированной длины, то при условии, что вы можете сэкономить буфер памяти того же размера, что и входные данные, сортировка может быть выполнена за O (n) время с использованием сортировки по сегментам или по осям. и это будет самый быстрый.

Хотя существуют алгоритмы линейного выбора времени, скрытая постоянная очень высока - около 24 . Это означает, что алгоритм O (nlog n), как правило, будет быстрее для менее чем нескольких миллионов элементов.

В противном случае, в общем случае, когда вы можете сравнить только 2 элемента и определить, какой из них больше, проблему лучше всего решить с помощью структуры данных кучи .

Предположим, вы хотите, чтобы k лучших из n предметов. Все решения, основанные на полной сортировке данных, требуют времени O (nlog n), в то время как использование кучи требует только времени O (nlog k) - просто создайте кучу на первых k элементах, затем продолжайте добавлять элемент и удалять максимум. Это оставит вас с кучей, содержащей самые маленькие k элементов.

Answer 4

Да, вы можете сделать это в O (n), просто сохранив (отсортированный) рабочий список верхнего N. Вы можете отсортировать рабочий список, используя обычные библиотечные функции или сеть сортировки .Например, простая демонстрация с использованием 3 и показом, какие элементы в рабочем списке меняют каждую итерацию.

5 2 8 7 9

i = 0
top[0] <= 5

i = 1
top[1] <= 2

i = 2
top[2] <= top[1] (2)
top[1] <= top[0] (5)
top[0] <= 8

i = 3
top[2] <= top[1] (5)
top[1] <= 7

i = 4
top[2] <= top[1] (7)
top[1] <= top[0] (8)
top[0] <= 9

Answer 5

Лучшее решение - использовать любые средства, которые предоставляет выбранный вами язык, что облегчит вашу жизнь.

Однако, предполагая, что этот вопрос больше связан с тем, какой алгоритм вы должны выбрать, я собираюсь предложить здесь другой подход. Если вы говорите о 10 из 100, вам не следует беспокоиться о производительности, если только вы не хотите делать это много раз в секунду.

Например, этот C-код (который настолько же неэффективен, насколько я могу это сделать, не будучи глупым) все еще занимает менее одной десятой секунды для выполнения. Мне не хватает времени даже подумать о том, чтобы пойти выпить кофе.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define SRCSZ 100
#define DSTSZ 10

int main (void) {
    int unused[SRCSZ], source[SRCSZ], dest[DSTSZ], i, j, pos;

    srand (time (NULL));
    for (i = 0; i < SRCSZ; i++) {
        unused[i] = 1;
        source[i] = rand() % 1000;
    }

    for (i = 0; i < DSTSZ; i++) {
        pos = -1;
        for (j = 0; j < SRCSZ; j++) {
            if (pos == -1) {
                if (unused[j]) {
                    pos = j;
                }
            } else {
                if (unused[j] && (source[j] > source[pos])) {
                    pos = j;
                }
            }
        }
        dest[i] = source[pos];
        unused[pos] = 0;
    }

    printf ("Source:");
    for (i = 0; i < SRCSZ; i++) printf (" %d", source[i]);
    printf ("\nDest:");
    for (i = 0; i < DSTSZ; i++) printf (" %d", dest[i]);
    printf ("\n");

    return 0;
}

Пропуск через time дает вам (я немного отформатировал вывод, чтобы сделать его читабельным, но не повлиял на результаты):

Source: 403 459 646 467 120 346 430 247 68 312 701 304 707 443
        753 433 986 921 513 634 861 741 482 794 679 409 145 93
        512 947 19 9 385 208 795 742 851 638 924 637 638 141
        382 89 998 713 210 732 784 67 273 628 187 902 42 25
        747 471 686 504 255 74 638 610 227 892 156 86 48 133
        63 234 639 899 815 986 750 177 413 581 899 494 292 359
        60 106 944 926 257 370 310 726 393 800 986 827 856 835
        66 183 901
Dest: 998 986 986 986 947 944 926 924 921 902

real    0m0.063s
user    0m0.046s
sys     0m0.031s

Только когда количество чисел станет большим, вы обычно будете беспокоиться. Не поймите меня неправильно, я не говорю, что вы не должны думать о производительности. Чего не следует делать, так это тратить слишком много времени на оптимизацию неважных вещей - YAGNI и всего этого джаза.

Как и во всех вопросах оптимизации, мера не угадать!

Answer 6

Вы можете использовать List и класс Comparators Гуавы, чтобы получить желаемые результаты.Это высоко оптимизированное решение.Пожалуйста, посмотрите образец ниже, который получает 5 лучших номеров.Api можно найти здесь .

import java.util.Comparator;
import java.util.List;
import java.util.stream.Collector;

import org.junit.Test;

import com.google.common.collect.Comparators;
import com.google.common.collect.Lists;

public class TestComparator {

    @Test
    public void testTopN() {
        final List<Integer> numbers = Lists.newArrayList(1, 3, 8, 2, 6, 4, 7, 5, 9, 0);
        final Collector<Integer, ?, List<Integer>> collector = Comparators.greatest(5,
                Comparator.<Integer>naturalOrder());
        final List<Integer> top = numbers.stream().collect(collector);
        System.out.println(top);
    }

}

Выход: [9, 8, 7, 6, 5]

Answer 7

Записано под реализациями сортировки выбора и вставки.Для большего набора данных я рекомендую сортировку вставками лучше, чем сортировку выбора

public interface FindTopValues
{
  int[] findTopNValues(int[] data, int n);
}

Реализация сортировки вставкой:

public class FindTopValuesInsertionSortImpl implements FindTopValues {  

/**
 * Finds list of the highest 'n' values in the source list, ordered naturally, 
 * with the highest value at the start of the array and returns it 
 */
@Override
public int[] findTopNValues(int[] values, int n) {

    int length = values.length;
    for (int i=1; i<length; i++) {
        int curPos = i;
        while ((curPos > 0) && (values[i] > values[curPos-1])) {
            curPos--;
        }

        if (curPos != i) {
            int element = values[i];
            System.arraycopy(values, curPos, values, curPos+1, (i-curPos));
            values[curPos] = element;
        }
    }       

    return Arrays.copyOf(values, n);        
}   

}

Реализация сортировки выбора:

public class FindTopValuesSelectionSortImpl implements FindTopValues {

/**
 * Finds list of the highest 'n' values in the source list, ordered naturally, 
 * with the highest value at the start of the array and returns it 
 */
@Override
public int[] findTopNValues(int[] values, int n) {
    int length = values.length;

    for (int i=0; i<=n; i++) {
        int maxPos = i;
        for (int j=i+1; j<length; j++) {
            if (values[j] > values[maxPos]) {
                maxPos = j;
            }
        }

        if (maxPos != i) {
            int maxValue = values[maxPos];
            values[maxPos] = values[i];
            values[i] = maxValue;
        }           
    }
    return Arrays.copyOf(values, n);        
}
}

Answer 8

Ну, вы можете создать кучу из несортированного массива за O (n) время, и вы можете получить верхний элемент из кучи за O (log (n)) время.Таким образом, ваше общее время выполнения O (n + k * log (n)).

Answer 9

public class FindTopValuesSelectionSortImpl implements FindTopValues {

/**
 * Finds list of the highest 'n' values in the source list, ordered naturally, 
 * with the highest value at the start of the array and returns it 
 */
@Override
public int[] findTopNValues(int[] values, int n) {
    int length = values.length;

    for (int i=0; i<=n; i++) {
        int maxPos = i;
        for (int j=i+1; j<length; j++) {
            if (values[j] > values[maxPos]) {
                maxPos = j;
            }
        }

        if (maxPos != i) {
            int maxValue = values[maxPos];
            values[maxPos] = values[i];**strong text**
            values[i] = maxValue;
        }           
    }
    return Arrays.copyOf(values, n);        
}
}

Answer 10

Лучший алгоритм в целом будет зависеть от размера K. Если K мало, то просто следуя алгоритму BubbleSort и итерируя K раз по внешнему циклу, вы получите верхние значения K.Сложность будет O (n * k).

Однако для значений K, близких к n, сложность приблизится к O (n ^ 2).В таком случае быстрая сортировка может быть хорошей альтернативой.