tamaño - Método eficiente para calcular el vector de rango de una lista en Python

sacar elementos de una lista python

Question

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

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

Sin embargo, las cosas se complican si la lista original tiene vínculos (es decir, varios elementos con el mismo valor). En ese caso, todos los elementos que tienen el mismo valor deben tener el mismo rango, que es el promedio de sus rangos obtenidos utilizando el método ingenuo anterior. Entonces, por ejemplo, si tengo [1, 2, 3, 3, 3, 4, 5] , la clasificación ingenua 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 lograrlo o no; si es así, hágamelo saber, pero de todos modos me interesaría una solución Python pura, ya que estoy desarrollando una herramienta que también debería funcionar sin NumPy.

Answer 1

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 2

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

Answer 3

Esto no proporciona el resultado exacto que especifique, pero quizás sea útil de todos modos. El siguiente fragmento de código proporciona el primer índice para cada elemento, lo que arroja un vector de 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__)]

Tus propias pruebas tendrían que demostrar la eficiencia de esto.

Answer 4

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é un poco el código.

Con la esperanza de ayudar a los chicos con las mismas necesidades.

Aquí está la clase para registrar las puntuaciones 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)]

Aquí está 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 5

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

Answer 6

Usando scipy, la función que está buscando 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.])

Los rangos comienzan en 1, en lugar de 0 (como en tu ejemplo), pero, de nuevo, así es como funciona la función de R de R

Aquí hay un equivalente a python puro de la función rankdata de scipy:

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 7

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