ZielLeistungssteigerung von Python-Funktion Cython
Ich versuche, mein Python-Programm mit Cython zu beschleunigen. Der Code, den ich schreibe, ist ein Versuch des Forward-Algorithmus, mit dem die Wahrscheinlichkeiten langer Sequenzen in einem Hidden-Markov-Modell (HMM) rekursiv und effizient berechnet werden. Dieses Problem wird normalerweise als Bewertungsproblem bezeichnet.
Python-Code
In einer Datei namens hmm.py
import numpy
import pandas
class HMM():
'''
args:
O:
observation sequence. A list of 'H's or 'T's
X:
state sequence. 'S','M' or 'L's
A:
transition matrix, N by N
B:
Emission matrix, M by N
M:
Number of possibilities in emission matrix
pi:
initial transition matrix
N:
Number of states
T:
length of the observation sequence
Q:
possible hidden states (Xs)
V:
possible observations (Os)
'''
def __init__(self,A,B,pi,O,X):
self.A=A
self.N=self.A.shape[0]
self.B=B
self.M=self.B.shape[1]
self.pi=pi
self.O=O
self.T=len(O)
self.Q=list(self.A.index)
self.V=list(self.B.keys())
self.X=X
def evaluate(self):
'''
Solve the evaluation problem for HMMs
by implementing the forward algorithm
'''
c0=0
ct=numpy.zeros(self.T)
alpha= numpy.zeros((self.T,self.N))
## compute alpha[0]
for i in range(self.N):
pi0=self.pi[self.Q[i]]
bi0=self.B.loc[self.Q[i]][self.O[0]]
alpha[0,i]=pi0*bi0
c0+=alpha[0,i]
ct[0]=alpha[0,i]
ct[0]=1/ct[0]#[0]
alpha=alpha*ct[0]
for t in range(1,self.T):
for i in range(self.N):
for j in range(self.N):
aji= self.A[self.Q[j]][self.Q[i]]
alpha[t,j]= alpha[t-1,j]*aji
ct[t]=ct[t]+alpha[t,i]
ct[t]=1/ct[t]
alpha=alpha*ct[t]
return (alpha,ct)
Dieser Code kann mit aufgerufen werden:
if __name__=='__main__':
A=[[0.7,0.3],[0.4,0.6]]
A= numpy.matrix(A)
A=pandas.DataFrame(A,columns=['H','C'],index=['H','C'])
'''
three types of emmission, small s, medium m and large l
'''
B=[[0.1,0.4,0.5],[0.7,0.2,0.1]]
B=numpy.matrix(B)
B=pandas.DataFrame(B,columns=['S','M','L'],index=['H','C'])
'''
initial probabilities for state, H and C
'''
pi=[0.6,0.4]
pi=numpy.matrix(pi)
pi=pandas.DataFrame(pi,columns=['H','C'])
O=(0,1,0,2)
O=('S','M','S','L')
X=('H','H','C','C')
H=HMM(A,B,pi,O,X)
print H.evaluate()
Wenn %timeit mit erhalte ich diese Ausgabe mit reinem Python
Compilation mit Cython
mich dann die evaluate Funktion (und nicht die ganze Klasse) in einer neuen Datei hmm.pyx Erweiterung:
import numpy
cimport numpy
cpdef evaluate_compiled(A,B,pi,O,X):
'''
Solve the evaluation problem for HMMs
by implementing the forward algorithm
'''
T=len(O)
N=len(list(set(X)))
Q=list(set(X))
V=list(set(O))
c0=0
ct=numpy.zeros(T)
alpha= numpy.zeros((T,N))
## compute alpha[0]
for i in range(N):
pi0=pi[Q[i]]
bi0=B.loc[Q[i]][O[0]]
alpha[0,i]=pi0*bi0
c0+=alpha[0,i]
ct[0]=alpha[0,i]
ct[0]=1/ct[0]#[0]
alpha=alpha*ct[0]
for t in range(1,T):
for i in range(N):
for j in range(N):
aji= A[Q[j]][Q[i]]
alpha[t,j]= alpha[t-1,j]*aji
ct[t]=ct[t]+alpha[t,i]
ct[t]=1/ct[t]
alpha=alpha*ct[t]
return (alpha,ct)
In setup.py:
try:
from setuptools import setup
from setuptools import Extension
except ImportError:
from distutils.core import setup
from distutils.extension import Extension
from Cython.Distutils import build_ext
import numpy
setup(cmdclass={'build_ext':build_ext},
ext_modules=[Extension('hmm',
sources=['HMMCluster/hmm.pyx'], #File is in a directory called HMMCluster
include_dirs=[numpy.get_include()])] )
Jetzt nach der Kompilierung kann ich Verwendung:
from hmm import evaluate_compiled
Und unter dem __main__ Block über die ich verwenden kann, Inplace von evaluate:
print evaluate_compiled(A,B,pi,O,X)
und mit %timeit:
Wie Sie sehen können, ohne Änderung der code habe ich eine ~ 3 fache verbesserung der geschwindigkeit. Alle Dokumente, die ich gelesen habe, weisen jedoch darauf hin, dass die mangelnde Geschwindigkeit in Python auf die dynamische Herleitung von Variablentypen zurückzuführen ist. Daher kann ich im Prinzip Variablentypen deklarieren und die Dinge weiter beschleunigen.
Cython mit Typdeklaration
nun die letzte Funktion zu diesem Beitrag ist, den gleichen Algorithmus wieder, aber mit Typdeklaration
cpdef evaluate_compiled_with_type_declaration(A,B,pi,O,X):
cdef int t,i,j
cdef int T = len(O)
cdef int N = len(list(set(X)))
cdef list Q = list(set(X))
cdef list V = list(set(O))
cdef float c0 = 0
# cdef numpy.ndarray ct = numpy.zeros(T,dtype=double) ## this caused compilation to fail
ct=numpy.zeros(T)
alpha= numpy.zeros((T,N))
for i in range(N):
pi0=pi[Q[i]]
bi0=B.loc[Q[i]][O[0]]
alpha[0,i]=pi0*bi0
c0+=alpha[0,i]
ct[0]=alpha[0,i]
ct[0]=1/ct[0]#[0]
alpha=alpha*ct[0]
for t in range(1,T):
for i in range(N):
for j in range(N):
aji= A[Q[j]][Q[i]]
alpha[t,j]= alpha[t-1,j]*aji
ct[t]=ct[t]+alpha[t,i]
ct[t]=1/ct[t]
alpha=alpha*ct[t]
return (alpha,ct)
Nach dem Übersetzen und% timeit i erhalten:
Wie Sie sehen können, haben die Typdeklarationen nicht gemacht weitere Verbesserungen der Code-Leistung. Meine Frage ist: Können weitere Verbesserungen an der Geschwindigkeit dieses Codes vorgenommen werden, und wenn ja, wie mache ich das?
bearbeiten folgende Vorschläge in den Kommentaren habe ich die zusätzlichen Typdeklarationen:
cdef float pi0,bi0
cdef numpy.ndarray[numpy.float64_t, ndim=1] ct
cdef numpy.ndarray[numpy.float64_t, ndim=2] aij,alpha
und habe diese von %timeit:
Also noch einmal, noch keine wirklichen speedups sogar mit deklarierenden Typen.
In der Zeile 'bi0 = B.loc [Q [i]] [O [0]]' vorgeschlagen, wie, Sie können "den Punkt vermeiden", wie hier beschrieben: https://wiki.python.org/moin/PythonSpeed/PerformanceTips. Allerdings bin ich bei der Analyse des zugrundeliegenden C-Codes von CPython keinesfalls stark. –
Ich würde versuchen, Typen für 'aji',' alpha' und 'ct' zu definieren, vielleicht so etwas wie' cdef numpy.darray [numpy.float64_t, ndim = 1] ... 'für eindimensionales Array. –
[Führen Sie den Befehl 'cython' aus (http://docs.cython.org/en/latest/src/reference/compilation.html), indem Sie die Option" -a "verwenden, und öffnen Sie das erstellte HTML-Dokument. Suchen Sie nach den gelben Linien, um zu sehen, wo der generierte Code nach wie vor möglicherweise langsame Python-Aufrufe oder -Objekte anstelle von geradlinigem C verwendet. –