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

问题描述 投票:0回答:13
我正在寻找一种有效的方法来计算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 也可以工作的工具。

python list sorting ranking
13个回答
87
投票
使用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]
    

27
投票
[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]
    

7
投票
这是我编写的用于计算排名的函数之一。

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]
    

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

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


3
投票
这是 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
    

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

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

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


2
投票
有一个非常好的模块,名为 Ranking

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


    


1
投票
所以..现在是 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)和空间上仍然非常低效,并且还要求值是可散列的。 

1
投票
查找数组排名的最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)
    

0
投票
这些代码给了我很多启发,尤其是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
    

0
投票
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


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

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]
    

0
投票
使用以下方法可以在 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库,但对于纯粹的独立代码来说,它足以在排序数组上实现二进制搜索过程,并使用唯一值来查询现有(在此数组中)值。

© www.soinside.com 2019 - 2024. All rights reserved.