как эффективно получить k больших элементов списка в Python

Question

Какой самый эффективный, изящный и питонный способ решения этой проблемы?

Учитывая список (или набор или любой другой) из n элементов, мы хотим получить k самых больших. (Вы можете предположить k<n/2 без потери общности, я думаю) Например, если список был:

l = [9,1,6,4,2,8,3,7,5]

n = 9, и скажем, k = 3. Какой самый эффективный алгоритм поиска 3 самых больших? В этом случае мы должны получить [9,8,7], без определенного порядка.

Спасибо! Manuel

Answer 1

Использовать самое старое из модуля 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) ]

Answer 2

Простой, 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 , что это не имеет значения.)

Answer 3

l = [9,1,6,4,2,8,3,7,5]

sorted(l)[-k:]

Answer 4

sorted(l, reverse=True)[:k]

Answer 5

Вы можете использовать модуль heapq.

>>> from heapq import heapify, nlargest
>>> l = [9,1,6,4,2,8,3,7,5]
>>> heapify(l)
>>> nlargest(3, l)
[9, 8, 7]
>>>