如何加速Python字符串匹配cod

Question

{a1}如何精确地重建一个未知的输入区域。为了获得好的统计数据，我需要迭代多次，但是我当前的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和相同长度的{}的所有子列表之间的lc。有没有可能通过某种方式修改经典的动态规划LCS算法来做到这一点？在

Answer 1

当cd4{cd3}的最大值小于cd3}时，^{cd3}最多依赖于cd3}。在

如果你的程序只计算了一次表，这将是动态编程，而它目前不是。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()中进行一个表预计算，但是您在每个调用上构建了整个列表，然后将其丢弃。我并不是说我理解您试图实现的算法，但是您的编码方式也可以是：

1. 没有递归关系，因此没有DP优化的依据，或
2. 有一个递归关系，你的实现很失败。在