Hilfe meine Funktion ist zu langsam.

[lukus]

Hallo,

ich brauch Hilfe für die Performance einer Funktion. Es werden 2 Arrays (1024x1024 Pixeln) miteinander verglichen und dann für jedes Pixel des einen Arrays ein Abweichungsarray erstellt und von diesem dann der Minimum-Wert genommen.

A1 und A2 sind die Arrays

Hier der Code:

Code: Alles auswählen

size1=A1.shape
size2=A2.shape
AbwSignalProzent=2
DTA=5
dosed = AbwSignalProzent *  A1[:,:].max()/100
G=np.zeros (size1) 
Ga=np.zeros (size1)
x=np.arange(1024)
y=np.arange(1024)
if size1 == size2:
    for i in range(0,size1[0]):        
        for j in range(0,size1[1]):

           # PixelAbstand im Quadrat als ARRAY
            r2 = (x[:,None] - x[i])**2 + (y[None,:]-y[j])**2
            # Pixelwertunterschied im Quadrat als ARRAY
            d2 =(int(A1[i , j]) - A2.astype(np.int))**2 ;#difference squared
            Ga =r2 / (float(DTA)**2) + d2/ (float(dosed)**2)
            G[i,j]=sqrt(Ga.min())

Es funktioniert gut. Nur ist es extrem langsam. Hat von euch jemand eine Idee zur Beschleunigung?

Vielen Dank und Gruß,

Lukas

[snafu]

@lukus: Du benutzt ja bereits richtigerweise Numpy. Warum machst du dann Vektor-Operationen mittels ``for``-Schleifen? Python selbst ist in solchen Dingen leider nicht wirklich gut. Dafür bietet Numpy aber entsprechende Möglichkeiten an, um ``for``-Schleifen durch den Aufruf von Numpy-Funktionen zu ersetzen, dessen Ausführung dann nämlich in schnellem C-Code umgesetzt wird. Das bringt dann in aller Regel deutlich spürbare Vorteile, was die Ausführungsgeschwindigkeit eines solchen Programms angeht.

[MagBen]

Das Stichwort ist Vektorisieren.
Für r2 geht das z.B. folgendermaßen:

Code: Alles auswählen

import numpy as np

n = 1024

x=np.arange(n)
y=np.arange(n)

x_b = x.repeat(n).reshape(n,n)
y_b = y.repeat(n).reshape(n,n)

x_abstand = (x-x_b)**2
y_abstand = (y-y_b)**2

for i in range(n):
    for j in range(n):
        # PixelAbstand im Quadrat als ARRAY
        r2_a = (x - x[i])**2 + (y-y[j])**2
        r2_b = x_abstand[i] + y_abstand[j]
        np.testing.assert_array_equal(r2_a, r2_b)

x[:,None] ist das gleiche wie x[:] ist das gleiche wie x

Die X- und Y-Abstände werden nicht in der Python-Schleife berechnet, sondern in Zeile 11 und 12. Fürs Testing habe ich aber noch die alte Variante in der Schleife gelassen, in Zeile 19 teste ich, dass die Vektorisierte Form das gleiche liefert, wie die ursprüngliche Schleifenimplementation. Wenn man als Prototyp eine Schleifenimplementation hat und diese dann vektorisiert, ist es immer nützlich zu testen, ob das Ergebnis noch stimmt. Wenn die vektorisierte Implementation dann stimmt, dann kann man den alten Code natürlich löschen.

r_2b wird immer noch in einer Schleife berechnet, aber wesentlich schneller als r2_a. Wollte man die Berechnung von r2b vollständig vektorisieren, dann wäre r2_b ein n x n x n Array, bei n=1024 also 4 oder 8 GB.

In der Art kannst Du nun auch die Berechnung von d2, Ga und G vollständig oder teilweise vektorisieren. Insbesondere A2.astype(np.int)) ist eine Katastrophe. In jedem Schleifendurchlauf wird die komplette Matrix zu einer Int-Matrix umgewandelt. Das müsste blos 1 mal passieren, anstatt size1[0] x size1[1] mal.

[lukus]

Hallo, vielen Dank für die Tipps. Ich werde sie heute ausprobieren.

@ MagBen: Die Katastrophe mit dem A2.astype(np.int)) kann ich ir gut vorstellen. Das kann ich aus der Schleife ziehen. Aber wäre es mit einem n x n x n Array noch mal deutlich schneller?

@ snafu: Ich habe ja schon probier mit den Array zu arbeiten, bin aber noch nicht auf die Lösung gekommen die beiden Schleifen weg zu lassen. Hast du eine Idee wie ich die for-Schleifen mittels Numpy Funktionen ersetzen kann.

Vielen Dank,

Lukas

[MagBen]

Die Katastrophe mit dem A2.astype(np.int)) kann ich ir gut vorstellen.

Ich schätze 500 Sekunden extra:
Es sind 1 Mio Float die zu Int umgewandelt werden müssen, der Rechner hat 3 GHz, aber sagen wir mal er nutzt nur 2 GHz für die Umwandlung, das macht dann 1/2000 Sekunde. Nun machst Du das aber nicht 1 mal, sondern 1000 x 1000 mal, das macht dann 500 Sekunden. Das sind alles aber nur Überschlagsrechnungen, es kommt dabei nicht auf den exakten Zahlenwert an, sondern nur auf die Größenordnung.

Aber wäre es mit einem n x n x n Array noch mal deutlich schneller?

Wahrscheinlich schon, aber denk an den Speicher. Probier eine Optimierung nach der anderen aus und schreib Dir die Laufzeiten auf. Eine gute Optimierung bringt 50% bis 90% weniger Rechenzeit. Der absolute Gewinn wird aber von Optimierung zu Optimierung immer weniger und irgendwann lohnt sich der Arbeitsaufwand nicht mehr. Wenn Du z.B. anstatt zwei verschachtelter Schleifen nur noch eine hättest, dann hättest Du schon 99.9% aller Python Schleifendurchläufe reduziert. Lohnt sich danach noch der Arbeitsaufwand um die restlichen 0.1% Python-Schleifendurchläufe vollständig zu eliminieren?