在Python中计算列表的秩向量的高效方法

Question

我希望能够在Python中高效地计算列表的排名向量，类似于R语言的rank函数。在没有元素之间存在平局的简单列表中，列表l的排名向量的第i个元素应为x，当且仅当l[i]是排序后的列表中第x个元素。到目前为止，这很简单，以下代码片段可以完成任务：

def rank_simple(vector):
    return sorted(range(len(vector)), key=vector.__getitem__)

然而，如果原始列表存在并列的元素（即多个具有相同值的元素），情况会变得复杂。在这种情况下，所有具有相同值的元素应该具有相同的排名，这是使用上述朴素方法获得的排名的平均值。例如，如果我有[1, 2, 3, 3, 3, 4, 5]，那么朴素排名会给我[0, 1, 2, 3, 4, 5, 6]，但我想要的是[0, 1, 3, 3, 3, 5, 6]。哪种方式在Python中实现最有效？

---

注：我不知道NumPy是否已经有一种方法可以实现这一点，如果有，请告诉我，但无论如何，我都希望得到一个纯Python的解决方案，因为我正在开发一个不需要NumPy也能工作的工具。

- Tamás

---

你有检查过 numpy.argsort(vector) 吗？ - yosemite_k

顺便说一句，我认为这段代码甚至无法计算序数排名。要正确计算序数排名，请阅读此链接：https://codereview.stackexchange.com/questions/65031/creating-a-list-containing-the-rank-of-the-elements-in-the-original-list - H. Jang

几乎是 Rank items in an array using Python/NumPy, without sorting array twice - Stack Overflow 的副本，只不过另一个问题明确要求使用numpy解决方案。 - user202729

抱歉打扰了十一年，但是...你的rank_simple()实际上是R语言中order()函数的等价物，而不是rank()函数吗？例如，请参见https://dev59.com/02ct5IYBdhLWcg3wLqfw。 - djvg

Answer 1

使用scipy，你要查找的函数是scipy.stats.rankdata：

In [13]: import scipy.stats as ss
In [19]: ss.rankdata([3, 1, 4, 15, 92])
Out[19]: array([ 2.,  1.,  3.,  4.,  5.])

In [20]: ss.rankdata([1, 2, 3, 3, 3, 4, 5])
Out[20]: array([ 1.,  2.,  4.,  4.,  4.,  6.,  7.])

排名从1开始，而不是0（如你的例子所示），但这也是 R 的 rank 函数的工作方式。

这里是一个纯Python等价于 scipy 的 rankdata 函数：

def rank_simple(vector):
    return sorted(range(len(vector)), key=vector.__getitem__)

def rankdata(a):
    n = len(a)
    ivec=rank_simple(a)
    svec=[a[rank] for rank in ivec]
    sumranks = 0
    dupcount = 0
    newarray = [0]*n
    for i in xrange(n):
        sumranks += i
        dupcount += 1
        if i==n-1 or svec[i] != svec[i+1]:
            averank = sumranks / float(dupcount) + 1
            for j in xrange(i-dupcount+1,i+1):
                newarray[ivec[j]] = averank
            sumranks = 0
            dupcount = 0
    return newarray

print(rankdata([3, 1, 4, 15, 92]))
# [2.0, 1.0, 3.0, 4.0, 5.0]
print(rankdata([1, 2, 3, 3, 3, 4, 5]))
# [1.0, 2.0, 4.0, 4.0, 4.0, 6.0, 7.0]

- unutbu

---

从xrange中删除x，改为使用range，这样就可以正常工作了。不确定xrange是否是一个打字错误还是我漏掉了什么，但还是谢谢！ - brilliantairic

Answer 2

[sorted(l).index(x) for x in l]

sorted(l) 将给出排序后的版本，index(x) 将给出在已排序数组中的索引。

例如：

l = [-1, 3, 2, 0,0]
>>> [sorted(l).index(x) for x in l]
[0, 4, 3, 1, 1]

- Jialiang Gu

---

不错的一行代码！考虑效率，这会为l中的每个x重复排序吗？顺便说一句，它返回并列排名的最低索引，而不是平均值，这是另一个有用的选项，但不完全符合OP的要求。 - FNia

Answer 3

这是我编写的一个计算排名的函数之一。

def calculate_rank(vector):
  a={}
  rank=1
  for num in sorted(vector):
    if num not in a:
      a[num]=rank
      rank=rank+1
  return[a[i] for i in vector]

输入：

calculate_rank([1,3,4,8,7,5,4,6])

输出：

[1, 2, 3, 7, 6, 4, 3, 5]

- Yuvraj Singh

Answer 4

这并不会给出您指定的精确结果，但也许它仍然有用。下面的代码片段给出了每个元素的第一个索引，产生了最终的排名向量[0, 1, 2, 2, 2, 5, 6]

def rank_index(vector):
    return [vector.index(x) for x in sorted(range(n), key=vector.__getitem__)]

您需要自己进行测试来证明其效率。

- stw_dev

---

这假设vector已经排序，但仍是一个非常易懂的实现。+1 - tgray

啊，说得好。Tamás的理解是从一个sorted()列表开始的...我会编辑以包括它。 - stw_dev

不仅假设不成立，而且 index() 方法也是 O(N)，因此根本不高效。 - zinking

Answer 5

这是unutbu代码的一个小变体，包括一个可选的“method”参数，用于绑定排名值的类型。

def rank_simple(vector):
    return sorted(range(len(vector)), key=vector.__getitem__)

def rankdata(a, method='average'):
    n = len(a)
    ivec=rank_simple(a)
    svec=[a[rank] for rank in ivec]
    sumranks = 0
    dupcount = 0
    newarray = [0]*n
    for i in xrange(n):
        sumranks += i
        dupcount += 1
        if i==n-1 or svec[i] != svec[i+1]:
            for j in xrange(i-dupcount+1,i+1):
                if method=='average':
                    averank = sumranks / float(dupcount) + 1
                    newarray[ivec[j]] = averank
                elif method=='max':
                    newarray[ivec[j]] = i+1
                elif method=='min':
                    newarray[ivec[j]] = i+1 -dupcount+1
                else:
                    raise NameError('Unsupported method')

            sumranks = 0
            dupcount = 0


    return newarray

- Sunthar

---

谢谢！scipy.stats.rankdata的最新版本有可选的方法参数，但我卡在了一个只支持平均方法的旧版本上，所以你为我节省了很多时间来编写自己的函数。如果您添加“dense”选项，那么您将覆盖所有内容。 - kslnet

Answer 6

我真的不明白为什么所有现有的解决方案都如此复杂。这可以像这样简单地完成：

[index for element, index in sorted(zip(sequence, range(len(sequence))))]

你需要构建包含元素和运行索引的元组。然后对整个列表进行排序，元组按其第一个元素进行排序，如果存在相等的情况，则按其第二个元素进行排序。这样就可以得到一个已排序的元组列表，只需从中选择索引即可。此外，这还消除了之后在序列中查找元素的需要，这可能使其成为O(N²)操作，而这是O(N log(N))。

- Martin Ueding

---

由于元组排序在第一和第二个元素相等时按第二个元素排序，因此并列的将按升序编号。 - Martin Ueding

这是一个不错的解决方案，用于排名并列项，但 OP 要求“所有具有相同值的元素应具有相同的排名”。 - amonowy

@amonowy：终于我明白为什么其他的解决方案这么复杂了。那么这个答案就不符合问题了。我应该删除它吗？ - Martin Ueding

对我来说，分析它是有益的，我认为值得保留。 - amonowy

Answer 7

有一个非常好用的模块叫做Rankinghttp://pythonhosted.org/ranking/，并且有易于理解的说明页面。要下载，只需使用easy_install ranking即可。

- Kerry Kalweit

Answer 8

找到数组排名的最Pythonic风格：

a = [10.0, 9.8, 8.0, 7.8, 7.7, 7.0, 6.0, 5.0, 4.0, 2.0]
rank = lambda arr: list(map(lambda i: sorted(arr).index(i)+1, arr))
rank(a)

- Rohan Dhanraj

Answer 9

所以...现在是2019年，我不知道为什么没有人建议以下内容：

# Python-only
def rank_list( x, break_ties=False ):
    n = len(x)
    t = list(range(n))
    s = sorted( t, key=x.__getitem__ )

    if not break_ties:
        for k in range(n-1):
            t[k+1] = t[k] + (x[s[k+1]] != x[s[k]])

    r = s.copy()
    for i,k in enumerate(s):
        r[k] = t[i]

    return r

# Using Numpy, see also: np.argsort
def rank_vec( x, break_ties=False ):
    n = len(x)
    t = np.arange(n)
    s = sorted( t, key=x.__getitem__ )

    if not break_ties:
        t[1:] = np.cumsum(x[s[1:]] != x[s[:-1]])

    r = t.copy()
    np.put( r, s, t )
    return r

这种方法在初始排序后具有线性运行时复杂度，仅存储2个索引数组，并且不需要值可哈希（仅需要成对比较）。

据我所知，这比迄今为止提出的其他方法更好：

• @unutbu的方法本质上是相似的，但我认为它对于OP所要求的太过复杂；
• 所有使用.index()的建议都很糟糕，其运行时复杂度为N^2；
• @Yuvraj Singh通过使用字典略微改进了.index()搜索，但由于每次迭代都需要进行搜索和插入操作，因此在时间（NlogN）和空间方面仍然非常低效，而且还需要值可哈希。

- Jonathan H

Answer 10

import numpy as np

def rankVec(arg):
    p = np.unique(arg) #take unique value
    k = (-p).argsort().argsort() #sort based on arguments in ascending order
    dd = defaultdict(int)
    for i in xrange(np.shape(p)[0]):
        dd[p[i]] = k[i]
    return np.array([dd[x] for x in arg])

时间复杂度为46.2微秒

- vamsi21

---

虽然这段代码可能回答了问题，但提供有关它如何以及/或为什么解决问题的附加上下文将提高其长期价值。请参阅此处。 - Jonathan H