我创建了一个函数max_points，它比较两个参数字符串，并返回与单独给定的标准相关的某个值，该标准涉及值ga,la,ldif和lgap的总和。它还返回达到这个特定值的字符串组合的列表。字符串s和t在各自的字谜中有最多n个间隙(在本例中，间隙是'_')。这里有一个函数应该返回的示例:
In [3]: max_points('AT_', 'A_T', 2, 5, 1, 0, 2)
Out[3]: (16, [['_A_T_', '_A_T_'],
['A__T_', 'A__T_'],
['A_T__', 'A_T__']])
我现在的代码是:
def max_points(s, t, ga, la, ldif, lgap, n = 1):
lst_s=generate_n_gaps(s, n)
lst_t=generate_n_gaps(t, n)
point_max=-9999
for i in lst_s:
for j in lst_t:
if len(i)==len(j):
point=pointage(i, j, ga, la, ldif, lgap)
if point>=point_max:
point_max=point
ultimate=[]
for i in lst_s:
for j in lst_t:
if len(i)==len(j) and pointage(i, j, ga, la, ldif, lgap)==point_max:
specific=[]
specific.append(i)
specific.append(j)
ultimate.append(specific)
return point_max, ultimate
其他函数generate_n_gaps和pointage(未显示)的工作原理如下:generate_n_gaps:返回参数字符串的所有组合的列表，最多有n个空格。pointage:只比较两个参数字符串s和t(不是它们的所有组合)，并返回一个与max_points函数符合相同条件的整数值。
您可以看到，如果参数字符串s和t的长度大于4或5，如果n大于2，则该函数最终输出相当多的列表。我怀疑这就是为什么某些输入需要超过2或3秒的时间。是否有任何方法可以使我的代码为这个特定的功能更快(<1秒的运行时)?或者问题可能出在使用的其他非指定函数上?
这里一个明显的问题是，您循环遍历所有i,j组合两次:一次计算最大值，然后第二次返回所有(i,j)组合达到这个最大值。
一次完成可能会更有效。比如:
point_max=-9999
# or better yet, -math.inf
ultimate=[]
for i in lst_s:
for j in lst_t:
if len(i)==len(j):
point=pointage(i, j, ga, la, ldif, lgap)
if point>point_max:
point_max=point
ultimate=[]
if point==point_max:
specific=[]
specific.append(i)
specific.append(j)
ultimate.append(specific)
这将使您的运行时间减少一半。
如果i和j有许多不同的可能长度，您也可以通过阻塞比较来实现节省。与其简单地遍历lstrong和lst_t，不如按长度拆分这些列表(使用按长度键的字典结构，每个值都是lstrong或具有该长度的lst_t的子集)。然后遍历所有可能的长度，只检查该长度的s值和t值。这需要更多的工作来设置，但可能有用，这取决于它为您节省了多少比较。
你还没有包括max_points的代码，但我会努力看看是否有任何可能的节省;您将会调用它很多次，所以您希望使它尽可能高效。
更高级的选项包括并行化，以及使用有关"分数"的特定信息。函数来更精确地阻塞你的分数调用。但先尝试简单的东西，看看是否能起作用。