Wie zum invertieren einer permutation array in numpy
Gegeben, ein selbst-Indizierung (nicht sicher, ob dies der richtige Ausdruck ist) numpy-array, zum Beispiel:
a = np.array([3, 2, 0, 1])
Dieser stellt dieser permutation (=>
ist ein Pfeil):
0 => 3
1 => 2
2 => 0
3 => 1
Ich versuche, ein array repräsentieren die inverse transformation ohne es "manuell" in python, das ist, ich will einen Reine numpy Lösung. Das Ergebnis möchte ich in dem oben genannten Fall ist:
array([2, 3, 1, 0])
Entspricht
0 <= 3 0 => 2
1 <= 2 or 1 => 3
2 <= 0 2 => 1
3 <= 1 3 => 0
Es scheint so einfach, aber ich kann einfach nicht denken, wie es zu tun. Ich habe versucht zu googeln, aber habe nicht gefunden was relevant ist.
- Was zurückgegeben werden soll, für
a = np.array([1, 1, 1, 1])
? - Sie können davon ausgehen, dass solche Fälle nicht angezeigt.
Du musst angemeldet sein, um einen Kommentar abzugeben.
Der inversen einer permutation
p
vonnp.arange(n)
ist die array-Indizess
diese Artp
, d.h.muss alles wahr. Solche
s
ist genau das, wasnp.argsort
gibt:s[p] = xrange(p.size)
, überprüfen Sie bitte meine Antwort.Sortierung ist ein übermaß hier. Dies ist nur ein single-pass-linearzeit-Algorithmus mit konstanter Speicherbedarf:
Der obige code druckt
als erforderlich.
Den rest der Antwort befasst sich mit der effizienten Vektorisierung der oben
for
Schleife. , Wenn Sie nur wollen, die Lösung zu wissen, springen Sie an das Ende dieser Antwort.(Die original-Antwort von Aug 27, 2014; die timings sind gültig für NumPy 1.8. Ein update mit NumPy 1.11 folgt später.)
Single-pass-linearzeit-Algorithmus wird erwartet, schneller zu sein als
np.argsort
; interessanterweise die trivial-Vektorisierung (s[p] = xrange(p.size)
, siehe index-arrays) der oben genanntenfor
Schleife ist tatsächlich etwas langsamer, alsnp.argsort
solangep.size < 700 000
(gut, auf meiner Maschine, Ihre Laufleistung wird variieren):Aus meiner IPython notebook:
Schließlich die asymptotische Komplexität kicks (
O(n log n)
fürargsort
vs.O(n)
für die single-pass-Algorithmus) und die single-pass-Algorithmus, werden konsequent schneller nach einem ausreichend großenn = p.size
(Schwelle etwa 700k auf meinem Rechner).Allerdings gibt es eine weniger einfache Weise zu Vektorisieren die oben
for
Schleife mitnp.put
:Gibt für
n = 700 000
(die gleiche Größe wie oben):Dies ist ein schönes 5,6 x speed-up für den nächsten zu nichts!
Um fair zu sein,
np.argsort
schlägt immer noch dienp.put
Ansatz für kleineren
(der Wendepunkt ist umn = 1210
auf meiner Maschine):Dies ist wahrscheinlich, weil wir reservieren und füllen Sie in ein extra array (an der
np.arange()
call) mit dernp_put
Ansatz.Obwohl Sie nicht Fragen, für eine Cython-Lösung, nur aus Neugier, ich auch zeitlich die folgenden Cython-Lösung mit eingegeben memoryviews:
Timings:
So, die
np.put
Lösung ist noch nicht so schnell wie möglich (lief 12.8 ms für diese Eingangs Größe; argsort nahm 72.7 ms).Update am Feb 3, 2017 mit NumPy 1.11
Jamie, Andris und Paul darauf hingewiesen, in den Kommentaren unten, dass das performance-Problem mit fancy indexing gelöst wurde. Jamie sagt, es sei bereits aufgelöst NumPy 1.9. Getestet habe ich es mit Python 3.5 und NumPy 1.11 auf die Maschine, die ich mit zurück in 2014.
Timings:
Eine signifikante Verbesserung, in der Tat!
Abschluss
Alles in allem, würde ich mit dem
Ansatz für die code-Klarheit. Meiner Meinung nach ist es weniger dunkel als
argsort
, und auch schneller für große input-Größen. Wenn Geschwindigkeit ein Problem wird, würde ich mit dem Cython-Lösung.np.put
füllt eine wichtige Nische zwischen meine langsame Lösung und Cython. +1.unique
- Funktion finden Sie unter hier. FWIW, der Vorteilnp.put
über fancy indexing ist meist verschwunden in numpy 1.9..Würde ich gerne ein klein wenig mehr hintergrund zu larsmans richtige Antwort. Die Grund warum
argsort
korrekt ist, kann gefunden werden, wenn Sie die Darstellung einer permutation durch eine matrix. Der mathematische Vorteil eine permutation matrixP
ist, dass die matrix "arbeitet auf Vektoren", d.h. eine permutation-matrix-mal-Vektor-permutes den Vektor.Ihre permutation, die wie folgt aussieht:
Gegeben eine permutation matrix, wir können "rückgängig" multipication durch Multiplikation mit es die inverse
P^-1
. Die Schönheit der permutations-Matrizen ist, dass Sie sind orthogonal, daherP*P^(-1)=I
oder in anderen WortenP(-1)=P^T
, die inverse ist die transponierte. Das bedeutet, wir nehmen die Indizes die transponierte matrix zu finden, die Ihre umgekehrte permutation Vektor:Welche, wenn man darüber nachdenkt, ist genau das gleiche wie das finden der Indizes über die Spalten Sortieren von
P
!