Python: взять max N элементов из некоторого списка

Question

Есть ли какая-то функция, которая вернет мне N наивысших элементов из какого-то списка?

I.e. если max(l) возвращает единственный самый высокий элемент, sth. как max(l, count=10) вернет мне список из 10 самых высоких чисел (или меньше, если l меньше).

Или что было бы эффективным простым способом получить их? (За исключением очевидной канонической реализации, а также нет таких вещей, которые связаны с сортировкой всего списка во-первых, потому что это было бы неэффективно по сравнению с каноническим решением.)

Answer 1

heapq.nlargest:

>>> import heapq, random 
>>> heapq.nlargest(3, (random.gauss(0, 1) for _ in xrange(100))) 
[1.9730767232998481, 1.9326532289091407, 1.7762926716966254] 

Answer 2

Довольно эффективное решение - это вариант быстрой сортировки, где рекурсия ограничена правая часть оси до положения точки поворота выше, чем число элементов, необходимых (с несколькими дополнительными условиями для решения пограничных случаев, конечно).

В стандартной библиотеке есть heapq.nlargest, как указано другими здесь.

Answer 3

Старт с первым 10 из L, вызовите X. Заметим, что минимальное значение X.

Цикл по L [I] для г над остальной частью L.

Если L [я] больше, чем min (X), падение min (X) из X и вставить L [i]. Возможно, вам нужно сохранить X как отсортированный связанный список и сделать вставку. Обновить мин (X).

В конце концов, у вас есть 10 наибольших значений в X.

Я подозреваю, что будет O (кН) (где к 10 здесь), так как сортировка вставкой линейна. Может быть, что использует GSL, так что если вы можете прочитать некоторые C код:

http://www.gnu.org/software/gsl/manual/html_node/Selecting-the-k-smallest-or-largest-elements.html

Наверное что-то в NumPy, что делает это.

Answer 4

Функция в стандартной библиотеке, что делает это heapq.nlargest