我有这段代码可以计算 Longest Common Subsequence在随机字符串之间进行测试,以了解重建输入的未知区域的准确程度。为了获得良好的统计数据,我需要多次迭代它,但我当前的 python 实现太慢了。即使使用 pypy目前运行一次需要 21 秒,理想情况下我希望运行它 100 次。
#!/usr/bin/python
import random
import itertools
#test to see how many different unknowns are compatible with a set of LCS answers.
def lcs(x, y):
n = len(x)
m = len(y)
# table is the dynamic programming table
table = [list(itertools.repeat(0, n+1)) for _ in xrange(m+1)]
for i in range(n+1): # i=0,1,...,n
for j in range(m+1): # j=0,1,...,m
if i == 0 or j == 0:
table[i][j] = 0
elif x[i-1] == y[j-1]:
table[i][j] = table[i-1][j-1] + 1
else:
table[i][j] = max(table[i-1][j], table[i][j-1])
# Now, table[n, m] is the length of LCS of x and y.
return table[n][m]
def lcses(pattern, text):
return [lcs(pattern, text[i:i+2*l]) for i in xrange(0,l)]
l = 15
#Create the pattern
pattern = [random.choice('01') for i in xrange(2*l)]
#create text start and end and unknown.
start = [random.choice('01') for i in xrange(l)]
end = [random.choice('01') for i in xrange(l)]
unknown = [random.choice('01') for i in xrange(l)]
lcslist= lcses(pattern, start+unknown+end)
count = 0
for test in itertools.product('01',repeat = l):
test=list(test)
testlist = lcses(pattern, start+test+end)
if (testlist == lcslist):
count += 1
print count
我尝试将它转换为 numpy,但我一定做得不好,因为它实际上运行得更慢。这段代码能否以某种方式加速很多?
更新。在下面的评论之后,如果 lcses
直接使用递归会更好,它在 pattern
和所有子列表之间给出 LCS相同长度的 text
。是否可以通过某种方式修改经典的动态规划 LCS 算法来做到这一点?
最佳答案
递归表 table
在每次调用 lcses()
时被重新计算 15 次,而它仅依赖于 m
和 n
其中 m
的最大值为 2*l
而 n
最多为 3*l
.
如果您的程序只计算一次表,则它是动态规划,但目前不是。 Python 的习惯用法是
table = None
def use_lcs_table(m, n, l):
global table
if table is None:
table = lcs(2*l, 3*l)
return table[m][n]
除了使用类实例比全局表声明更清晰和更具可扩展性。但这让您了解为什么要花这么多时间。
在评论回复中添加:
动态编程是一种优化,需要以额外的空间换取更少的时间。在您的示例中,您似乎在 lcs()
中进行了表预计算,但您在每次调用时都构建了整个列表,然后将其丢弃。我不声称了解您要实现的算法,但您的编码方式是:
- 没有递归关系,因此没有理由进行 DP 优化,或者
- 有递归关系,但你搞砸了。
关于python - 如何加速Python字符串匹配代码,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/17381758/