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

Ответ 1

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

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

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

Ответ 2

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

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

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

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

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

Ответ 3

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

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

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

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

Ответ 4

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

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

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

Ответ 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 (результат сравнения будет в основном ложным).

Ответ 6

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

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