как эффективно получить k большие элементы списка в Python
Каков самый эффективный, изящный и pythonic способ решить эту проблему?
Учитывая список (или набор или безотносительно) n элементов, мы хотим получить k самые большие. (Можно принять k<n/2 без потери общности я предполагаю), Например, если список был:
l = [9,1,6,4,2,8,3,7,5]
n = 9, и скажем, k = 3. Каков самый эффективный алгоритм для получения 3 самых больших? В этом случае мы должны добраться [9,8,7], без определенного порядка.
Спасибо! Manuel
5 ответов
Использовать наибольшее значение из модуля heapq
from heapq import nlargest
lst = [9,1,6,4,2,8,3,7,5]
nlargest(3, lst) # Gives [9,8,7]
Вы можете также укажите ключ к nlargest, если вы хотите изменить критерии:
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) ]
Простой способ за O (n log n) - отсортировать список и получить последние k элементов.
Правильный способ - использовать алгоритм выбора , который выполняется за время O (n + k log k).
Кроме того, heapq.nlargest занимает время O (n log k) , что может быть достаточно или недостаточно.
(Если k = O (n), тогда все 3 алгоритма имеют одинаковую сложность (т.е. не беспокойтесь). Если 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]
>>>