Das Python eine interpreterbasierte Sprache ist, hat zwar viele Vorteile, aber leider auch ein paar Nachteil. Einer davon ist die Ausführungsgeschwindigkeit, die sich vor allem bei langen Schleifen und Berechnungen bemerkbar macht. Auf dieser Seite sollen an Hand des bereits bekannten Beispiels der Optimierung mittels des Monte-Carlo-Verfahrens verschiedene Methoden gezeigt werden, mit denen sich die Programmlaufzeit reduzieren lassen. Die Zeitmessungen wurden auf einem Desktop-PC mit i3-Prozessor durchgeführt.
Getestet wird einmal ein "reiner" Python-Ansatz, bei der die Berechnungen in einer Schleife ablaufen. Das Ergebnis wird dann verglichen mit einer Lösung, bei der die Schleife durch NumPy-Funktionen ersetzt wird. Anstatt die Schleife zu druchlaufen, wird das Problem quasi als Vektorrechnung betrachtet. Bei der dritten Methode, wird die zeitintensive Schleife zusammen mit den Berechnungen in zwei C++-Funktionen ausgelagert. Diese werden als DLL mittels Ctype in das Python-Programm eingebunden.
Um die Ausführungsgeschwindigkeit vergleichen zu können, werden für jede Variante die Zeit vom Funktionsaufruf bis zur Rückkehr gemessen. Um das Ergebnis nicht durch die CPU-Auslastung zu beeinflussen, wird dies mehrmals (200 mal) wiederholt und ein Mittelwert berechnet. Dieser wird in der Konsole zusammen mit den gefundenen Minimas ausgegeben. Auserdem werden die einzelnen Zeiten in Histogrammen dargestellt. Zur Kontrolle werden außerdem die gefundenen Punkte noch geplottet.
Rocking Wombat
# -*- coding: utf-8 -*-
"""
Created on Thu Aug 13 20:21:44 2015
@author: Sven
"""
import MonteCarloStandard as mcs
import MonteCarloNumpy as mcn
import MonteCarloCtypes as mcc
import numpy as np
from matplotlib import pyplot as plt
from mpl_toolkits.mplot3d import Axes3D
import time
# Daten für Schaubild erstellen
x = np.arange(-0.04, 0.04, 0.001)
y = np.arange(-0.04, 0.04, 0.001)
X,Y = np.meshgrid(x, y)
Z = mcs.ackley(X, Y)
python_time = []
numpy_time = []
ctypes_time = []
linksunten = [-2.0,-2.0]
rechtsoben = [2.0,2.0]
n = 500000
# Später mit 200 Durchgängen
for i in range(200):
start = time.time()
px,py,pz = mcs.montecarlo(linksunten, rechtsoben, n, func=mcs.ackley)
python_time.append(time.time()-start)
start = time.time()
npx,npy,npz = mcn.montecarlo(linksunten, rechtsoben, n, func=mcn.ackley)
numpy_time.append(time.time()-start)
start = time.time()
cpx, cpy, cpz = mcc.montecarlo(linksunten, rechtsoben, n)
ctypes_time.append(time.time()-start)
# Zeitdaten auswerten
n, bins, patches = plt.hist(python_time, 10, normed=0, facecolor='red', alpha=0.75)
plt.xlabel('Zeit in s')
plt.ylabel(u'Häufigkeit')
plt.title(r'Dauer Monte-Carlo-Suche nur mit Python')
plt.grid(True)
plt.show()
n, bins, patches = plt.hist(numpy_time, 10, normed=0, facecolor='blue', alpha=0.75)
plt.xlabel('Zeit in s')
plt.ylabel(u'Häufigkeit')
plt.title(r'Dauer Monte-Carlo-Suche mit Numpy')
plt.grid(True)
plt.show()
n, bins, patches = plt.hist(ctypes_time, 10, normed=0, facecolor='green', alpha=0.75)
plt.xlabel('Zeit in s')
plt.ylabel(u'Häufigkeit')
plt.title(r'Dauer Monte-Carlo-Suche mit Auslagerungen in C++')
plt.grid(True)
plt.show()
# Ergebnis ausgeben
print '--Auswertung------------------------------------------------------------'
print '----Schleife in Python--------------------------------------------------'
print 'Durchschnittliche Dauer: ',np.mean(python_time),'s'
print "Minimum bei: ",px,',',py,',',pz
print '\n'
print '----Berechnung ohne Schleife komplett mit Numpy-------------------------'
print 'Durchschnittliche Dauer: ',np.mean(numpy_time),'s'
print "Minimum bei: ",npx,',',npy,',',npz
print '\n'
print '----Berechnung mittels Auslagerung in C++-Funktionen--------------------'
print 'Durchschnittliche Dauer: ',np.mean(ctypes_time),'s'
print "Minimum bei: ",cpx,',',cpy,',',cpz
print '\n'
# Plotten
fig = plt.figure(figsize=(10, 7))
ax = fig.gca(projection='3d')
surf = ax.plot_wireframe(X, Y, Z, rstride=10, cstride=10, linewidth=0.5)
min_point1 = ax.scatter(px,py,pz,c=u'r', label="Python")
min_point2 = ax.scatter(npx,npy,npz,c=u'b', label="Numpy")
min_point3 = ax.scatter(cpx,cpy,cpz,c=u'g', label="Ctypes")
ax.set_title("Ackley-Funktion")
ax.set_xlabel("x")
ax.set_ylabel("y")
ax.set_zlabel("z")
plt.show()
Die Standard-Version ist identisch mit der Monte-Carlo-Suche aus dem Matlab-Python-Tutorial auf dieser Seite.
# -*- coding: utf-8 -*-
"""
Created on Mon Aug 17 19:16:19 2015
@author: Sven
"""
import numpy as np
def montecarlo(linksunten, rechtsoben, n, func):
'''Sucht Ackley-Funktion nach Minimum ab mittels Monte-Carlo-Verfahren'''
# Variablen für aktuelles Minimum
min_y = 0
min_x = 0
min_z = 0
# Suchgebiet
xu = linksunten[0]
yu = linksunten[1]
xo = rechtsoben[0]
yo = rechtsoben[1]
d_x = xo-xu
d_y = yo-yu
# Zufälligen xy-Koordinate im Suchgebiet erzeugen
point = [xu + d_x*np.random.rand(), yu + d_y*np.random.rand()]
min_x,min_y = np.meshgrid([point[0]],[point[1]])
# z-Koordinate berechnen
min_z = func(min_x,min_y)[0][0]
for i in range(n-1):
point = [xu + d_x*np.random.rand(), yu + d_y*np.random.rand()]
px,py = np.meshgrid([point[0]],[point[1]])
pz = func(px,py)[0][0]
# Testen ob ein neues Minimum gefunden wurde
if pz < min_z:
min_z = pz
min_x = px
min_y = py
return min_x[0][0],min_y[0][0],min_z
def ackley(x, y):
'''Ackley'''
a = -20 * np.exp(-0.2*np.sqrt((x**2 + y**2)/2))
b = -np.exp((np.cos(2*np.pi*x) + np.cos(2*np.pi*y))/2)
z = a + b + 20 + np.exp(1)
return z
NumPy bietet eine Reihe von Funktionen um mathematische Operationen auf Arrays, vergleichbar mit Vektoren, anzuwenden. Anstatt den Funktionswert für die erzeugten Zufallspunkte in einer Schleife Punkt für Punkt zu berechnen, werden zwei Vektoren mit x- und y-Punkten erzeugt und die Ackley-Funktion liefert einen Vektor mit der z-Komponente zurück. In diesem Vektor wird anschließend nach dem minimalsten Wert gesucht.
# -*- coding: utf-8 -*-
"""
Created on Mon Aug 17 19:16:53 2015
@author: Sven
"""
import numpy as np
def montecarlo(linksunten, rechtsoben, n, func):
'''Monte-Carlo ohne Schleife'''
# Suchgebiet
xu = linksunten[0]
yu = linksunten[1]
xo = rechtsoben[0]
yo = rechtsoben[1]
d_x = xo-xu
d_y = yo-yu
points = [np.add(xu, np.multiply(d_x,np.random.rand(n))) , np.add(yu, np.multiply(d_y,np.random.rand(n)))]
z = func(points[0], points[1])
minimum = np.min(z)
index = np.where(z==minimum)
return points[0][index],points[1][index],minimum
def ackley(x, y):
'''Ackley'''
a = np.multiply(-20, np.exp(np.multiply(-0.2 , np.sqrt( np.divide( np.add(np.power(x,2) ,np.power(y,2)), 2 ) ) ) ))
b = np.multiply(-1.0,np.exp( np.divide( np.add(np.cos(np.multiply(2*np.pi,x)), np.cos(np.multiply(2*np.pi,y) )),2)))
z = np.add(a,np.add(b, np.add(20, np.exp(1))))
return z
In der Ctypes-Variante findet die eigentliche Monte-Carlo-Suche im C-Code statt. Das Python-Skript lädt nur die DLL und wandelt die Python-Variablen in C-konforme Datentypen um.
# -*- coding: utf-8 -*-
"""
Created on Mon Aug 17 19:17:55 2015
@author: Sven
"""
import ctypes
def montecarlo(linksunten,rechtsoben,n_rand):
'''Monte-Carlo-Suche, die mittels ctypes auf C++-Funktionen zugreift'''
lib = ctypes.cdll.LoadLibrary('MonteCarloDLL.dll')
n = ctypes.c_int(n_rand)
lu = (ctypes.c_float*2)(linksunten[0],linksunten[1])
ro = (ctypes.c_float*2)(rechtsoben[0],rechtsoben[1])
MonteCarlo = lib.MonteCarlo
MonteCarlo.argtypes = ()
MonteCarlo.restype = ctypes.POINTER(ctypes.c_float)
result = MonteCarlo(lu,ro,n)
return result[0],result[1],result[2]
Die C++-Funktionen ähneln in ihrer Funktionsweise wieder der in Python implementierten Suche mittels Schleife.
// MonteCarloDLL.cpp : Definiert die exportierten Funktionen für die DLL-Anwendung.
//
#include "stdafx.h"
#include "MonteCarloDLL.h"
#include <cmath>
#include <cstdlib>
#include "time.h"
# define M_PI 3.14159265358979323846 /* pi */
namespace SearchFunc
{
/*Funktion berechnet aus zwei Float-Werten
den Rückgabewert für die Ackley-Funktion.*/
float ackley(float x, float y){
float z = 0;
float a = 0;
float b = 0;
a = -20 * exp(-0.2*sqrt((pow(x,2) + pow(y,2))/2));
b = -1 * exp((cos(2*M_PI*x) + cos(2*M_PI*y))/2);
z = a + b + 20.0 + exp(1);
return z;
}
float* MonteCarlo(float* linksunten, float* rechtsoben, int n){
srand ( (unsigned int) time(NULL) ); // Random-Funktion initialisieren
// Werte initalisieren
float x = linksunten[0] + ((float)(rand())) / (RAND_MAX / (rechtsoben[0] - linksunten[0]) + 1);
float y = linksunten[1] + ((float)(rand())) / (RAND_MAX / (rechtsoben[1] - linksunten[1]) + 1);
float z = ackley(x, y);
static float minimum[3] = {x,y,z}; // und ersten Punkt als erstes Minimum festlegen
for(int i = 0;i<n;i++){
// Zufallszahlen im Suchbereich erzeugen
x = linksunten[0] + ((float)(rand())) / (RAND_MAX / (rechtsoben[0] - linksunten[0]) + 1);
y = linksunten[1] + ((float)(rand())) / (RAND_MAX / (rechtsoben[1] - linksunten[1]) + 1);
z = ackley(x, y); // z-Komponente berechnen
// auf Minimum testen
if(z < minimum[2]){
minimum[0] = x;
minimum[1] = y;
minimum[2] = z;
}
}
return minimum;
}
}
In der Header-Datei müssen die Funktionen noch extern verfügbar gemacht werden.
// MonteCarloDLL.h
namespace SearchFunc
{
extern "C" __declspec(dllexport) float ackley(float x, float y);
// Gibt das Ergebnis der Monte-Carlo-Suche zurueck
extern "C" __declspec(dllexport) float* MonteCarlo(float* linksunten, float* rechtsoben, int n);
}
Das Ergebnis ist nicht besonderst überraschend. Die vollständig in Python programmierte Schleifen-Variante ist am langsamsten. Deutlich besser ist die auf NumPy aufbauende Variante. Aber auch die Auslagerung von Programmteilen in C++ bringt nochmal eine deutliche Verbesserung.
--Auswertung------------------------------------------------------------ ----Schleife in Python-------------------------------------------------- Durchschnittliche Dauer: 30.4260449982 s Minimum bei: -0.000816046443069 , 0.0005051505705 , 0.00273909395522 ----Berechnung ohne Schleife komplett mit Numpy------------------------- Durchschnittliche Dauer: 0.150134987831 s Minimum bei: [ 0.00188504] , [ 0.0007265] , 0.00582263871658 ----Berechnung mittels Auslagerung in C++-Funktionen-------------------- Durchschnittliche Dauer: 0.0626900136471 s Minimum bei: 0.00018310546875 , 0.00030517578125 , 0.00101002363954
Die Grafik unten zeigt den Zusammenhang zwischen der Ausführungszeit in Abhängigkeit von der Anzahl der ab zusuchenden Punkte. Die Zeit wurde immer über 20 Messungen gemittelt. Da parallel zur Messung am PC gearbeitet wurde, gibt es trotzdem einige Ausreiser. Die Tendenz eines linearen Zusammenhangs ist trotzdem deutlich zu erkennen.
Die Python-Skripte können zusammen mit der DLL, der dazugehörigen C++-Datei und Header-Datei als .zip-Datei runter geladen werden.