我有一个数字列表:
myList = [1, 2, 3, 100, 5]
现在如果我对这个列表进行排序得到[1,2,3,5,100]。 我想要的是元素的下标 原始列表的排序顺序,即[0,1,2,4,3] ——ala MATLAB的排序函数,返回两者 值和索引。
我有一个数字列表:
myList = [1, 2, 3, 100, 5]
现在如果我对这个列表进行排序得到[1,2,3,5,100]。 我想要的是元素的下标 原始列表的排序顺序,即[0,1,2,4,3] ——ala MATLAB的排序函数,返回两者 值和索引。
当前回答
myList = [1, 2, 3, 100, 5]
sorted(range(len(myList)),key=myList.__getitem__)
[0, 1, 2, 4, 3]
其他回答
如果您不想使用numpy,
sorted(range(len(seq)), key=seq.__getitem__)
是最快的,如这里所示。
RustyRob答案的一个变体(它已经是最高性能的纯Python解决方案),当你排序集合时可能会更好:
不是一个序列(例如,它是一个集合,并且有一个合理的理由希望索引对应于迭代器必须前进多远才能到达项目),或者 是一个没有O(1)索引的序列(在Python包含的电池中,collections.deque是一个显著的例子)
情况#1不太可能有用,但情况#2更可能有意义。无论哪种情况,你都有两个选择:
转换为列表/元组并使用转换后的版本,或 使用基于迭代顺序分配键的技巧
这个答案为第2点提供了解决方案。请注意,它不能保证按照语言标准工作;该语言表示每个键将被计算一次,但不表示它们的计算顺序。到目前为止,在CPython(引用解释器)的每个版本中,它都是按照从头到尾的顺序预先计算的,所以这是可行的,但请注意,这并不能保证。在任何情况下,代码是:
sizediterable = ...
sorted_indices = sorted(range(len(sizediterable)), key=lambda _, it=iter(sizediterable): next(it))
All that does is provide a key function that ignores the value it's given (an index) and instead provides the next item from an iterator preconstructed from the original container (cached as a defaulted argument to allow it to function as a one-liner). As a result, for something like a large collections.deque, where using its .__getitem__ involves O(n) work (and therefore computing all the keys would involve O(n²) work), sequential iteration remains O(1), so generating the keys remains just O(n).
如果您需要使用内置类型来保证语言标准的工作,Roman的解决方案将具有与此解决方案相同的算法效率(因为它们都不依赖于索引原始容器的算法效率)。
需要明确的是,对于collections.deque的建议用例,deque必须非常大;Deques有一个相当大的常量除数用于索引,所以只有真正巨大的才会有问题。当然,出于同样的原因,如果输入比较小/便宜,排序的成本是非常小的,所以如果输入足够大,有效的排序很重要,那么它们也足够大,有效的索引也很重要。
使用enumerate的答案很好,但我个人不喜欢用lambda来按值排序。下面的操作只是倒转索引和值,并对其排序。首先是按值排序,然后是按下标排序。
sorted((e,i) for i,e in enumerate(myList))
本质上你需要做一个argsort,你需要什么实现取决于你是想使用外部库(例如NumPy),还是想保持纯python而不依赖。
你需要问自己的问题是:你想要
对数组/列表进行排序的索引 元素在排序后的数组/列表中的下标
不幸的是,问题中的例子并没有说清楚我们想要什么,因为两者都会给出相同的结果:
>>> arr = np.array([1, 2, 3, 100, 5])
>>> np.argsort(np.argsort(arr))
array([0, 1, 2, 4, 3], dtype=int64)
>>> np.argsort(arr)
array([0, 1, 2, 4, 3], dtype=int64)
选择argsort实现
如果你有NumPy,你可以简单地使用NumPy函数。Argsort或numpy.ndarray.argsort方法。
在其他一些答案中已经提到了不使用NumPy的实现,因此我将根据这里的基准答案简要介绍最快的解决方案
def argsort(l):
return sorted(range(len(l)), key=l.__getitem__)
获取对数组/列表进行排序的下标
要获得对数组/列表排序的下标,您可以简单地调用数组或列表上的argsort。我在这里使用的是NumPy版本,但Python实现应该会给出相同的结果
>>> arr = np.array([3, 1, 2, 4])
>>> np.argsort(arr)
array([1, 2, 0, 3], dtype=int64)
结果包含获取排序数组所需的下标。
因为排序后的数组是[1,2,3,4],所以argsorted数组包含了原始数组中这些元素的下标。
最小的值是1,它在原始索引1处,所以结果的第一个元素是1。 2在原式的下标2处所以结果的第二个元素是2。 3在原矩阵的下标0处,所以结果的第三个元素是0。 最大的值是4,它在原始索引的3处,所以结果的最后一个元素是3。
获取元素在排序后的数组/列表中的下标
在这种情况下,你需要应用argsort两次:
>>> arr = np.array([3, 1, 2, 4])
>>> np.argsort(np.argsort(arr))
array([2, 0, 1, 3], dtype=int64)
在这种情况下:
the first element of the original is 3, which is the third largest value so it would have index 2 in the sorted array/list so the first element is 2. the second element of the original is 1, which is the smallest value so it would have index 0 in the sorted array/list so the second element is 0. the third element of the original is 2, which is the second-smallest value so it would have index 1 in the sorted array/list so the third element is 1. the fourth element of the original is 4 which is the largest value so it would have index 3 in the sorted array/list so the last element is 3.
像下面这样:
>>> myList = [1, 2, 3, 100, 5]
>>> [i[0] for i in sorted(enumerate(myList), key=lambda x:x[1])]
[0, 1, 2, 4, 3]
enumerate(myList)给你一个包含(index, value)元组的列表:
[(0, 1), (1, 2), (2, 3), (3, 100), (4, 5)]
通过将列表传递给sorted并指定一个函数来提取排序键(每个元组的第二个元素;这就是的意义。最后,使用[i[0] for i in…列表理解。