如何加速这段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是一个DNA序列字符串，大约有1,000个元素。logProbs是一个字典列表，每个位置一个字典。目标是找到任何长度为l（大约10-20个元素）的子序列的最大分数。我意识到所有这些循环都由于解释开销而低效，并且在静态编译/JIT'd语言中会快得多。但是，我不想切换语言。首先，我需要一个JVM语言来使用我的库，这限制了我的选择。其次，我不想将此代码整体翻译成较低级别的JVM语言。但是，如果必要的话，我愿意在其他地方重写此热点，尽管我不知道如何接口它或开销会是什么。除了这种方法的单线程缓慢性外，我还无法在并行化方面使程序扩展到4个CPU以上。鉴于它几乎在我发布的10行热点中花费了所有时间，我无法弄清楚这里的瓶颈在哪里。

- dsimcha

---

我无法理解您正在使用的数据结构。您能否发布seq和logProbs的缩短样本？ - Katriel

我的第一反应是numpy，所以也许这个页面上的一些东西会有用：https://dev59.com/jnRC5IYBdhLWcg3wYP6h - Russell Borogove

@Russell：Jython中没有numpy，但我认为你应该能够访问Java的数字计算库。 - Katriel

@martineau: "logProbs 是一个字典列表..." - Fred Larson

@Fred Larson：抱歉，我的意思是将logProbs列表中的每个项目都变成一个列表而不是一个字典。我相信seq[index]可能只有很少的几个可能值。这将涉及到将每个可能的值逻辑映射到一个索引，但这可能比从序列哈希每个值以查找其是否为字典更快。 - martineau

Answer 1

它速度慢的原因是因为它是O(N*N)的。

最大子序列算法可能会帮助你改进这个问题。

- John La Rooy

---

这个问题和最大子序列有一点不同，正好导致提出的解决方案不能完全奏效。 - dsimcha

Answer 2

如果针对同一seq重复调用topScore，则可以使用memoize来缓存其值。

例如：http://code.activestate.com/recipes/52201/。

- Rohan Monga

---

虽然我希望从这篇文章中得到更多有见地的东西，但我会接受它，因为这就是我最终做的事情。 - dsimcha

那个示例基本上展示了如何编写一个装饰器，它可以捕获返回值并将其映射到输入。我想给你提供一段代码来实现这个功能，因为我总是喜欢使用别人的代码而不是自己写。 - Rohan Monga

Answer 3

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

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

- mouad

Answer 4

在 for i 循环之外预先计算 xrange(l) 怎么样？

- Wangnick

Answer 5

没有什么明显的缓慢。我可能会像这样重写内部循环：

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)

但我也不知道哪个会节省更多时间。

将DNA碱基存储为整数0-3，从元组中查找分数可能会稍微快一些，而不是从字典中查找。将字母转换为数字会影响性能，但这只需要做一次。

- Thomas K

---

如果精度很重要，可能需要使用 math.fsum()。 - martineau

Answer 6

一定要使用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通常保持不变，而你想运行许多DNA序列，那么考虑将你的DNA序列堆叠成一个2D数组。Numpy可以非常快速地循环遍历2D数组，因此如果你有200个DNA序列需要处理，它只需要比单个序列花费更少的时间。

最后，如果你真的需要加速，使用Scipy.weave。这是一种非常简单的方法，可以编写几行快速的C代码来加速你的循环。然而，我建议使用Scipy >0.8。

- kiyo

Answer 7

您可以尝试将除了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

- John Machin

Answer 8

我怀疑这不会有太大的影响，但你可以尝试更改：

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

到

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

或者甚至将该枚举提升到 seq 循环之外。

- Russell Borogove