Classez les éléments d'un tableau à l'aide de Python / NumPy, sans trier le tableau deux fois

J'ai un tableau de nombres et j'aimerais créer un autre tableau qui représente le rang de chaque élément dans le premier tableau. J'utilise Python et NumPy.

Par exemple:

array = [4,2,7,1]
ranks = [2,1,3,0]

Voici la meilleure méthode que j'ai trouvée:

array = numpy.array([4,2,7,1])
temp = array.argsort()
ranks = numpy.arange(len(array))[temp.argsort()]

Existe-t-il des méthodes meilleures / plus rapides qui évitent de trier le tableau deux fois?

Utilisez le tranchage sur le côté gauche dans la dernière étape:

array = numpy.array([4,2,7,1])
temp = array.argsort()
ranks = numpy.empty_like(temp)
ranks[temp] = numpy.arange(len(array))

Cela évite de trier deux fois en inversant la permutation lors de la dernière étape.

Utilisez argsort deux fois, d'abord pour obtenir l'ordre du tableau, puis pour obtenir le classement:

array = numpy.array([4,2,7,1])
order = array.argsort()
ranks = order.argsort()

Lorsque vous traitez avec des tableaux 2D (ou de dimension supérieure), assurez-vous de passer un argument d'axe à argsort pour passer le bon axe.

Cette question date de quelques années et la réponse acceptée est excellente, mais je pense que ce qui suit mérite d'être mentionné. Si cela ne vous dérange pas de la dépendance scipy, vous pouvez utiliser scipy.stats.rankdata:

In [22]: from scipy.stats import rankdata

In [23]: a = [4, 2, 7, 1]

In [24]: rankdata(a)
Out[24]: array([ 3.,  2.,  4.,  1.])

In [25]: (rankdata(a) - 1).astype(int)
Out[25]: array([2, 1, 3, 0])

Une fonctionnalité intéressante de rankdataest que l' methodargument offre plusieurs options pour gérer les liens. Par exemple, il y a trois occurrences de 20 et deux occurrences de 40 dans b:

In [26]: b = [40, 20, 70, 10, 20, 50, 30, 40, 20]

La valeur par défaut attribue le rang moyen aux valeurs liées:

In [27]: rankdata(b)
Out[27]: array([ 6.5,  3. ,  9. ,  1. ,  3. ,  8. ,  5. ,  6.5,  3. ])

method='ordinal' attribue des rangs consécutifs:

In [28]: rankdata(b, method='ordinal')
Out[28]: array([6, 2, 9, 1, 3, 8, 5, 7, 4])

method='min' affecte le rang minimum des valeurs liées à toutes les valeurs liées:

In [29]: rankdata(b, method='min')
Out[29]: array([6, 2, 9, 1, 2, 8, 5, 6, 2])

Voir la docstring pour plus d'options.

J'ai essayé d'étendre les deux solutions pour les tableaux A de plus d'une dimension, en supposant que vous traitez votre tableau ligne par ligne (axe = 1).

J'ai étendu le premier code avec une boucle sur les lignes; il peut probablement être amélioré

temp = A.argsort(axis=1)
rank = np.empty_like(temp)
rangeA = np.arange(temp.shape[1])
for iRow in xrange(temp.shape[0]): 
    rank[iRow, temp[iRow,:]] = rangeA

Et le second, suivant la suggestion de k.rooijers, devient:

temp = A.argsort(axis=1)
rank = temp.argsort(axis=1)

J'ai généré au hasard 400 tableaux de forme (1000, 100); le premier code prenait environ 7,5, le second 3,8.

Pour une version vectorisée d'un rang moyen, voir ci-dessous. J'adore np.unique, cela élargit vraiment la portée de ce que le code peut et ne peut pas être efficacement vectorisé. En plus d'éviter les boucles for python, cette approche évite également la double boucle implicite sur «a».

import numpy as np

a = np.array( [4,1,6,8,4,1,6])

a = np.array([4,2,7,2,1])
rank = a.argsort().argsort()

unique, inverse = np.unique(a, return_inverse = True)

unique_rank_sum = np.zeros_like(unique)
np.add.at(unique_rank_sum, inverse, rank)
unique_count = np.zeros_like(unique)
np.add.at(unique_count, inverse, 1)

unique_rank_mean = unique_rank_sum.astype(np.float) / unique_count

rank_mean = unique_rank_mean[inverse]

print rank_mean

Outre l'élégance et la brièveté des solutions, il y a aussi la question de la performance. Voici un petit repère:

import numpy as np
from scipy.stats import rankdata
l = list(reversed(range(1000)))

%%timeit -n10000 -r5
x = (rankdata(l) - 1).astype(int)
>>> 128 µs ± 2.72 µs per loop (mean ± std. dev. of 5 runs, 10000 loops each)

%%timeit -n10000 -r5
a = np.array(l)
r = a.argsort().argsort()
>>> 69.1 µs ± 464 ns per loop (mean ± std. dev. of 5 runs, 10000 loops each)

%%timeit -n10000 -r5
a = np.array(l)
temp = a.argsort()
r = np.empty_like(temp)
r[temp] = np.arange(len(a))
>>> 63.7 µs ± 1.27 µs per loop (mean ± std. dev. of 5 runs, 10000 loops each)

Utilisez argsort () deux fois pour le faire:

>>> array = [4,2,7,1]
>>> ranks = numpy.array(array).argsort().argsort()
>>> ranks
array([2, 1, 3, 0])

J'ai essayé les méthodes ci-dessus, mais j'ai échoué car j'avais beaucoup de zeores. Oui, même avec des éléments flottants, les doublons peuvent être importants.

J'ai donc écrit une solution 1D modifiée en ajoutant une étape de vérification des liens:

def ranks (v):
    import numpy as np
    t = np.argsort(v)
    r = np.empty(len(v),int)
    r[t] = np.arange(len(v))
    for i in xrange(1, len(r)):
        if v[t[i]] <= v[t[i-1]]: r[t[i]] = r[t[i-1]]
    return r

# test it
print sorted(zip(ranks(v), v))

Je pense que c'est aussi efficace que possible.

J'ai aimé la méthode de k.rooijers, mais comme l'a écrit rcoup, les nombres répétés sont classés en fonction de la position du tableau. Ce n'était pas bon pour moi, j'ai donc modifié la version pour post-traiter les rangs et fusionner tous les nombres répétés en un rang moyen combiné:

import numpy as np
a = np.array([4,2,7,2,1])
r = np.array(a.argsort().argsort(), dtype=float)
f = a==a
for i in xrange(len(a)):
   if not f[i]: continue
   s = a == a[i]
   ls = np.sum(s)
   if ls > 1:
      tr = np.sum(r[s])
      r[s] = float(tr)/ls
   f[s] = False

print r  # array([ 3. ,  1.5,  4. ,  1.5,  0. ])

J'espère que cela pourrait aussi aider les autres, j'ai essayé de trouver une autre solution à cela, mais je n'ai pas trouvé de solution ...

argsort et slice sont des opérations de symétrie.

essayez slice deux fois au lieu d'argsort deux fois. puisque slice est plus rapide que argsort

array = numpy.array([4,2,7,1])
order = array.argsort()
ranks = np.arange(array.shape[0])[order][order]

Version plus générale de l'une des réponses:

In [140]: x = np.random.randn(10, 3)

In [141]: i = np.argsort(x, axis=0)

In [142]: ranks = np.empty_like(i)

In [143]: np.put_along_axis(ranks, i, np.repeat(np.arange(x.shape[0])[:,None], x.shape[1], axis=1), axis=0)

Voir Comment utiliser numpy.argsort () comme index dans plus de 2 dimensions? pour généraliser à plus de dims.