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

StackOverflow https://stackoverflow.com/questions/1218922

  •  10-07-2019
  •  | 
  •  

Вопрос

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

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

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

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

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

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

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

Это было полезно?

Решение

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

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

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

Другие советы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top