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

Question

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

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

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

Мне нужна следующая функция вместо чистой сортировки. На самом деле я не хочу тратить время на сортировку элементов, которые мне безразличны.

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

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

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

Answer 1

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

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

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

Answer 2

Алгоритмы выбора должны помочь здесь.

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

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

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

Редактировать: Другой автор указал, что 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 быстро получит высокое значение и, следовательно, большинство значений в списке ввода нужно будет только сравнить с minvalue (результат сравнения будет в основном ложным).

Answer 6

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

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, без их сортировки. Конечно, если вы хотите, чтобы они были отсортированы, или для простоты, куча лучше, и вызов библиотечной функции все же лучше. Но это крутой алгоритм.