Ordnen Sie Elemente in einem Array mit Python / NumPy, ohne das Array zweimal zu sortieren

100

Ich habe ein Array von Zahlen und möchte ein weiteres Array erstellen, das den Rang jedes Elements im ersten Array darstellt. Ich benutze Python und NumPy.

Beispielsweise:

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

Hier ist die beste Methode, die ich mir ausgedacht habe:

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

Gibt es bessere / schnellere Methoden, die es vermeiden, das Array zweimal zu sortieren?

Joshayers
quelle
6
Ihre letzte Zeile entspricht ranks = temp.argsort().
Sven Marnach

Antworten:

67

Verwenden Sie im letzten Schritt das Schneiden auf der linken Seite:

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

Dadurch wird vermieden, dass zweimal sortiert wird, indem die Permutation im letzten Schritt invertiert wird.

Sven Marnach
quelle
3
Perfekt, danke! Ich wusste, dass es eine Lösung gab und es würde offensichtlich erscheinen, wenn ich sie sah. Ich habe einige Tests mit timeit durchgeführt, und diese Methode ist für kleine Arrays etwas langsamer. Auf meinem Computer sind sie gleich, wenn das Array 2.000 Elemente enthält. Mit 20.000 Elementen ist Ihre Methode etwa 25% schneller.
Joshayers
Gibt es eine Empfehlung, wie dies zeilenweise erfolgen soll?
Xaser
Für mehr als 1 Dim siehe Antwort unten.
Mathtick
100

Verwenden Sie argsort zweimal, um zuerst die Reihenfolge des Arrays zu ermitteln und dann die Rangfolge zu ermitteln:

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

Stellen Sie beim Umgang mit 2D-Arrays (oder höherdimensionalen Arrays) sicher, dass Sie ein Achsenargument an argsort übergeben, um es über die richtige Achse zu ordnen.

k.rooijers
quelle
2
Beachten Sie, dass, wenn Zahlen in Ihrem Eingabearray wiederholt werden (z. B. [4,2,7,1,1]), die Ausgabe diese Zahlen basierend auf ihrer Array-Position ( [3,2,4,0,1])
bewertet
4
Zweimaliges Sortieren ist ineffizient. Die Antwort von @Sven Marnach zeigt, wie man das Ranking mit einem einzigen Anruf an erreicht argsort.
Warren Weckesser
6
@WarrenWeckesser: Ich habe gerade den Unterschied zwischen den beiden getestet, und Sie haben Recht für große Arrays, aber für alles, was kleiner ist (n <100), ist Double Argsort schneller (ungefähr 20% schneller für n = 100 und ungefähr 5-mal schneller für n = 10). Wenn Sie also viele Rankings über viele kleine Wertesätze hinweg durchführen müssen, ist diese Methode viel besser.
naught101
3
@WarrenWeckesser: Eigentlich irre ich mich, diese Methode ist zweifellos besser. Beide Methoden sind auch viel schneller als die scipy.stats-Methode. Ergebnisse: gist.github.com/naught101/14042d91a2d0f18a6ae4
naught101
1
@ naught101: Es gibt einen Fehler in Ihrem Skript. Die Linie array = np.random.rand(10)sollte sein array = np.random.rand(n).
Warren Weckesser
88

Diese Frage ist ein paar Jahre alt und die akzeptierte Antwort ist großartig, aber ich denke, das Folgende ist immer noch erwähnenswert. Wenn Ihnen die Abhängigkeit nichts ausmacht scipy, können Sie Folgendes verwenden 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])

Ein nettes Merkmal von rankdataist, dass das methodArgument mehrere Optionen für den Umgang mit Bindungen bietet. Zum Beispiel gibt es drei Vorkommen von 20 und zwei Vorkommen von 40 in b:

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

Die Standardeinstellung weist den gebundenen Werten den Durchschnittsrang zu:

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

method='ordinal' weist aufeinanderfolgende Ränge zu:

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

method='min' weist allen gebundenen Werten den Mindestrang der gebundenen Werte zu:

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

Weitere Optionen finden Sie in der Dokumentzeichenfolge.

Warren Weckesser
quelle
1
Ja, dies ist die beste Antwort überall dort, wo Randfälle wichtig sind.
naught101
Ich finde es interessant, dass rankdataderselbe Mechanismus wie die akzeptierte Antwort verwendet wird, um das anfängliche Ranking intern zu generieren.
AlexV
5

Ich habe versucht, beide Lösungen für Arrays A mit mehr als einer Dimension zu erweitern, vorausgesetzt, Sie verarbeiten Ihr Array zeilenweise (Achse = 1).

Ich habe den ersten Code mit einer Schleife für Zeilen erweitert. wahrscheinlich kann es verbessert werden

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

Und der zweite, der dem Vorschlag von k.rooijers folgt, wird:

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

Ich habe zufällig 400 Arrays mit Form (1000.100) generiert. Der erste Code dauerte ungefähr 7,5, der zweite 3,8.

Igor Fobia
quelle
5

Eine vektorisierte Version eines gemittelten Ranges finden Sie unten. Ich liebe np.unique, es erweitert wirklich den Umfang dessen, was Code effizient vektorisiert werden kann und was nicht. Abgesehen von der Vermeidung von Python-for-Schleifen vermeidet dieser Ansatz auch die implizite Doppelschleife über '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
Eelco Hoogendoorn
quelle
Apropos; Ich habe diesen Code so erstellt, dass er dieselbe Ausgabe wie der andere gemittelte Rangcode erzeugt, aber ich kann mir vorstellen, dass der Mindestrang einer Gruppe sich wiederholender Zahlen genauso gut funktioniert. Dies kann noch einfacher erhalten werden als >>> unique, index, inverse = np.unique (a, True, True) >>> rank_min = rank [index] [inverse]
Eelco Hoogendoorn
Ich erhalte den folgenden Fehler mit Ihrer Lösung (numpy 1.7.1): AttributeError: Das Objekt 'numpy.ufunc' hat kein Attribut 'at'
Fear
Dies erfordert eine neuere Version von numpy. Ihre ist ziemlich alt
Eelco Hoogendoorn
4

Neben der Eleganz und Kürze der Lösungen stellt sich auch die Frage nach der Leistung. Hier ist ein kleiner Maßstab:

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)
Mischa Lisovyi
quelle
1
Gute Idee, aber für einen fairen Vergleich sollten Sie verwenden rankdata(l, method='ordinal') - 1.
Warren Weckesser
3

Verwenden Sie argsort () zweimal, um dies zu tun:

>>> array = [4,2,7,1]
>>> ranks = numpy.array(array).argsort().argsort()
>>> ranks
array([2, 1, 3, 0])
Kwong
quelle
2
Dies wurde bereits erwähnt , bevor Sie Ihre Antwort
gaben
2

Ich habe die oben genannten Methoden ausprobiert, bin aber gescheitert, weil ich viele Zeoren hatte. Ja, auch bei Floats können doppelte Elemente wichtig sein.

Also schrieb ich eine modifizierte 1D-Lösung, indem ich einen Schritt zur Überprüfung der Krawatte hinzufügte:

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

Ich glaube, es ist so effizient wie es nur sein kann.

h2kyeong
quelle
0

Ich mochte die Methode von k.rooijers, aber wie rcoup schrieb, werden wiederholte Zahlen nach der Array-Position eingestuft. Das war nicht gut für mich, deshalb habe ich die Version geändert, um die Ränge nachzubearbeiten und alle wiederholten Zahlen zu einem kombinierten Durchschnittsrang zusammenzuführen:

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

Ich hoffe, das könnte auch anderen helfen. Ich habe versucht, eine andere Lösung dafür zu finden, konnte aber keine finden ...

Martin F. Thomsen
quelle
0

Argsort und Slice sind Symmetrieoperationen.

Versuchen Sie es zweimal mit Slice anstatt zweimal mit Argsort. da Slice schneller ist als Argsort

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