¿Cómo acelerar este código Python?

Tengo el siguiente pequeño método de Python que es, con mucho, el punto de acceso de rendimiento (según mi generador de perfiles,> 95% del tiempo de ejecución se gasta aquí) en un progtwig mucho más 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 

El código se está ejecutando en la implementación Jython de Python, no CPython, si eso importa. seq es una cadena de secuencia de ADN, del orden de 1.000 elementos. logProbs es una lista de diccionarios, uno para cada posición. El objective es encontrar la puntuación máxima de cualquier longitud l (en el orden de 10-20 elementos) subsecuencia de seq .

Me doy cuenta de que todo este bucle es ineficiente debido a la sobrecarga de interpretación y sería mucho más rápido en un lenguaje estáticamente comstackdo / JIT. Sin embargo, no estoy dispuesto a cambiar de idioma. Primero, necesito un lenguaje JVM para las bibliotecas que estoy usando, y este tipo de restricciones restringe mis elecciones. En segundo lugar, no quiero traducir este código al por mayor a un lenguaje JVM de nivel inferior. Sin embargo, estoy dispuesto a volver a escribir este punto de acceso en otra cosa si es necesario, aunque no tengo idea de cómo conectarlo o cuál sería la sobrecarga.

Además de la lentitud de este método de un solo hilo, tampoco puedo hacer que el progtwig escale mucho más allá de 4 CPU en términos de paralelización. Dado que pasa casi todo el tiempo en el punto de acceso de 10 líneas que he publicado, no puedo averiguar cuál podría ser el cuello de botella aquí.

Si se llama repetidamente a topScore para la misma memoize podría memoize su valor.

Por ejemplo, http://code.activestate.com/recipes/52201/

La razón por la que es lento es porque es O (N * N)

El algoritmo de subsecuencia máxima puede ayudarte a mejorar esto.

¿Qué hay de precomputar xrange(l) fuera del bucle for i?

No tengo ni idea de lo que estoy haciendo, pero tal vez esto pueda ayudar a acelerar 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())) 

Nada salta como si fuera lento. Podría reescribir el bucle interno de esta manera:

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

o incluso:

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

Pero tampoco sé que eso ahorraría mucho tiempo.

Podría ser un poco más rápido almacenar las bases de ADN como números enteros 0-3, y buscar las puntuaciones de una tupla en lugar de un diccionario. Habrá un impacto en la interpretación de la traducción de letras a números, pero eso solo debe hacerse una vez.

Definitivamente use numpy y almacene logProbs como una matriz 2D en lugar de una lista de diccionarios. También almacene seq como una matriz 1D de enteros (cortos) como se sugirió anteriormente. Esto ayudará si no tiene que hacer estas conversiones cada vez que llama a la función (hacer estas conversiones dentro de la función no le ahorrará mucho). Puedes eliminarlos del segundo bucle:

 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 

Lo que haga después de eso depende de cuál de estos 2 elementos de datos cambia con más frecuencia:

Si logProbs generalmente permanece igual y desea ejecutar muchas secuencias de ADN a través de él, entonces considere astackr sus secuencias de ADN como una matriz 2D. Numpy puede recorrer la matriz 2D muy rápidamente, por lo que si tiene que procesar 200 secuencias de ADN, solo tomará un poco más de tiempo que una sola.

Finalmente, si realmente necesitas acelerar, usa scipy.weave. Esta es una forma muy fácil de escribir unas pocas líneas de C rápida para acelerar tus bucles. Sin embargo, recomiendo scipy> 0.8.

Puedes intentar levantar más que solo self.logProbs fuera de los bucles:

 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 

Dudo que haga una diferencia significativa, pero podrías intentar cambiar:

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

a

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

o incluso levantar esa enumeración fuera del bucle de secuencia.