Как ускорить этот код Python?

если topScore вызывается повторно для одного и того же seq вы можете memoize его значение.

Например: http://code.activestate.com/recipes/52201/

Причина, по которой она медленная, состоит в том, что она O (N * N)

Максимальный алгоритм подпоследовательности может помочь вам улучшить это

Как насчет предварительного xrange(l) вне цикла for i?

я не знаю, что я делаю, но, возможно, это поможет ускорить ваш алгоритм:

 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())) 

Ничто не выпрыгивает, как медленное. Я мог бы переписать внутренний цикл следующим образом:

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

или даже:

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

но я не знаю, что это сэкономит много времени.

Возможно, было бы немного быстрее хранить базы ДНК в виде целых чисел 0-3 и искать оценки из кортежа вместо словаря. Будет нанесен удар по переводу букв на цифры, но это нужно сделать только один раз.

Определенно используйте numpy и храните logProbs как 2D-массив, а не список словарей. Также сохраните seq как 1D массив (коротких) целых чисел, как было предложено выше. Это поможет, если вам не нужно делать эти преобразования каждый раз, когда вы вызываете функцию (выполнение этих преобразований внутри функции не позволит вам значительно сэкономить). Вы можете устранить второй цикл:

 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 

То, что вы делаете после этого, зависит от того, какой из этих двух элементов данных изменяется наиболее часто:

Если logProbs обычно остается неизменным, и вы хотите запустить через него много последовательностей ДНК, тогда рассмотрите возможность укладки ваших последовательностей ДНК в виде 2D-массива. numpy может быстро проходить через 2D-массив, поэтому, если у вас есть 200 последовательностей ДНК, это займет немного больше времени, чем один.

Наконец, если вам действительно нужно ускорить работу, используйте scipy.weave. Это очень простой способ написать несколько строк быстрого C, чтобы ускорить цикл. Тем не менее, я рекомендую scipy> 0.8.

Вы можете попробовать поднять больше, чем просто self.logProbs вне петель:

 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 

Я сомневаюсь, что это будет иметь существенное значение, но вы можете попробовать изменить:

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

в

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

или даже поднимать это перечисление вне цикла seq.