高效查找Python数组/列表中N个最大元素的索引

Question

如果这是一个重复的问题，我很抱歉，我找了这个信息，但仍然找不到。

通过使用N个最大元素的索引以非常高效的降序排列numpy数组（或python列表）是可能的吗？

例如，数组：

a = array([4, 1, 0, 8, 5, 2])

按降序排列的最大元素的索引将给出（考虑N=6，所有元素都包括在内）：

8-->；3个

5--gt；4个

4-->；0

2--gt；5个

1-->；1

0-->；2

result = [3, 4, 0, 5, 1, 2]

我知道如何使用一种有点愚蠢的方法（比如对数组进行排序并搜索N个数字中的每一个作为它们的索引），但是我想知道是否有像瓶颈或heapq这样的有效库，或者也许有一种pythonic方法可以使这个过程非常快速。我必须把它应用到几个数组中，每个数组有300k个元素，所以性能是个问题。

提前谢谢！

更新

我读了答案，决定用300k随机整数计时，结果如下：

溶液1：sorted(range(len(a)), key=lambda i:a[i])时间：230ms

溶液2：heapq.nlargest(len(a), zip(a, itertools.count()))时间：396ms

溶液3：heapq.nlargest(len(a), enumerate(a), key=operator.itemgetter(1))时间：864 ms

溶液4：def f(a,N): return np.argsort(a)[::-1][:N] (N = len(a))时间：104 ms

非常感谢你的快速和非常好的回答！

Answer 1

你看过内置的numpyargsort方法吗？以下内容：

http://docs.scipy.org/doc/numpy/reference/generated/numpy.argsort.html

在我的机器上，我可以用这种方法在29毫秒内对一个有300000个随机浮点数的数组进行排序。

def f(a,N):
    return np.argsort(a)[::-1][:N]

Answer 2

您可以使用heapq轻松完成此操作：

>>> heapq.nlargest(3, zip(a, itertools.count()))
[(8, 3), (5, 4), (4, 5)]

元组按第一个值排序，然后按第二个值排序。。。这意味着我们可以简单地构造一个(value, index)元组并排序，给我们值的索引（这些值也被给出，但是我们可以很容易地将它们扔掉）。

我使用zip()和itertools.count()作为枚举给我们错误的顺序，因此它们将按索引而不是按值排序。或者，你也可以做((value, index) for index, value in enumerate(a))，但我觉得不太清楚。

另一种选择是给一个键，执行heapq.nlargest(3, enumerate(a), key=operator.itemgetter(1))。

Answer 3

L = [4, 1, 0, 8, 5, 2]
sorted(range(len(L)), key=lambda i:L[i])