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

У меня есть следующий крошечный метод Python, который на сегодняшний день является точкой доступа производительности (по моему профилировщику,> 95% времени выполнения здесь расходуется) в гораздо более крупной программе:

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 

Код запускается в реализации Jython Python, а не CPython, если это имеет значение. seq – последовательность последовательности ДНК, порядка 1000 элементов. logProbs – это список словарей, по одному для каждой позиции. Цель состоит в том, чтобы найти максимальный балл любой длины l (порядка 10-20 элементов) подпоследовательности seq .

Я понимаю, что этот цикл неэффективен из-за сложностей с интерпретацией и будет намного быстрее на статически скомпилированном / JIT'd языке. Однако я не хочу переключать языки. Во-первых, мне нужен язык JVM для библиотек, которые я использую, и этот вид ограничивает мои варианты. Во-вторых, я не хочу переводить этот код на более низкоуровневый JVM-язык. Тем не менее, я готов переписать эту точку доступа во что-то еще, если это необходимо, хотя я не знаю, как ее можно связать или что накладные расходы будут.

В дополнение к однопоточной медлительности этого метода, я также не могу заставить программу масштабировать более 4 процессоров с точки зрения распараллеливания. Учитывая, что он проводит почти все свое время в 10-строчной горячей точке, которую я разместил, я не могу понять, что может быть узким местом.

8 Solutions collect form web for “Как ускорить этот код 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.

  • Каков самый быстрый способ чтения данных из текстового файла и выделения его в фрейм данных?
  • Свяжите ATLAS / MKL с установленным Numpy
  • Почему буквальные форматированные строки настолько медленны в Python 3.6 alpha? (теперь фиксированная в 3.6 стабильной)
  • numpy на многоядерном оборудовании
  • Ускорение «for-loop» при анализе изображений при итерациях до 40 000
  • Ошибка Apache Spark на этапе reduceByKey
  • Где я могу найти сложность времени и пространства встроенных типов последовательностей в Python
  • Почему Django admin list_select_related не работает в этом случае?
  • Почему чтение нескольких файлов происходит в то же время медленнее, чем чтение последовательно?
  • Ajax v., Включая данные в HTML
  • Сокращение времени процессора для операторов if-elif
  • Python - лучший язык программирования в мире.