Método eficiente para calcular el vector de rango de una lista en Python

Question

Estoy buscando una manera eficiente de calcular el vector de rango de una lista en Python, similar a la función de R rank. En una lista simple sin vínculos entre los elementos, elemento i del vector de rango de una lista l debe ser x si y sólo si l[i] es el elemento -ésimo x en la lista ordenada. Esto es simple hasta el momento, el siguiente fragmento de código hace el truco:

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

las cosas se complican, sin embargo, si la lista original tiene lazos (es decir, múltiples elementos con el mismo valor). En ese caso, todos los elementos que tengan el mismo valor deberían tener el mismo rango, que es el promedio de sus rangos obtenidos usando el método ingenuo anterior. Entonces, por ejemplo, si tengo [1, 2, 3, 3, 3, 4, 5], el ranking ingenuo me da [0, 1, 2, 3, 4, 5, 6], pero lo que me gustaría tener es [0, 1, 3, 3, 3, 5, 6]. ¿Cuál sería la forma más eficiente de hacer esto en Python?

---

Nota al pie: No sé si NumPy ya tiene un método para lograr esto o no; si lo hace, hágamelo saber, pero de todos modos estaría interesado en una solución pura de Python, ya que estoy desarrollando una herramienta que también debería funcionar sin NumPy.

Answer 1

Usando scipy, la función que busca es 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.]) 

Las filas comienzan en 1, en lugar de 0 (como en el ejemplo), pero por otra parte, que es la forma La función R de rank también funciona.

Aquí es una pura-pitón equivalente de la función rankdata scipy 's:

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

Esto no da el resultado exacto que especifique, pero quizá sería útil de todos modos. El siguiente fragmento da el primer índice para cada elemento, produciendo un vector rango final de [0, 1, 2, 2, 2, 5, 6]

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

sus propias pruebas tendría que demostrar la eficacia de esta.

Answer 3

Hay un módulo muy bonito llamado Ranking http://pythonhosted.org/ranking/ con una página de instrucciones fácil de seguir. Para descargar, simplemente use easy_install ranking

Answer 4

Aquí hay una pequeña variación del código de unutbu, que incluye un argumento opcional de 'método' para el tipo de valor de los rangos vinculados.

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 5

Estos códigos me dan mucha inspiración, especialmente el código de unutbu. Sin embargo mis necesidades son más simples, así que cambié el código un poco.

Esperando ayudar a los chicos con las mismas necesidades.

Aquí está la clase para registrar los puntajes y rangos de los jugadores.

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

Algunos datos.

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

Este es el código para el cálculo:

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 6

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 es 46.2us

Answer 7

Ésta es una de las funciones que escribí para calcular el rango.

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] 

entrada: calculate_rank ([1,3,4,8,7,5,4,6])
salida: [1, 2, 3, 7, 6, 4, 3, 5]