22

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

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

例如，数组：

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

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

8 --> 3

5 --> 4

4 --> 0

2 --> 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]) 时间： 230 ms

解决方案2： heapq.nlargest(len(a), zip(a, itertools.count())) 时间： 396 ms

解决方案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

非常感谢您提供快速且非常好的答案！

4

4 回答 4

21

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

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

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

def f(a,N):
    return np.argsort(a)[::-1][:N]
于 2012-10-08T18:58:31.097 回答
11 
L = [4, 1, 0, 8, 5, 2]
sorted(range(len(L)), key=lambda i:L[i])
于 2012-10-08T18:52:38.200 回答
6

你可以heapq很容易地做到这一点：

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

元组是通过对第一个值排序，然后是第二个，等等(value, index)...这些离开）。

我正在使用zip()and itertools.count()as enumerate 给了我们错误的顺序，所以它们将按索引排序，而不是按值排序。或者，您也可以这样做((value, index) for index, value in enumerate(a))，但我觉得不太清楚。

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

于 2012-10-08T18:52:58.320 回答
1

使用 heapq 的另一种方法

heapq.nlargest(n, range(len(a)), key=a.__getitem__)

n<<len(a)正如其他地方所评论的那样，除非 a 非常大并且因为排序是 Python 中相对较快的操作，否则它不会胜过排序。然而最终缓慢的 O(n) 总是会击败 O(n*log(n))

于 2012-10-09T05:36:35.273 回答