NumPy

Question

NumPy 的 np.argsort is able to do stable sorting 通过传递 kind = 'stable' 参数。

此外 np.argsort 不支持反向（降序）顺序。

如果需要不稳定的行为，那么降序可以很容易地通过 desc_ix = np.argsort(a)[::-1] 建模。

我正在寻找 efficient/easy 任何可比较 dtype 的降序稳定排序 NumPy 数组 a 的解决方案。请参阅我在最后一段中对“稳定性”的理解。

对于 dtype 是任何数值的情况，可以通过对数组的否定版本进行排序来轻松完成稳定的降序 arg 排序：

print(np.argsort(-np.array([1, 2, 2, 3, 3, 3]), kind = 'stable'))
# prints: array([3, 4, 5, 1, 2, 0], dtype=int64)

但我需要支持任何可比较的 dtype，包括 np.str_ 和 np.object_。

只是为了澄清 - 也许对于降序 stable 的经典含义意味着从右到左枚举相等的元素。如果是这样，那么在我的问题中 stable + descending 的含义有所不同 - 应该从左到右枚举相等范围的元素，而彼此之间的相等范围按降序排列。 IE。应该像上面最后一个代码一样实现相同的行为。 IE。我想要稳定性，就像 Python 在下一个代码中实现的一样：

print([e[0] for e in sorted(enumerate([1,2,2,3,3,3]), key = lambda e: e[1], reverse = True)])
# prints: [3, 4, 5, 1, 2, 0]

Answer 1

一个最简单的解决方案是通过将任何 dtype 的已排序唯一元素映射到升序整数，然后将负整数稳定升序 arg-sorting。

Try it online!

import numpy as np
a = np.array(['a', 'b', 'b', 'c', 'c', 'c'])
u = np.unique(a)
i = np.searchsorted(u, a)
desc_ix = np.argsort(-i, kind = 'stable')
print(desc_ix)
# prints [3 4 5 1 2 0]

Answer 2

我们可以利用np.unique(..., return_inverse=True)-

u,tags = np.unique(a, return_inverse=True)
out = np.argsort(-tags, kind='stable')

Answer 3

我认为这个公式应该有效：

import numpy as np
a = np.array([1, 2, 2, 3, 3, 3])
s = len(a) - 1 - np.argsort(a[::-1], kind='stable')[::-1]
print(s)
# [3 4 5 1 2 0]

Answer 4

类似于@jdehesa 的干净解决方案，此解决方案允许指定一个轴。

indices = np.flip(
    np.argsort(np.flip(x, axis=axis), axis=axis, kind="stable"), axis=axis
)
normalised_axis = axis if axis >= 0 else x.ndim + axis
max_i = x.shape[normalised_axis] - 1
indices = max_i - indices

NumPy - 任何 dtype 的降序稳定 arg-sort 数组

NumPy - descending stable arg-sort of arrays of any dtype

python

arrays

sorting

stable-sort