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

Question

У меня есть следующий крошечный метод 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

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

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

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

Answer 1

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

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

Answer 2

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

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

Answer 3

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

Answer 4

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

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

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

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

на

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

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

Answer 6

Вы можете попробовать поднять больше, чем просто 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

Answer 7

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

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.

Answer 8

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

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 и искать результаты в кортеже, а не в словаре.Преобразование букв в цифры будет снижено, но это нужно сделать только один раз.