Есть ли какая-нибудь функция, которая вернет мне N наивысших элементов из некоторого списка?
т.е. если max(l) возвращает один высший элемент, sth. например, max(l, count=10) вернет мне список из 10 самых высоких чисел (или меньше, если l меньше).
Или что было бы эффективным способом получить их? (За исключением очевидной канонической реализации, а также нет таких вещей, которые связаны с сортировкой всего списка, потому что это было бы неэффективно по сравнению с каноническим решением.)
>>> import heapq, random
>>> heapq.nlargest(3, (random.gauss(0, 1) for _ in xrange(100)))
[1.9730767232998481, 1.9326532289091407, 1.7762926716966254]
Функция в стандартной библиотеке, которая делает это, heapq.nlargest
Начните с первых 10 из L, вызовите X. Обратите внимание на минимальное значение X.
Переходим через L [i] для я над остальной частью L.
Если L [i] больше min (X), снимите min (X) из X и вставьте L [i]. Возможно, вам нужно сохранить X как отсортированный связанный список и сделать вставку. Обновить мин (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, которое делает это.
Довольно эффективное решение - это вариант быстрой сортировки, где рекурсия ограничена правой частью стержня, пока позиция точки опоры не будет больше, чем количество требуемых элементов (с несколькими дополнительными условиями, чтобы, конечно, иметь дело с пограничными случаями).
Стандартная библиотека имеет heapq.nlargest, как указано другими здесь.