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

Selection algorithms should help here.

A very easy solution is to find the 100th biggest element, then run through the list picking off elements that are bigger than this element. That will give you the 100 biggest elements. This is linear in the length of the list; this is best possible.

There are more sophisticated algorithms. A heap, for example, is very amenable to this problem. The heap based algorithm is n log k where n is the length of the list and k is the number of largest elements that you want to select.

There's a discussion of this problem on the Wikipedia page for selection algorithms.

Edit: Another poster has pointed out that Python has a built in solution to this problem. Obviously that is far easier than rolling your own, but I'll keep this post up in case you would like to learn about how such algorithms work.

You can use a Heap data structure. A heap will not necessarily be ordered, but it is a fairly fast way to keep semi-ordered data, and it has the benefit of the smallest item always being the first element in the heap.

A heap has two basic operations that will help you: Add and Replace.

Basically what you do is add items to it until you get to a 100 items (your top N number per your question). Then after that, you replace the first item with every new item, as long as the new item is bigger than the first item.

Whenever you replace the first item with something bigger, the internal code in the heap will adjust the heap contents so that if the new item is not the smallest, it will bubble up into the heap, and the smallest item will "bubble down" to the first element, ready to be replaced along the way.

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

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

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

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

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

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

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

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

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

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