Найдите наивысшие n элементов в списке и их местоположениях. Python

Question

Недавно меня попросили написать код, чтобы найти наивысшие n элементов в списке и вернуть как значения, так и местоположения.

Вы можете получить более быстрый (с точки зрения времени выполнения), чем этот?

def highest(L, n): 
    return sorted(enumerate(L), reverse=True, key=lambda x: x[1])[:n] 

if __name__ == '__main__': 

    M = [102, 56, 2355, 3, 25, 78, 19, 25, 1002, -54, 0, 23, -1] 
    r = highest(M,5) 
    print r #[(2, 2355), (8, 1002), (0, 102), (5, 78), (1, 56)] 

Answer 1

Если n мал по сравнению с длиной списка, heapq.nlargest должен быть быстрее, чем сортировка всего списка. Это также более читаемо.

def highest(L, n): 
    return heapq.nlargest(n, enumerate(L), key=operator.itemgetter(1)) 

>>> M = [102, 56, 2355, 3, 25, 78, 19, 25, 1002, -54, 0, 23, -1] 
>>> highest(M,5) 
[(2, 2355), (8, 1002), (0, 102), (5, 78), (1, 56)] 

Это будет работать в O (N + NlogN), где N является длина списка и n является количество элементов для возврата, в отличие от O (NlogN) для сортировки.

Answer 2

Просто добавьте, вы можете использовать kth_smallest в pandas, чтобы найти значение в O (N).

import numpy as np 
import pandas as pd 
a = np.array([102, 56, 2355, 3, 25, 78, 19, 25, 1002, -54, 0, 23, -1.0]) 
pd.algos.kth_smallest(a, len(a)-5) 

код здесь:

https://github.com/pydata/pandas/blob/master/pandas/algos.pyx#L653

Примечание: kth_smallest возвращает только значение, но вы можете сканировать массив, чтобы найти место.