Ich habe ein numpy Array wie dieses: [1 2 2 0 0 1 3 5]
Ist es möglich, den Index der Elemente als 2D-Array abzurufen? Zum Beispiel wäre die Antwort für die obige Eingabe[[3 4], [0 5], [1 2], [6], [], [7]]
Momentan muss ich die verschiedenen Werte schleifen und numpy.where(input == i)
für jeden Wert aufrufen , was eine schreckliche Leistung mit einer ausreichend großen Eingabe hat.
python
numpy
numpy-ndarray
Frederico Schardong
quelle
quelle
np.argsort([1, 2, 2, 0, 0, 1, 3, 5])
gibtarray([3, 4, 0, 5, 1, 2, 6, 7], dtype=int64)
. dann können Sie einfach die nächsten Elemente vergleichen.Antworten:
Hier ist ein O (max (x) + len (x)) Ansatz unter Verwendung von
scipy.sparse
:Dies funktioniert durch Erstellen einer Sparse-Matrix mit Einträgen an den Positionen (x [0], 0), (x [1], 1), ... Mit dem
CSC
Format (komprimierte Sparse-Spalte) ist dies ziemlich einfach. Die Matrix wird dann in dasLIL
Format (verknüpfte Liste) konvertiert. In diesem Format werden die Spaltenindizes für jede Zeile als Liste in ihremrows
Attribut gespeichert. Wir müssen sie also nur nehmen und in eine Liste konvertieren.Beachten Sie, dass
argsort
Lösungen auf der Basis kleiner Arrays wahrscheinlich schneller sind, bei einigen jedoch nicht wahnsinnig großen Größen überkreuzen.BEARBEITEN:
argsort
-basiertenumpy
-nur Lösung:Wenn die Reihenfolge der Indizes innerhalb von Gruppen keine Rolle spielt, können Sie es auch versuchen
argpartition
(es macht in diesem kleinen Beispiel keinen Unterschied, aber dies ist im Allgemeinen nicht garantiert):BEARBEITEN:
@ Divakar rät von der Verwendung von ab
np.split
. Stattdessen ist eine Schleife wahrscheinlich schneller:Oder Sie können den brandneuen Walross-Operator (Python3.8 +) verwenden:
BEARBEITEN (BEARBEITET):
(Nicht reines Numpy): Alternativ zu Numba (siehe Beitrag von @ senderle) können wir auch Pythran verwenden.
Kompilieren mit
pythran -O3 <filename.py>
Hier
numba
gewinnt ein Whisker leistungsmäßig:Ältere Sachen:
Timings vs. Numba (alt)
quelle
np.split
.Eine mögliche Option, die von der Größe Ihrer Daten abhängt, besteht darin, sie einfach zu löschen
numpy
und zu verwendencollections.defaultdict
:Dann erhalten Sie ein Wörterbuch von
{value1: [index1, index2, ...], value2: [index3, index4, ...]}
. Die Zeitskalierung ist nahezu linear mit der Größe des Arrays, sodass 10.000.000 auf meinem Computer ~ 2,7 Sekunden benötigen, was vernünftig genug erscheint.quelle
Obwohl es sich um eine
numpy
Lösung handelt, habe ich mich entschlossen zu prüfen, ob es eine interessantenumba
Lösung gibt. Und tatsächlich gibt es! Hier ist ein Ansatz, der die partitionierte Liste als zerlumptes Array darstellt, das in einem einzelnen vorab zugewiesenen Puffer gespeichert ist. Dies ist inspiriert von demargsort
von Paul Panzer vorgeschlagenen Ansatz . (Eine ältere Version, die nicht so gut lief, aber einfacher war, siehe unten.)Dadurch wird eine Liste mit zehn Millionen Elementen in 75 ms verarbeitet. Dies entspricht einer fast 50-fachen Beschleunigung gegenüber einer in reinem Python geschriebenen listenbasierten Version.
Für eine langsamere, aber etwas besser lesbare Version hatte ich Folgendes zuvor, basierend auf der kürzlich hinzugefügten experimentellen Unterstützung für dynamisch dimensionierte "typisierte Listen", mit denen wir jeden Behälter viel schneller in einer nicht ordnungsgemäßen Weise füllen können.
Dies ringt
numba
ein bisschen mit der Typ-Inferenz-Engine, und ich bin sicher, dass es einen besseren Weg gibt, mit diesem Teil umzugehen. Dies stellt sich auch als fast 10x langsamer als oben heraus.Ich habe diese gegen Folgendes getestet:
Ich habe sie auch gegen eine vorkompilierte Cython-Version getestet, die der
enum_bins_numba_buffer
(unten ausführlich beschriebenen) ähnelt .Auf einer Liste von zehn Millionen zufälligen Ints (
ints = np.random.randint(0, 100, 10000000)
) erhalte ich die folgenden Ergebnisse:Beeindruckenderweise
numba
übertrifft diese Art der Arbeit einecython
Version derselben Funktion, selbst wenn die Grenzwertprüfung deaktiviert ist. Ich bin noch nicht vertraut genugpythran
, um diesen Ansatz damit zu testen, aber ich wäre an einem Vergleich interessiert. Aufgrund dieser Beschleunigung scheint es wahrscheinlich, dass diepythran
Version mit diesem Ansatz auch etwas schneller ist.Hier ist die
cython
Version als Referenz mit einigen Build-Anweisungen. Nach dercython
Installation benötigen Sie eine einfachesetup.py
Datei wie die folgende:Und das Cython-Modul
enum_bins_cython.pyx
:Führen Sie mit diesen beiden Dateien in Ihrem Arbeitsverzeichnis den folgenden Befehl aus:
Sie können die Funktion dann mit importieren
from enum_bins_cython import enum_bins_cython
.quelle
Hier ist eine wirklich sehr seltsame Art, dies zu tun, die schrecklich ist, aber ich fand es zu lustig, um sie nicht zu teilen - und alles
numpy
!EDIT: Dies ist die beste Methode, die ich auf diesem Weg finden konnte. Es ist immer noch 10x langsamer als die
argsort
Lösung von @PaulPanzer :quelle
Sie können dies tun, indem Sie ein Wörterbuch mit Zahlen erstellen. Schlüssel sind die Zahlen und Werte sollten die Indizes sein, die die Zahl sieht. Dies ist eine der schnellsten Möglichkeiten. Sie können den folgenden Code sehen:
quelle
Pseudocode:
Ermitteln Sie die "Anzahl der 1d-Arrays im 2d-Array", indem Sie den Minimalwert Ihres Numpy-Arrays vom Maximalwert subtrahieren und dann plus eins. In Ihrem Fall ist es 5-0 + 1 = 6
Initialisieren Sie ein 2d-Array mit der Anzahl der darin enthaltenen 1d-Arrays. Initialisieren Sie in Ihrem Fall ein 2d-Array mit 6 1d-Arrays. Jedes 1d-Array entspricht einem eindeutigen Element in Ihrem Numpy-Array. Das erste 1d-Array entspricht beispielsweise '0', das zweite 1d-Array entspricht '1', ...
Durchlaufen Sie Ihr Numpy-Array und setzen Sie den Index des Elements in das entsprechende 1d-Array. In Ihrem Fall wird der Index des ersten Elements in Ihrem Numpy-Array auf das zweite 1d-Array gesetzt, der Index des zweiten Elements in Ihrem Numpy-Array wird auf das dritte 1d-Array gesetzt, ....
Die Ausführung dieses Pseudocodes dauert linear, da dies von der Länge Ihres Numpy-Arrays abhängt.
quelle
Dies gibt Ihnen genau das, was Sie wollen und würde ungefähr 10.000 Sekunden für 10.000.000 auf meinem Computer dauern:
quelle
Wenn Sie also eine Liste von Elementen haben, möchten Sie (Element-, Index-) Paare bilden. In linearer Zeit könnte dies wie folgt erfolgen:
Dies sollte O (n) Zeit dauern. Ich kann mir derzeit keine schnellere Lösung vorstellen, werde sie aber hier aktualisieren, wenn ich dies tue.
quelle