Оптимальный алгоритм возврата значений топ k из массива длины N

Question

У меня есть массив n чисел с плавающей запятой, и я хочу вернуть верхнюю к (в моем случае n ~ 100, k ~ 10)

Существует ли известный оптимальный путь решения этой проблемы?

Может ли кто-нибудь предоставить алгоритм C?

РЕДАКТИРОВАТЬ: на самом деле есть две проблемы: отсортированные и несортированные. Меня интересуют несортированные, которые должны быть быстрее!

Answer 1

Вы можете сделать это в O(n), используя алгоритм выбора . Найдите k самый большой элемент с алгоритмом разбиения, тогда все элементы после него будут больше его, и это ваш топ k.

Если вам нужны эти топы k в отсортированном порядке, вы можете отсортировать их по O(k log k).

Answer 2

Метод 1

Так как k мало, вы можете использовать метод турнира, чтобы найти kth наибольшее. Этот метод описан в книге Кнута «Искусство программирования», том 3, стр. 212.

Сначала создайте турнир на n-k + 2 элемента. Что-то вроде турнира по нокаут-теннису. Сначала вы разбиваетесь на пары и сравниваете членов пар (как будто эти двое сыграли матч, а один проиграл). Затем победители, вы снова делитесь на пары и так далее, пока не получите победителя. Вы можете просмотреть его как дерево с победителем наверху.

Это занимает n-k + 1 сравнение точно.

Теперь победитель этих n-k + 2 не может быть вашим k-м по величине элементом. Подумайте о своем пути P до турнира.

Из оставшихся k-2 теперь выберите один и следуйте по пути P, который даст вам новый по величине. По сути, вы переделываете турнир с заменой предыдущего победителя на один из k-2 элементов. Пусть P будет путем нового победителя. Теперь выберите другой из k-3 и следуйте по новому пути вверх и т. Д.

В конце, после того как вы исчерпали k-2, замените самое большое на -infinity, и самый большой из турниров будет k-м самым большим. Элементы, которые вы выбросили, являются верхними элементами k-1.

Требуется не более n - k + (k-1) [log (n-k+2)] сравнений, чтобы найти верхнюю k. Он использует O (N) памяти, хотя.

С точки зрения количества сравнений это, вероятно, должно превзойти любые алгоритмы выбора.

Метод 2

В качестве альтернативы вы можете поддерживать минимальную кучу из k элементов.

Сначала вставьте k элементов. Затем для каждого элемента массива, если он меньше элемента min кучи, выбросьте его. В противном случае, delete-min кучи и вставить элемент из массива.

В конце, куча будет содержать верхние k элементов. Это займет O(n log k) сравнений.

Конечно, если n мало, просто достаточно отсортировать массив. Код тоже будет проще.

Answer 3

Краткий ответ: нет.

Более длинный ответ: да, известно несколько взаимно несовместимых оптимальных решений. Это зависит от n, k и от того, какие свойства массива вы можете гарантировать.

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

Точно так же верхняя граница сложности - O (n.log (n)), потому что вы всегда можете найти ответ, отсортировав массив (O (n.log (n))) и вернув первые 10 элементов (O ( 1)).

Линейный поиск, сравнивающий каждый элемент с десятым самым высоким из найденных к настоящему моменту и вставляющий его в соответствующем месте в списке элементов с наибольшим количеством найденных к настоящему моменту при необходимости, имеет аналогичную сложность для сценариев среднего и наилучшего вариантов и имеет наихудший случай O (kn), который значительно лучше, чем O (n-квадрат). Для ожидаемых размеров я ожидаю, что этот метод будет работать хорошо.

Если бы n было намного больше (~ 10000) и k было бы увеличено в том же соотношении, то, вероятно, стоило бы реализовать алгоритм быстрого выбора. Быстрый выбор работает лучше, чем больше элементов вы хотите. Однако, если k не увеличилось в масштабе с n, вам следует придерживаться линейного поиска. Быстрый выбор и друзья изменяют исходный массив, поэтому они менее подходят, если вы не можете сделать это на месте, потому что вам нужно гораздо больше памяти и много копирования, что не включает сложность алгоритма.

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

Answer 4

Ниже приведено элегантное решение на основе кучи на Java со сложностью O (nlogK). Это не самый эффективный, но я думаю, что это достаточно легко понять. Вы можете изменить Integer на Float, если хотите использовать решение с плавающей запятой

import java.util.Arrays;
import java.util.PriorityQueue;

public class FindKLargest {

public static void find(int[] A, int k) {

    PriorityQueue<Integer> pq = new PriorityQueue<>(k);// Min heap because the element has to be greater
                                                        // than the smallest element in the heap in order
                                                        // to be qualified to be a member of top k elements.
    for (int i = 0; i < A.length; i++) {
        if (i < k) // add until heap is filled with k elements.
            pq.add(A[i]);
        else if (pq.peek() < A[i]) { // check if it's bigger than the
                                        // smallest element in the heap.
            pq.poll();
            pq.add(A[i]);
        }
    }
    int[] topK = new int[pq.size()];
    int index = 0;
    while (index != k)
        topK[index++] = pq.poll();
    System.out.println(Arrays.toString(topK));
}

public static void main(String[] args) {
    int[] arr = { 1, -2, -3, -4, -5 };
    find(arr, 4);
}

}

Answer 5

если у вас есть необычный графический процессор, я могу рассказать вам, как вычислить верхний огромный k из огромных n экземпляров одновременно, поэтому распределите их по текстуре для каждого экземпляра и добавьте смесь к текстуре с помощью их«высота» как позиция вдоль текстуры.

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

вы клонируетепозиции.(Вы должны получить 2, если есть 2, 10, если есть 10) во всех случаях.(просто скажите, что все это на текстуре 8192x8192, 64x64 из этих «высотных» блоков.) и вы также пропускаете слоты с 0 счетами.

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

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

имеет больше смысла делать это, если все они были созданы снова, то это обнаружение потока на порог.(просто скажите, что вы запускали ANN 128x128 раз одновременно, (кто-нибудь изменяет перевод?), тогда это имеет смысл.

и достигните пороговой высоты для этого количества, но это приблизительно ... так что вы получитеприблизительное число k для n списков.

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