webentwicklung-frage-antwort-db.com.de

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

Ich habe ein Array mit 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 ein zweimaliges Sortieren des Arrays vermeiden?

78
joshayers

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

Dies vermeidet ein zweimaliges Sortieren, indem die Permutation im letzten Schritt invertiert wird.

54
Sven Marnach

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

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

Wenn Sie mit 2D-Arrays (oder Arrays mit höheren Dimensionen) arbeiten, müssen Sie ein Achsenargument an argsort übergeben, um über die richtige Achse zu ordnen.

82
k.rooijers

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 von scipy nichts ausmacht, können Sie 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 Feature von rankdata ist, dass das Argument method verschiedene Optionen für die Behandlung von Bindungen bietet. Beispielsweise 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 verknüpften Werten den durchschnittlichen Rang 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 verknüpften Werten den Mindestrang der verknüpften 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 Dokumentation.

73

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

Ich habe den ersten Code mit einer Schleife in 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 die zweite, die k.rooijers Vorschlag folgt, wird:

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

Ich habe zufällig 400 Arrays mit Shape generiert (1000.100). Der erste Code dauerte ungefähr 7.5, der zweite 3.8.

4
Igor Fobia

Eine vektorisierte Version eines gemittelten Rangs finden Sie unten. Ich liebe np.unique, es erweitert wirklich den Umfang dessen, was Code effizient vektorisieren kann und was nicht. Dieser Ansatz vermeidet nicht nur python for-loops, sondern 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
4

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 habe ich eine modifizierte 1D-Lösung geschrieben, indem ich einen Schritt zur Überprüfung der Krawatte hinzugefügt habe:

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 geht.

2
h2kyeong

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

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

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

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

Ich mochte die Methode von k.rooijers, aber wie rcoup schrieb, werden wiederholte Zahlen entsprechend 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, dies könnte auch anderen helfen. Ich habe versucht, eine andere Lösung für dieses Problem zu finden, konnte aber keine finden ...

0