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

Question

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

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

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

Answer 1

heapq.nlargest * * 1004

>>> 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] для i по остальной части L.

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

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

Я подозреваю, что это будет O (kN) (где k здесь 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, как указано другими здесь.