Поиск N-го элемента в несортированном списке без сортировки списка

Question

Эй. У меня очень большой массив, и я хочу найти N-е наибольшее значение. Обычно я могу отсортировать массив и затем взять N-й элемент, но меня интересует только один элемент, так что, возможно, есть лучший способ, чем сортировка всего массива ...

Answer 1

Куча - лучшая структура данных для этой операции, и в Python есть отличная встроенная библиотека для этого, называемая heapq.

import heapq

def nth_largest(n, iter):
    return heapq.nlargest(n, iter)[-1]

Пример использования:

>>> import random
>>> iter = [random.randint(0,1000) for i in range(100)]
>>> n = 10
>>> nth_largest(n, iter)
920

Подтвердите результат сортировкой:

>>> list(sorted(iter))[-10]
920

Answer 2

Сортировка потребует минимум времени выполнения O (nlogn) - Есть очень эффективные алгоритмы выбора , которые могут решить вашу проблему за линейное время.

Partition-based selection (иногда Quick select), основанный на идее быстрой сортировки (рекурсивное разбиение), является хорошим решением (см. Ссылку для псевдокода + Другой пример ).

Answer 3

Вы можете попробовать метод Медиана медиан - его скорость равна O (N).

Answer 4

Простая модифицированная быстрая сортировка очень хорошо работает на практике. Он имеет среднее время пробега, пропорциональное N (хотя в худшем случае время пробега - O (N ^ 2)).

Действуй как быстрая сортировка. Выберите случайным образом значение пивота, затем просмотрите ваши значения и посмотрите, находятся ли они выше или ниже этого значения, и разбейте их на две ячейки на основе этого сравнения. В быстрой сортировке вы затем рекурсивно сортируете каждую из этих двух корзин. Но для вычисления N-го наибольшего значения вам нужно только отсортировать ОДИН из бинов. Население каждого бина сообщает вам, какой бин содержит ваше n-е наибольшее значение. Так, например, если вам нужно 125-е наивысшее значение, и вы сортируете по двум бинам, у которых 75 в «верхнем» бункере и 150 в «нижнем» бункере, вы можете игнорировать верхний бункер и просто перейти к поиску 125-75 = 50-е самое высокое значение только в нижнем бункере.

Answer 5

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

Answer 6

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

Однако вы можете сохранить ваши самые большие K-ые значения в виде двоичного дерева, и операция станет O (n log k).

Согласно Wikipedia, это лучший алгоритм выбора:

 function findFirstK(list, left, right, k)
     if right > left
         select pivotIndex between left and right
         pivotNewIndex := partition(list, left, right, pivotIndex)
         if pivotNewIndex > k  // new condition
             findFirstK(list, left, pivotNewIndex-1, k)
         if pivotNewIndex < k
             findFirstK(list, pivotNewIndex+1, right, k)

Его сложность O (n)

Answer 7

По сути, вы хотите создать список "top-N" и выбрать список в конце этого списка.

Таким образом, вы можете отсканировать массив один раз и вставить в пустой список, когда элемент largeArray больше, чем последний элемент вашего списка top-N, а затем удалить последний элемент.

После того, как вы закончите сканирование, выберите последний элемент в вашем списке топ-N.

Пример для целых и N = 5:

int[] top5 = new int[5]();
top5[0] = top5[1] = top5[2] = top5[3] = top5[4] = 0x80000000; // or your min value

for(int i = 0; i < largeArray.length; i++) {
    if(largeArray[i] > top5[4]) {
       // insert into top5:
       top5[4] = largeArray[i];

       // resort:
       quickSort(top5);
    }
}

Answer 8

Использовать heapsort. Это только частично упорядочивает список, пока вы не вытянете элементы.

Answer 9

Одна вещь, которую вы должны сделать, если она находится в рабочем коде, это проверить образцы ваших данных. Например, вы можете рассмотреть «большие» массивы из 1000 или 10000 элементов и создать метод быстрого выбора из рецепта.

Скомпилированная природа отсортированных и несколько скрытых и постоянно развивающихся оптимизаций делает его быстрее, чем написанный на python метод быстрого выбора для наборов данных малого и среднего размера (<1 000 000 элементов). Кроме того, вы можете обнаружить, что при увеличении размера массива сверх этого значения память более эффективно обрабатывается в собственном коде, и преимущество сохраняется. </p>

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