Speed up map() funktion

[schneitzmaster]

Hey Leute,

ich habe zwei numpy arrays. Der erste Array (nds_ids) beinhaltet Indizes der zweite (ele) verweist in jeder Zeile auf die Indizes von nds_ids.
Nun möchte ich nur die Zeilen von ele extrahieren die auch auf tatsächlich existierende Indizes in nds_ids verweisen.
Momentan läuft das Ganze über:

Code: Alles auswählen

import numpy as np
nds_ids = np.array( [1,2,3,4,5,6,7],dtype=int )
ele     = np.array( [ [1,2,3],[8,5,3],[4,5,1] ],dtype=int )

result  = np.where( map(lambda x: np.all(np.in1d(x, nds_ids)   ),ele) )[0]
print result

Für große Arrays dauert das allerdings sehr lang. Gibt es dafür eine schnellere / elegantere Variante evtl. mittels numpy Funktionen?

[EyDu]

Mal auf die schnelle:

Code: Alles auswählen

np.where(np.all(np.in1d(ele, nds_ids).reshape(ele.shape), axis=1))

Ich behaupte aber mal, dass es aber noch schöner geht.

[MagBen]

Wenn nds_ids sortiert ist, dann kannst Du das so ausnutzen:

Code: Alles auswählen

np.where(np.all(np.searchsorted(nds_ids, ele)<nds_ids.size, axis=1))[0]

[schneitzmaster]

@ EyDu: das ist eine gut Möglichkeit. So funktioniert das ganze viel schneller.
@ MagBen: die Werte in nds_ids können sortiert werden, allerdings kann nds_ids auch so aussehen

Code: Alles auswählen

nds_ids = np.array( [1,2,3,4,57,612,732],dtype=int )

Dann funktioniert deine Variante leider nicht.

[MagBen]

so aber:

Code: Alles auswählen

np.where(np.all(nds_ids[np.searchsorted(nds_ids, ele)]==ele, axis=1))[0]

[MagBen]

Auch diese Variante hat Schwächen, für

Code: Alles auswählen

nds_ids = np.array( [1,2,3,4,5],dtype=int )

gibt's einen IndexError. Das kann aber vermieden werden, dann ist es aber kein Einzeiler mehr.

Trotzdem würde ich bei großen Datenmengen die Performance-Vorteile von sortiertem Suchen ausnutzen.

[schneitzmaster]

@MagBen: okay danke ich werd mir das mit dem sorted array mal anschauen.

Vielleicht könnte ich hier gleich noch eine andere Frage los werden, die in die gleiche Richtung zielt.
Ich habe 2 arrays mit Knotenkoordinaten (nodes, new_nodes).
Nun möchte ich dem Knotenarray nodes die Knoten aus new_nodes hinzufügen oder falls der entsprechende Knoten schon enthalten ist, die index position extrahieren.
Praktisch umgestzt habe ich das Ganze in dem ich jeweils die Knotenposition aus new_nodes vom nodes-array abgezogen habe, die norm gebildet habe und dann diese norm als
kriterium herangezogen habe um zu entscheiden ob der Knoten bereits in nodes enthalten ist.
Auch hier ist wiederum die map Funktion zur Bildung des diff_arr der Flaschenhals.

Code: Alles auswählen

import numpy
nodes = np.array( [ [0.,0.,0.],
                    [1.,1.,1.],
                    [0.5,0.5,0.5]] )
new_nodes = np.array( [[1.,1.,1.],
                       [1.,1.,1.00001]])
delta = 10**-8
diff_arr     = np.array(map(lambda x: np.add(nodes,-x), new_nodes )) # LANGSAM
norm_arr  = map(lambda x: np.linalg.norm(x,axis=1),diff_arr)
idx      = []
for i in xrange(len(norm_arr)): # LOOP OVER ALL NODES
    norm_arr_i = norm_arr[i]
    if norm_arr_i.min()>delta:
        nodes = np.vstack( (nodes,new_nodes[i]) )
        idx.append(len(nodes)-1)
    else:
        idx.append(norm_arr_i.argmin())

print nodes
print idx

[EyDu]

Probiere das doch mal selber schrittweise selbst umzusetzen. Du hast ja nun schon ein paar Beispiele, wie du Operationen umschreiben musst. Wir können ja schlecht jedes deiner Performanceprobleme für dich lösen

Übrigens ist

Code: Alles auswählen

for i in rang(len(something)):

in Python ein Anti-Pattern und sollte nicht verwendet werden. Man kann direkt über Listen und andere Sequenzen iterieren, da braucht man keinen Umweg über den Index. Und wenn man doch mal den Index benötigt, dann gibt es dazu die enumerate-Funktion. Und falls du über mehrere Sequenzen gleichzeitig iterieren möchtest, dann hilft die zip-Funktion bei der Aufgabe.

[MagBen]

Jeder 3D-Vektor von new_nodes wird von jedem 3D-Vektor in nodes abgezogen. Die innerste Iteration über die 3D-Vektoren von nodes läuft schon innerhalb von Numpy. Die Python map Funktion durch ein Numpy Konstrukt zu ersetzen wird deshalb nicht viel bringen. Das ganze skalliert mit N**2.

Dieses Problem wird in einigen 3D-Tools durch einen Octtree gelöst:
Du berechnest zunächst die Bounding-Box Deines Problems. Diese Bounding-Box wird dann in 8 Unterboxen aufgeteilt, die auch wiederum jeweils in 8 Unterboxen aufgeteilt werden. Das macht man solange, bis nur noch eine akzeptable Anzahl an 3D-Vektoren in einer Box liegen. Es geht nun sehr schnell für einen neuen 3D-Vektor die Box zu finden in die er reingehört und danach muss nur noch der Abstand zu den 3D-Vektoren dieser Box berechnet werden.

[schneitzmaster]

@ EyDu: Ja das ist mir schon klar das ihr hier nicht meine Probleme lösen sollt. Ich dachte bloß, dass es gut rein passt wegen der map-funktion. Mir ist auch bewusst das man diese Anti-Pattern nicht verwenden sollte. Allerdings weiß ich bei meinem Beispiel keinen anderen Weg, da ich ja den Index i benötige. Um einmal auf norm_arr und auf new-nodes zu zugreifen. Geht das über enumerate eleganter?
@ MagBen: Danke für den Tip ich werde mal nach Octtree googeln. Das hört sich vielversprechend an.

[MagBen]

Danke für den Tip ich werde mal nach Octtree googeln. Das hört sich vielversprechend an.

Es gibt noch eine einfachere Variante:
Du sortierst nodes nach x-y-z. Bei new_nodes suchst Du dann sortiert zunächst nach x-delta und x+delta und nimmst alle nodes dazwischen mit. Bei den gefundenen Nodes wiederholst Du das für die Y-Koordinate und dann für die Z-Koordinate. Bei den Nodes die danach übrig bleiben berechnest Du den kartesischen Abstand.

Problematisch dabei ist, dass nodes nach jeder Änderung neu sortiert werden muss, das ist beim Octtree besser.

Die Abstandsberechnung lässt sich auch optimieren. np.norm quadriert alle Werte und zieht danach die Wurzel daraus. Das Wurzelziehen kann aber weggelassen werden, wenn Du mit delta**2 anstatt mit delta vergleichst.

[schneitzmaster]

Die Abstandsberechnung lässt sich auch optimieren. np.norm quadriert alle Werte und zieht danach die Wurzel daraus. Das Wurzelziehen kann aber weggelassen werden, wenn Du mit delta**2 anstatt mit delta vergleichst.

Wie kann ich das umsetzen ohne auf die schnell implementierten numpy-routinen zu verzichten? Ich meine die norm-funktion ist ja schon sehr auf geschwindigkeit optimiert. Wenn ich das ganz mittels schleifen nachprogrammiere wird's ja wieder langsamer.

[EyDu]

@ EyDu: Ja das ist mir schon klar das ihr hier nicht meine Probleme lösen sollt. Ich dachte bloß, dass es gut rein passt wegen der map-funktion. Mir ist auch bewusst das man diese Anti-Pattern nicht verwenden sollte. Allerdings weiß ich bei meinem Beispiel keinen anderen Weg, da ich ja den Index i benötige. Um einmal auf norm_arr und auf new-nodes zu zugreifen. Geht das über enumerate eleganter?

Hab ich doch schon geschrieben. Die zip-Funktion.

Wie kann ich das umsetzen ohne auf die schnell implementierten numpy-routinen zu verzichten? Ich meine die norm-funktion ist ja schon sehr auf geschwindigkeit optimiert. Wenn ich das ganz mittels schleifen nachprogrammiere wird's ja wieder langsamer.

Der einfachste weg ist wahrscheinlich ``scipy.spatial.KDTree``.

[schneitzmaster]

@ EyDu: Ich hab das Ganze jetzt mittels KDtree und der Methode "query_pairs" implementiert. Leider ist meine brute-force variente schneller bzw. genauso schnell.

In der Beschreibung davon steht auch:

For large dimensions (20 is already large) do not expect this to run significantly faster than brute force. High-dimensional nearest-neighbor queries are a substantial open problem in computer science.

[schneitzmaster]

So ich hab jetzt cKDTree benutzt und alles läuft super schnell. Da ich eine maximale Anzahl von 100k haben werde reicht mir das.
Vielen Dank noch mal for den Tip.

[Kebap]

Übrigens ist

Code: Alles auswählen

for i in rang(len(something)):

in Python ein Anti-Pattern und sollte nicht verwendet werden. Man kann direkt über Listen und andere Sequenzen iterieren, da braucht man keinen Umweg über den Index. Und wenn man doch mal den Index benötigt, dann gibt es dazu die enumerate-Funktion. Und falls du über mehrere Sequenzen gleichzeitig iterieren möchtest, dann hilft die zip-Funktion bei der Aufgabe.

@ EyDu: Ja das ist mir schon klar das ihr hier nicht meine Probleme lösen sollt. Ich dachte bloß, dass es gut rein passt wegen der map-funktion. Mir ist auch bewusst das man diese Anti-Pattern nicht verwenden sollte. Allerdings weiß ich bei meinem Beispiel keinen anderen Weg, da ich ja den Index i benötige. Um einmal auf norm_arr und auf new-nodes zu zugreifen. Geht das über enumerate eleganter?

Ich fand die folgende Präsentation sehr hilfreich als Einleitung beim Verstehen, was mit zip, enumerate, usw. alles möglich ist, und warum ich das benutzen will: http://nedbatchelder.com/text/iter.html

[schneitzmaster]

@Kebap: Die Präsi ist super danke!