如何加速这段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

这段代码是在Jython这个Python的实现上运行的，不是CPython。如果这有影响的话。seq是一个大约有1000个元素的DNA序列字符串。logProbs是一个字典列表，每个字典对应序列中的一个位置。我们的目标是找到任意长度为l（大约10到20个元素）的子序列在seq中的最大得分。

我意识到这些循环效率很低，因为解释执行的开销很大，如果用一种静态编译的语言或者JIT编译的语言来写会快很多。不过，我不想换语言。首先，我需要一个JVM语言来使用我正在用的库，这限制了我的选择。其次，我不想把这段代码完全翻译成一种更底层的JVM语言。不过，如果有必要，我愿意用其他语言重写这个性能差的部分，只是我不知道怎么去连接它，或者这样做会带来什么开销。

除了这个方法单线程运行很慢之外，我还无法让程序在并行处理上扩展到超过4个CPU。考虑到它几乎所有的时间都花在我贴出的那10行代码上，我搞不清楚这里的瓶颈可能是什么。

Answer 1

我不知道自己在做什么，但也许这可以帮助你加快算法的速度：

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 2

之所以慢，是因为它的复杂度是O(N*N)，也就是说，随着数据量的增加，处理的时间会迅速变长。

你可以看看这个最大子序列算法，它可能会帮助你提高效率。

Answer 3

如果你对同一个 seq 多次调用 topScore，你可以把它的值存起来，这个过程叫做 memoize。

比如说，参考这个链接：http://code.activestate.com/recipes/52201/