在Python中计算列表的排名向量的有效方法，处理关系

Question

我正在寻找一种有效的方法来计算Python中列表的排名向量，类似于R的

rank

函数。在元素之间没有联系的简单列表中，当且仅当 

l 是排序列表中的第 x

 元素时，列表 

l[i] 的排名向量的元素 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 也可以工作的工具。

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

 函数的工作方式。

这是

scipy

 的 

rankdata 函数的纯 Python 等效项：

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]

Answer 2

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

sorted(l)

 将给出排序后的版本

index(x)

 将给出排序数组中的 

index

例如：

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

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]

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__)]

您自己的测试必须证明其效率。

Answer 5

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

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

Answer 6

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

[index for element, index in sorted(zip(sequence, range(len(sequence))))] 您构建包含元素和运行索引的元组。然后对整个事物进行排序，元组按其第一个元素排序，在关系期间按其第二个元素排序。这样一来，人们就拥有了这些元组的排序列表，然后只需要从中挑选出索引即可。此外，这还消除了之后在序列中查找元素的需要，这可能使其成为 O(N²) 操作，而这是 O(N log(N))。

Answer 7

有一个非常好的模块，名为 Ranking

http://pythonhosted.org/ranking/，具有易于遵循的说明页面。要下载，只需使用easy_install ranking

Answer 8

所以..现在是 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 个索引数组，并且不要求值是可哈希的（只需要成对比较）。

AFAICT，这比迄今为止建议的其他方法更好：

@unutbu 的方法本质上是相似的，但是（我认为）对于 OP 的要求来说太复杂了；
所有使用
• .index()

  的建议都很糟糕，运行时复杂度为N^2；

@Yuvraj Singh 在使用字典的
• .index()

   搜索的基础上略有改进，但是在每次迭代时进行搜索和插入操作，这在时间（NlogN）和空间上仍然非常低效，并且还要求值是可散列的。 

Answer 9

查找数组排名的最Python风格：

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)

Answer 10

这些代码给了我很多启发，尤其是unutbu的代码。 不过我的需求比较简单，所以我稍微改变了代码。

希望可以帮助到有同样需求的小伙伴。

这里是记录玩家分数和排名的类。

class Player():
    def __init__(self, s, r):
        self.score = s
        self.rank = r

一些数据。

l = [Player(90,0),Player(95,0),Player(85,0), Player(90,0),Player(95,0)] 计算代码如下：

l.sort(key=lambda x:x.score, reverse=True)    
l[0].rank = 1
dupcount = 0
prev = l[0]
for e in l[1:]:
    if e.score == prev.score:
        e.rank = prev.rank
        dupcount += 1
    else:
        e.rank = prev.rank + dupcount + 1
        dupcount = 0
        prev = e

Answer 11

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.2us

Answer 12

这适用于斯皮尔曼相关系数。

def get_rank(X, n):
    x_rank = dict((x, i+1) for i, x in enumerate(sorted(set(X))))
    return [x_rank[x] for x in X]

Answer 13

使用以下方法可以在 O(n log n) 时间和 O(n) 额外空间内实现排名函数。

import bisect

def rank_list(lst: list[int]) -> list[int]:
    sorted_vals = sorted(set(lst))
    return [bisect.bisect_left(sorted_vals, val) for val in lst]

我在这里使用

bisect库，但对于纯粹的独立代码来说，它足以在排序数组上实现二进制搜索过程，并使用唯一值来查询现有（在此数组中）值。