Каков самый эффективный, элегантный и питонический способ решения этой проблемы?
Учитывая список (или набор или что-то еще) из n элементов, мы хотим получить k самых больших. (Можно предположить k<n/2 без потери общности, я думаю)
Например, если список был:
l = [9,1,6,4,2,8,3,7,5]
n = 9, и пусть k = 3.
Какой самый эффективный алгоритм для извлечения 3 самых больших?
В этом случае мы должны получить [9,8,7] в определенном порядке.
Спасибо! Manuel
Использовать nlargest из модуля heapq
from heapq import nlargest
lst = [9,1,6,4,2,8,3,7,5]
nlargest(3, lst) # Gives [9,8,7]
Вы также можете дать ключ к самому большому, если вы хотите изменить свои критерии:
from heapq import nlargest
tags = [ ("python", 30), ("ruby", 25), ("c++", 50), ("lisp", 20) ]
nlargest(2, tags, key=lambda e:e[1]) # Gives [ ("c++", 50), ("python", 30) ]
l = [9,1,6,4,2,8,3,7,5]
sorted(l)[-k:]
Простым способом O (n log n) является сортировка списка, затем получение последних k элементов.
Правильный способ - использовать алгоритм выбора который работает в O (n + k log k) времени.
Кроме того, heapq.nlargest принимает время O (n log k), которое может быть или не быть достаточно хорошим.
(Если k = O (n), то все три алгоритма имеют одинаковую сложность (т.е. не утруждают себя). Если k = O (log n), то алгоритм выбора, описанный в Википедии, равен O (n) и heapq.nlargest - O (n log log n), но двойной логарифм "достаточно постоянный" для большинства практических n, что это не имеет значения.)
Вы можете использовать модуль heapq.
>>> from heapq import heapify, nlargest
>>> l = [9,1,6,4,2,8,3,7,5]
>>> heapify(l)
>>> nlargest(3, l)
[9, 8, 7]
>>>
sorted(l, reverse=True)[:k]