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 中执行此操作最有效的方法?
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]
[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]
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]
[0, 1, 2, 2, 2, 5, 6]
def rank_index(vector):
return [vector.index(x) for x in sorted(range(n), key=vector.__getitem__)]
您自己的测试必须证明其效率。
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
[index for element, index in sorted(zip(sequence, range(len(sequence))))]
您构建包含元素和运行索引的元组。然后对整个事物进行排序,元组按其第一个元素排序,在关系期间按其第二个元素排序。这样一来,人们就拥有了这些元组的排序列表,然后只需要从中挑选出索引即可。此外,这还消除了之后在序列中查找元素的需要,这可能使其成为 O(N²) 操作,而这是 O(N log(N))。
http://pythonhosted.org/ranking/,具有易于遵循的说明页面。要下载,只需使用easy_install ranking
# 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,这比迄今为止建议的其他方法更好:
.index()
的建议都很糟糕,运行时复杂度为N^2;
.index()
搜索的基础上略有改进,但是在每次迭代时进行搜索和插入操作,这在时间(NlogN)和空间上仍然非常低效,并且还要求值是可散列的。
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)
希望可以帮助到有同样需求的小伙伴。
这里是记录玩家分数和排名的类。
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
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
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]
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库,但对于纯粹的独立代码来说,它足以在排序数组上实现二进制搜索过程,并使用唯一值来查询现有(在此数组中)值。