1

最近我被要求编写一些代码来查找列表中最高的 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)]
4

2 回答 2

9

如果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) 进行排序。

于 2013-02-28T13:30:04.467 回答
1

只是一个补充，您可以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仅返回值，但您可以扫描数组以查找位置。

于 2013-02-28T14:05:50.893 回答