Как получить самые большие номера из огромного количества номеров?

Question

Я хотел бы получить самые большие 100 элементов из списка не менее 100000000 номеров.

Я мог бы отсортировать весь список и просто взять последние 100 элементов из отсортированного списка, но это было бы очень дорого с точки зрения как памяти, так и времени.

Есть ли какой-либо существующий простой, питонический способ сделать это?

То, что я хочу, это функция вместо чистой сортировки. На самом деле я не хочу тратить время на сортировку элементов, которые мне все равно.

Например, это функция, которую я хотел бы иметь:

getSortedElements(100, lambda x,y:cmp(x,y)) 

Примечание это требование только для точки зрения производительности.

Answer 1

Модуль heapq в стандартной библиотеке предлагает функцию nlargest(), чтобы сделать это:

top100 = heapq.nlargest(100, iterable [,key]) 

Это не сортирует весь список, так что вы не будете тратить время на элементы, которые вы не» нужно.

Answer 2

Selection algorithms должен помочь здесь.

Очень простое решение состоит в том, чтобы найти 100-й самый большой элемент, а затем запустить список, отбирающий элементы, которые больше, чем этот элемент. Это даст вам 100 самых больших элементов. Это линейно по длине списка; это возможно.

Есть более сложные алгоритмы. A heap, например, очень поддается этой проблеме. Алгоритм, основанный на куче, равен n log k, где n - это длина списка, а k - это число наибольших элементов, которые вы хотите выбрать.

Существует обсуждение этого problem на странице Википедии для алгоритмов выбора.

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

Answer 3

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

Куча имеет две основные операции, которые помогут вам: Добавить и заменить.

В основном, что вы делаете, это добавлять к нему предметы, пока вы не доберетесь до 100 предметов (ваше первое число N на ваш вопрос). Затем после этого вы заменяете первый элемент каждым новым элементом, если новый элемент больше, чем первый элемент.

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

Answer 4

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

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

Как уже упоминалось в python, вы использовали бы heapq. В Java PriorityQueue: http://java.sun.com/javase/6/docs/api/java/util/PriorityQueue.html

Answer 5

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

Инициализация:

Make an array of 100 elements and initialise all elements 
with a low value (less than any value in your input list). 

Initialise an integer variable to 0 (or any value in 
[0;99]), say index_minvalue, that will point to the 
current lowest value in the array. 

Initialise a variable, say minvalue, to hold the current 
lowest value in the array. 

Для каждого значение, например current_value, в списке входных данных:

if current_value > minvalue 

    Replace value in array pointed to by index_minvalue 
    with current_value 

    Find new lowest value in the array and set index_minvalue to 
    its array index. (linear search for this will be OK as the array 
    is quickly filled up with large values) 

    Set minvalue to current_value 

else 
    <don't do anything!> 

minvalue wil l быстро получить высокое значение и, следовательно, большинство значений в списке входных данных нужно будет только сравнить с minvalue (результат сравнения будет в основном ложным).

Answer 6

Для алгоритмов weenies в аудитории: вы можете сделать это с помощью простого изменения в алгоритме Тони Хоара Find:

find(topn, a, i, j) 
    pick a random element x from a[i..j] 
    partition the subarray a[i..j] (just as in Quicksort) 
    into subarrays of elements <x, ==x, >x 
    let k be the position of element x 
    if k == 0 you're finished 
    if k > topn, call find(topn, a, i, k) 
    if k < topn, call find(topn-k, k, j) 

Этот алгоритм ставит крупнейшие topn элементы в первых topn элементов массива a, без сортировки. Конечно, если вы хотите, чтобы они отсортировались или просто для простоты, куча лучше, а вызов библиотечной функции еще лучше. Но это классный алгоритм.