Как ускорить этот код 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.

  • Самый быстрый способ фильтровать списки списков на основе третьего списка?
  • Сравнение: import statement vs __import__ function
  • Ошибка Apache Spark на этапе reduceByKey
  • Администратор Django меняет форму загрузки довольно медленно
  • Хранение объектов Python в списке Python по сравнению с массивом Numpy с фиксированной длиной
  • Python - ускорить преобразование категориальной переменной в ее числовой индекс
  • Быстро вычислить собственные векторы для каждого элемента массива в python
  • Оптимальный способ вычисления парной взаимной информации с использованием numpy
  •  
    Interesting Posts for Van-Lav

    Кодирование с плавающей запятой

    Существуют ли встроенные функции, блокирующие операции ввода-вывода, которые не позволяют запускать другие потоки?

    Как обрабатывать изображения в режиме реального времени и выводить видео в реальном времени результата?

    Как получить весь контент между двумя тегами xml в Python?

    Расстояние между массивами numpy, columnwise

    Как получить прозрачный фон в окне с PyGTK и PyCairo?

    Как я могу избежать преобразования python больших чисел в научную нотацию?

    Как рисовать сетку на сюжет в Python?

    Python Реализация шаблона проектирования пула объектов

    pexpect отправить перемещение курсора

    Файл CSV в SkFlow

    Шрифт awesome не загружается при использовании простого HTTP-сервера Python

    Когда использование точки с запятой в Python считается «хорошим» или «приемлемым»?

    Pandas: Как создать кадр данных случайных чисел?

    Какова максимальная длина имени атрибута в python?

    Python - лучший язык программирования в мире.