高效地查找Python数组/列表中N个最大元素的索引 [英] Finding the Index of N biggest elements in Python Array / List Efficiently

问题描述

如果这是一个重复的问题，我很抱歉，我一直在寻找此信息，但仍然找不到.

I'm sorry in advance if this is a duplicated question, I looked for this information but still couldn't find it.

是否可以通过高效使用N个最大元素的索引以降序排列numpy数组(或python列表)?

Is it possible to arrange a numpy array (or python list) by using the indexes of the N biggest elements in decreasing order very efficiently?

例如，数组:

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

以递减的顺序给出最大元素的索引(考虑N = 6，包括所有元素):

The indexes of the biggest elements in decreasing order would give (considering N = 6, all the elements are included):

8-> 3

5-> 4

4-> 0

2-> 5

1-> 1

0-> 2

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

我知道如何使用某种愚蠢的方法(例如对数组进行排序并为索引搜索N个数字中的每一个)，但是我想知道是否存在任何有效的库，例如瓶颈或heapq或pythonic使其变得非常快的方法.我必须将其应用到每个包含30万个元素的多个数组中，所以这就是性能成为问题的原因.

I know how to make it using a somewhat silly approach (like sorting the array and searching for each of the N numbers for their indexes), but I was wondering if is there any efficient library like bottleneck or heapq or maybe a pythonic approach to make this very fast. I have to apply it in several arrays with 300k elements each so that's why performance is an issue.

提前谢谢！

更新

我阅读了答案，并决定使用300k随机整数对它们进行计时，结果如下:

I read the answers and decided to timeit them using a 300k of random integers, here are the results:

解决方案1: sorted(range(len(a)), key=lambda i:a[i]) 时间: 230毫秒

解决方案2: heapq.nlargest(len(a), zip(a, itertools.count())) 时间: 396毫秒

解决方案3: heapq.nlargest(len(a), enumerate(a), key=operator.itemgetter(1)) 时间: 864毫秒

解决方案4: def f(a,N): return np.argsort(a)[::-1][:N] (N = len(a)) 时间:104毫秒

非常感谢您的快速回答！！

Thanks a lot for the fast and very good answers!

推荐答案

您是否看过内置的numpy argsort方法?:

Have you looked at the built-in numpy argsort method?:

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

使用该方法，我可以在大约29毫秒的时间内对具有300,000个随机浮点数的数组进行排序.

I can sort an array with 300,000 random floats in about 29 ms on my machine using that method.

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

这篇关于高效地查找Python数组/列表中N个最大元素的索引的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！