AnswerBun.com

Efficient method to calculate the rank vector of a list in Python

Stack Overflow Asked by Tamás on August 19, 2020

I’m looking for an efficient way to calculate the rank vector of a list in Python, similar to R’s rank function. In a simple list with no ties between the elements, element i of the rank vector of a list l should be x if and only if l[i] is the x-th element in the sorted list. This is simple so far, the following code snippet does the trick:

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

Things get complicated, however, if the original list has ties (i.e. multiple elements with the same value). In that case, all the elements having the same value should have the same rank, which is the average of their ranks obtained using the naive method above. So, for instance, if I have [1, 2, 3, 3, 3, 4, 5], the naive ranking gives me [0, 1, 2, 3, 4, 5, 6], but what I would like to have is [0, 1, 3, 3, 3, 5, 6]. Which one would be the most efficient way to do this in Python?


Footnote: I don’t know if NumPy already has a method to achieve this or not; if it does, please let me know, but I would be interested in a pure Python solution anyway as I’m developing a tool which should work without NumPy as well.

11 Answers

Using scipy, the function you are looking for is 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.])

The ranks start at 1, rather than 0 (as in your example), but then again, that's the way R's rank function works as well.

Here is a pure-python equivalent of scipy's rankdata function:

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]

Correct answer by unutbu on August 19, 2020

This works for the spearman correlation coefficient .

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]

Answered by behanm on August 19, 2020

I really don't get why all the existing solutions are so complex. This can be done just like this:

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

You build tuples which contain the elements and a running index. Then you sort the whole thing, and tuples sort by their first element and during ties by their second element. This way one has a sorted list of these tuples and just need to pick out the indices from that afterwards. Also this removes the need to look up elements in the sequence afterwards, which likely makes it a O(N²) operation whereas this is O(N log(N)).

Answered by Martin Ueding on August 19, 2020

So.. this is 2019, and I have no idea why nobody suggested the following:

# 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

This approach has linear runtime complexity after the initial sort, it only stores 2 arrays of indices, and does not require values to be hashable (only pairwise comparison needed).

AFAICT, this is better than other approaches suggested so far:

  • @unutbu's approach is essentially similar, but (I would argue) too complicated for what the OP asked;
  • All suggestions using .index() are terrible, with a runtime complexity of N^2;
  • @Yuvraj Singh improves slightly upon the .index() search using a dictionary, however with search and insert operations at each iteration, this is still highly inefficient both in time (NlogN) and space, and it also requires the values to be hashable.

Answered by Jonathan H on August 19, 2020

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

sorted(l) will give the sorted version index(x) will give the index in the sorted array

for example :

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

Answered by Jialiang Gu on August 19, 2020

This is one of the functions that I wrote to calculate rank.

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]

input:

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

output:

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

Answered by Yuvraj Singh on August 19, 2020

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

timecomplexity is 46.2us

Answered by vamsi21 on August 19, 2020

These codes give me a lot of inspiration, especially unutbu's code. However my needs are simpler, so I changed the code a little.

Hoping to help the guys with the same needs.

Here is the class to record the players' scores and ranks.

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

Some data.

l = [Player(90,0),Player(95,0),Player(85,0), Player(90,0),Player(95,0)]

Here is the code for calculation:

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

Answered by Joe on August 19, 2020

Here is a small variation of unutbu's code, including an optional 'method' argument for the type of value of tied ranks.

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

Answered by Sunthar on August 19, 2020

There is a really nice module called Ranking http://pythonhosted.org/ranking/ with an easy to follow instruction page. To download, simply use easy_install ranking

Answered by Kerry Kalweit on August 19, 2020

This doesn't give the exact result you specify, but perhaps it would be useful anyways. The following snippet gives the first index for each element, yielding a final rank vector of [0, 1, 2, 2, 2, 5, 6]

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

Your own testing would have to prove the efficiency of this.

Answered by stw_dev on August 19, 2020

Add your own answers!

Related Questions

Update sql database from datagridview in c#

2  Asked on December 25, 2021 by user13987069

   

Wait for observable to get array-data

2  Asked on December 25, 2021 by bena

     

How can you add an object into json through python

1  Asked on December 25, 2021 by jonasmanthebot

   

Pandas reindex to fill date index

1  Asked on December 25, 2021 by niviral

       

checking if file exists in FileInfo[]

1  Asked on December 25, 2021 by abhilash-vg

     

Processing of a file: byte arrays and dimentions

2  Asked on December 25, 2021 by ld420

   

CSS Grid template areas in wrong order

1  Asked on December 25, 2021

   

c++ should I prefer union or exception

2  Asked on December 25, 2021 by chetzacoalt

   

How to set default state for an object when using useState

1  Asked on December 25, 2021 by ross-attrill

   

friend class and the scope of function arguments

2  Asked on December 25, 2021 by user2269707

   

How to remove unchecked value from list?

3  Asked on December 25, 2021 by afelip

   

handling for loop exceptions

6  Asked on December 25, 2021 by sivaram

     

How to filter JSON Data in JS

1  Asked on December 25, 2021 by user12129876

       

Ask a Question

Get help from others!

© 2022 AnswerBun.com. All rights reserved. Sites we Love: PCI Database, MenuIva, UKBizDB, Menu Kuliner, Sharing RPP, SolveDir