代码之家 › 专栏 › 技术社区 › dsimcha

如何加速这个Python代码?

jython jvm performance python java

dsimcha · 技术社区 · 14 年前

我有下面的小Python方法 到目前为止 性能热点(根据我的profiler,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 是一个DNA序列串,按1000个元素的顺序排列。 logProbs 是字典列表,每个位置一个。目标是找出任意长度的最大分数。 l (关于10-20个元素的顺序)子序列 顺序 .

我意识到由于解释开销,所有这些循环都是低效的,而且在静态编译/JIT语言中会快得多。不过,我不愿意换语言。首先,我使用的库需要一种JVM语言,这种语言限制了我的选择。其次,我不想把这些代码大规模地转换成低级的JVM语言。但是,如果需要的话,我愿意重写这个热点,尽管我不知道如何接口它,也不知道开销是多少。

除了这种方法的单线程缓慢性之外,我也无法让程序在并行化方面扩展到超过4个CPU。考虑到它几乎所有的时间都花在我发布的10行热点上,我不知道这里的瓶颈是什么。

8 回复 | 直到 14 年前

Rohan Monga 14 年前

如果 topScore 是为了同样的 seq 你可以 memoize 它的价值。

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

John La Rooy 14 年前

它之所以慢是因为它是O(N*N)

这个 maximum subsequence 算法可能有助于改进

cwallenpoole 14 年前

预计算呢 xrange(l) 在我的循环之外?

mouad 14 年前

我不知道我在做什么,但也许这有助于加快你的算法:

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

Thomas K 14 年前

没有什么能像慢动作那样跳出来。我可以这样重写内部循环:

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整数,并从元组而不是字典中查找分数可能会稍微快一些。把字母翻译成数字会有很大的效果,但这只需要做一次。

kiyo 14 年前

一定要使用numpy并将logProbs存储为一个2D数组,而不是一个字典列表。还将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通常保持不变,并且希望通过它运行许多DNA序列,那么可以考虑将DNA序列堆叠为2D数组。numpy可以很快地在2D数组中循环,所以如果你有200个DNA序列要处理,它只需要比单个序列稍长的时间。

最后,如果你真的需要加速,使用scipy.weave。这是写几行快速C来加速循环的一种非常简单的方法。但是,我建议使用scipy>0.8。

John Machin Santi 14 年前

你可以试着提升不止是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

Russell Borogove 14 年前

我怀疑这会有很大的不同,但你可以尝试改变:

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

到

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

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