能否使用argsort进行降序排列？

Question

请考虑下面的代码：

avgDists = np.array([1, 8, 6, 9, 4])
ids = avgDists.argsort()[:n]

这给了我前n个最小元素的索引。是否可以使用相同的argsort以降序方式获取前n个最高元素的索引？

- shn

---

这不就是简单的 ids = np.array(avgDists).argsort()[-n:] 吗？ - Jaime

@Jaime：不，那行不通。"正确答案"是[3, 1, 2]。你的代码会产生 [2, 1, 3]（以n等于3为例）。 - dawg

@drewk 那就把它改成 ids = np.array(avgDists).argsort()[-n:][::-1]。关键是要避免复制整个列表，这是在列表前面加上 - 时会发生的事情。对于 OP 的小例子来说不重要，但对于更大的情况可能会有影响。 - Jaime

@Jaime：你是正确的。请看我的更新答案。然而，语法与您在切片结尾上的评论正好相反：np.array(avgDists).argsort()[::-1][:n] 将做到这一点。此外，如果你要使用numpy，请留在numpy内部。首先将列表转换为数组：avgDist=np.array(avgDists)，然后变成 avgDist.argsort()[::-1][:n]。 - dawg

Answer 1

如果你对一个数组取反，最小的元素将变为最大的元素，反之亦然。因此，n个最高元素的索引是：

(-avgDists).argsort()[:n]

正如在评论中提到的那样，另一种思考这个问题的方式是观察到大元素在argsort中出现在最后。因此，您可以从argsort的末尾开始读取来找到前n个最大的元素：

avgDists.argsort()[::-1][:n]

两种方法的时间复杂度均为O(n log n)，因为argsort调用是这里的主导项。但第二种方法有一个很好的优点：它用O(1)的切片替换了对数组的O(n)取反。如果你在循环内部使用小数组，那么避免这种否定可能会带来一些性能提升；如果你在处理大型数组，则可以节省内存使用，因为否定会创建整个数组的副本。

请注意，这些方法并不总是给出等效的结果：如果请求将稳定排序实现传递给argsort，例如通过传递关键字参数kind='mergesort'，那么第一种策略将保持排序稳定性，但第二种策略将打破稳定性（即相等项目的位置将被颠倒）。

示例时间：

使用100个浮点数的小数组和长度为30的尾部，视图方法约快15%。

>>> avgDists = np.random.rand(100)
>>> n = 30
>>> timeit (-avgDists).argsort()[:n]
1.93 µs ± 6.68 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
>>> timeit avgDists.argsort()[::-1][:n]
1.64 µs ± 3.39 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
>>> timeit avgDists.argsort()[-n:][::-1]
1.64 µs ± 3.66 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

对于更大的数组，argsort是主导的，时间差异不显著。

>>> avgDists = np.random.rand(1000)
>>> n = 300
>>> timeit (-avgDists).argsort()[:n]
21.9 µs ± 51.2 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
>>> timeit avgDists.argsort()[::-1][:n]
21.7 µs ± 33.3 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
>>> timeit avgDists.argsort()[-n:][::-1]
21.9 µs ± 37.1 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)

请注意下面来自nedim的评论是不正确的。在倒序之前或之后截断对效率没有影响，因为这两个操作都只是以不同的方式跨越数组的视图，而不是实际复制数据。

- wim

---

在反转之前切片会更加高效，即np.array(avgDists).argsort()[:-n][::-1]。 - nedim

如果原始数组包含 NaN，则这些答案并不相等。在这种情况下，第一个解决方案似乎会给出更自然的结果，其中 NaN 在末尾而不是开头。 - feilchenfeldt

当需要进行稳定排序时，这些方法有何区别？切片策略是否会颠倒相等的项？ - Eric

@nedim的评论应该是[-n：]而不是[:-n]。 - Girardi

@nedim 评论是误导性/不正确的，我认为。对于列表（切片是副本），可能会有类似的说法，但证据并不支持numpy数组的这种情况（切片是视图）。 - wim

Answer 2

就像Python一样，[::-1] 反转了由 argsort() 返回的数组，[:n] 给出了最后的 n 个元素：

>>> avgDists=np.array([1, 8, 6, 9, 4])
>>> n=3
>>> ids = avgDists.argsort()[::-1][:n]
>>> ids
array([3, 1, 2])

这种方法的优点是，ids 是 视图 的 avgDists:

>>> ids.flags
  C_CONTIGUOUS : False
  F_CONTIGUOUS : False
  OWNDATA : False
  WRITEABLE : True
  ALIGNED : True
  UPDATEIFCOPY : False

（当“OWNDATA”为False时，表示这是一个视图而非副本）

另一种方法是像下面这样：

(-avgDists).argsort()[:n]

问题在于这种方法是创建数组中每个元素的负数：

>>> (-avgDists)
array([-1, -8, -6, -9, -4])

并创建一个副本来执行此操作：

>>> (-avgDists_n).flags['OWNDATA']
True

所以，如果你用这个非常小的数据集来计时：

>>> import timeit
>>> timeit.timeit('(-avgDists).argsort()[:3]', setup="from __main__ import avgDists")
4.2879798610229045
>>> timeit.timeit('avgDists.argsort()[::-1][:3]', setup="from __main__ import avgDists")
2.8372560259886086

view方法速度更快（且使用的内存只有原对象的一半...）

- dawg

---

这个答案不错，但我感觉你的措辞误导了真实的性能特征：“即使使用非常小的数据集，视图方法速度明显更快”。实际上，取反是O(n)，argsort是O(n log n)。这意味着随着数据集变大，计时差异将会减小 - O(n log n)项会占主导地位，但您的建议是O(n)部分的优化。因此，复杂度保持不变，只有对于特定的小数据集我们才会看到任何显著的差异。 - wim

渐进等价复杂度仍可能意味着一个算法比另一个算法快两倍。放弃这样的区别可能会产生后果。例如，即使时间差异（作为百分比）趋近于0，我愿意打赌，带否定的算法仍然使用了两倍的内存。 - bug

@bug 可以，但在这种情况下不会。我在我的答案中添加了一些时间。这些数字表明，对于更大的数组，这些方法具有类似的时间，这支持argsort是占主导地位的假设。对于否定，我猜你关于内存使用的想法是正确的，但如果用户关心nan的位置和/或需要稳定的排序，他们仍然可能更喜欢它。 - wim

这种方法的优势在于ids是avgDists的一个视图：这是不正确的。ids是argsort返回的未命名索引数组的一个视图。 - undefined

Answer 3

如果你只需要最小/最大的n个元素的索引，而不是使用np.argsort，你可以使用np.argpartition。

这不需要对整个数组进行排序，而只需对所需部分进行排序，但请注意，“分区内的顺序”是未定义的，因此它会给出正确的索引，但它们可能没有正确排序：

>>> avgDists = [1, 8, 6, 9, 4]
>>> np.array(avgDists).argpartition(2)[:2]  # indices of lowest 2 items
array([0, 4], dtype=int64)

>>> np.array(avgDists).argpartition(-2)[-2:]  # indices of highest 2 items
array([1, 3], dtype=int64)

- MSeifert

---

如果你同时使用argsort和argpartition，操作必须在argpartition操作上执行。 - demongolem

虽然这不会按降序返回索引。返回应该是[4, 0]，[3,1]。 - Andrei R.

Answer 4

正如 @Kanmani 暗示的那样，一种更易于解释的实现方式可能使用 numpy.flip，如下所示：

import numpy as np

avgDists = np.array([1, 8, 6, 9, 4])
ids = np.flip(np.argsort(avgDists))
print(ids)

通过使用访问者模式而不是成员函数，更容易读取操作顺序。

- Adam Erickson

Answer 5

您可以使用翻转命令numpy.flipud()或numpy.fliplr()来在使用argsort命令进行排序后按降序获取索引。这是我通常做的方法。

- Kanmani

---

这比切片慢得多。 - endolith

Answer 6

您可以创建一个数组的副本，然后将每个元素乘以-1。
这样，之前最大的元素就变成了最小的元素。
在副本中，n个最小元素的索引是原始数组中n个最大元素的索引。

- MentholBonbon

---

这很容易通过否定数组来完成，就像其他答案中所述：-array。 - onofricamila

Answer 7

一种优雅的方法如下所示 -

ids = np.flip(np.argsort(avgDists))

这将为您提供按降序排序的元素索引。现在，您可以使用常规切片...

top_n = ids[:n]

- NiteshK

Answer 8

通过以下示例：

avgDists = np.array([1, 8, 6, 9, 4])

获取 n 个最大值的索引：

ids = np.argpartition(avgDists, -n)[-n:]

将它们按降序排序：

ids = ids[np.argsort(avgDists[ids])[::-1]]

获取结果（n=4）：

>>> avgDists[ids]
array([9, 8, 6, 4])

- Alexey Antonenko

Answer 9

考虑相等元素的顺序

如果您运行排序程序并且存在2个相等的元素，则通常不会更改它们的顺序。然而，翻转/[::-1]方法会改变相等元素的顺序。

>>> arr = np.array([3, 5, 4, 7, 3])
>>> 
>>> np.argsort(arr)[::-1]
array([3, 1, 2, 4, 0])  # equal elements reorderd
>>> np.argsort(-arr)
array([3, 1, 2, 0, 4])  # equal elements not reorderd (compatible to other sorting)

为了兼容性考虑，我更喜欢使用负数数组的argsort方法。特别是在arr表示更复杂元素的某些数字表示时，这一点尤为重要。

示例：

obj = ['street', 'house', 'bridge', 'station', 'rails']
arr = np.array([3, 5, 4, 7, 3])  # cost of obj in coins

免责声明：更常见的方法是使用sorted(list_of_tuples_obj_cost, key=lambda x: x[1])来解决上述示例。

- Markus Dutschke

Answer 10

另一种方法是在argsort的参数中仅使用“-”，例如：“df[np.argsort(-df[:, 0])]”，其中df是数据框，您想按第一列排序（由列号'0'表示）。根据需要更改列名。当然，该列必须是数字列。

- Biswajit Ghoshal