Come velocizzare questo codice Python?

Question

Ho il seguente metodo Python piccolo che è di gran lunga le prestazioni hotspot (secondo il mio profiler,> 95% del tempo di esecuzione è trascorso qui) in un programma molto più grande:

def topScore(self, seq): 
    ret = -1e9999 
    logProbs = self.logProbs # save indirection 
    l = len(logProbs) 
    for i in xrange(len(seq) - l + 1): 
     score = 0.0 
     for j in xrange(l): 
      score += logProbs[j][seq[j + i]] 
     ret = max(ret, score) 

    return ret 

Il codice viene eseguito nell'implementazione Jython di Python, non in CPython, se questo è importante. seq è una stringa di sequenza del DNA, nell'ordine di 1.000 elementi. logProbs è un elenco di dizionari, uno per ogni posizione. L'obiettivo è trovare il punteggio massimo di qualsiasi lunghezza l (nell'ordine di 10-20 elementi) sottosuccessione di seq.

Mi rendo conto che tutto questo ciclo è inefficiente a causa di un sovraccarico di interpretazione e sarebbe molto più veloce in un linguaggio compilato staticamente/JIT. Tuttavia, non sono disposto a cambiare lingua. Innanzitutto, ho bisogno di un linguaggio JVM per le librerie che sto usando, e questo tipo di vincoli alle mie scelte. In secondo luogo, non voglio tradurre questo codice all'ingrosso in una lingua JVM di livello inferiore. Tuttavia, sono disposto a riscrivere questo hotspot in qualcos'altro, se necessario, anche se non ho idea di come interfacciarlo o quale sarebbe l'overhead.

In aggiunta alla lentezza a thread singolo di questo metodo, non riesco neanche a far sì che il programma scaletri molte 4 CPU in termini di parallelizzazione. Dato che trascorre quasi tutto il suo tempo nell'hotspot a 10 linee che ho pubblicato, non riesco a capire quale potrebbe essere il collo di bottiglia.

Answer 1

se topScore viene chiamato ripetutamente per lo stesso seq è possibile memoize il suo valore.

E.g. http://code.activestate.com/recipes/52201/

Answer 2

Niente salta come lento. Potrei riscrivere il ciclo interno in questo modo:

score = sum(logProbs[j][seq[j+i]] for j in xrange(l)) 

o anche:

seqmatch = zip(seq[i:i+l], logProbs) 
score = sum(posscores[base] for base, posscores in seqmatch) 

ma non so che o farebbe risparmiare molto tempo.

Potrebbe essere leggermente più veloce memorizzare le basi del DNA come numeri interi 0-3 e cercare i punteggi di una tupla anziché di un dizionario. Ci sarà un successo nelle prestazioni nella traduzione di lettere in numeri, ma ciò deve essere fatto una sola volta.

Answer 3

Il motivo è lento è perché è O (N * N)

La maximum subsequence algoritmo può aiutare a migliorare questa

Answer 4

Non ho idea di cosa sto facendo, ma forse questo può aiutare a velocizzare l'algo:

ret = -1e9999 
logProbs = self.logProbs # save indirection 
l = len(logProbs) 

scores = collections.defaultdict(int) 

for j in xrange(l): 
    prob = logProbs[j] 
    for i in xrange(len(seq) - l + 1): 
     scores[i] += prob[seq[j + i]] 


ret = max(ret, max(scores.values())) 

Answer 5

usano Decisamente NumPy e memorizzare logProbs come una matrice 2D, invece di un elenco di dizionari. Memorizza anche seq come array 1D di numeri interi (corti) come suggerito sopra. Ciò sarà di aiuto se non dovrai fare queste conversioni ogni volta che chiami la funzione (facendo queste conversioni all'interno della funzione non ti salverà molto). È possibile eliminare il secondo ciclo:

import numpy as np 
... 
print np.shape(self.logProbs) # (20, 4) 
print np.shape(seq) # (1000,) 
... 
def topScore(self, seq): 
ret = -1e9999 
logProbs = self.logProbs # save indirection 
l = len(logProbs) 
for i in xrange(len(seq) - l + 1): 
    score = np.sum(logProbs[:,seq[i:i+l]]) 
    ret = max(ret, score) 

return ret 

Cosa si fa dopo che dipende da quale di questi 2 elementi di dati cambia il più spesso:

Se logProbs rimane generalmente lo stesso e si desidera eseguire molti DNA sequenze attraverso di esso, quindi prendere in considerazione l'impilamento delle sequenze di DNA come un array 2D. numpy può scorrere l'array 2D molto rapidamente, quindi se hai 200 sequenze di DNA da elaborare, ci vorrà solo un po 'più di un singolo.

Infine, se hai davvero bisogno di accelerare, usa scipy.weave. Questo è un modo molto semplice per scrivere poche righe di C veloce per accelerare i loop. Tuttavia, consiglio scipy> 0.8.

Answer 6

E il precalcolo xrange(l) fuori dal ciclo i?

Answer 7

Si può cercare di sollevamento più di un semplice self.logProbs al di fuori dei cicli:

def topScore(self, seq): 
    ret = -1e9999 
    logProbs = self.logProbs # save indirection 
    l = len(logProbs) 
    lrange = range(l) 
    for i in xrange(len(seq) - l + 1): 
     score = 0.0 
     for j in lrange: 
      score += logProbs[j][seq[j + i]] 
     if score > ret: ret = score # avoid lookup and function call 

    return ret 

Answer 8

dubito che farà una differenza significativa, ma si potrebbe provare a cambiare:

for j in xrange(l): 
     score += logProbs[j][seq[j + i]] 

a

for j,lP in enumerate(logProbs): 
     score += lP[seq[j + i]] 

o anche il sollevamento di quell'elenco al di fuori del ciclo seq.