如何优化Python中max_points函数的运行效率使其耗时低于1秒

问题描述 #

我编写了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：返回输入字符串插入最多n个缺口后的所有组合列表
• pointage：仅比对传入的两个字符串，按照和max_points一致的计分规则返回整数分值

现存问题 #

当输入字符串s、t长度大于4或5，且n大于2时，函数会生成大量列表，部分输入场景下运行耗时超过2-3秒。需要优化该max_points函数的运行速度，使其耗时低于1秒，同时确认性能瓶颈是否可能出在上述两个未给出实现的依赖函数上。

优化思路 #

1. 瓶颈排查 #

两个未实现的依赖函数完全可能成为核心性能瓶颈，优先单独做基准测试：

• 对于generate_n_gaps：长度为L的字符串插入最多n个缺口，理论组合数为组合数C(L+n, n)量级，例如L=5、n=3时单字符串变体就有56种，两串做笛卡尔积就有3000+配对需要计算。如果该函数实现中存在重复生成变体、未过滤无效值的问题，会凭空增加数倍的计算量。
• 对于pointage：该函数属于高频调用函数，哪怕每次调用多1毫秒，几千次调用下来就会多花数秒。

另外当前代码本身存在两个明显的性能/逻辑问题：

• 同一对(i,j)会重复调用两次pointage：第一轮找最大值时算一次，第二轮收集结果时再算一次，直接把计分逻辑的耗时翻了一倍。
• 第一轮遍历存在逻辑bug：当len(i)!=len(j)时不会更新point变量，后续判断分值时会直接复用前一对字符串的计算结果，很容易算出错误的最高分值。

2. 低改造成本优化（无需更换核心算法） #

只需要调整现有遍历逻辑，不需要修改依赖函数，就能砍掉60%以上的耗时：

• 把两轮遍历合并为一轮：计算分值的同时就维护「分值-对应字符串对」的映射，不要重复计算分值，同时修复长度不等时的变量污染bug。
• 提前把两个变体列表按长度分组，遍历的时候只取长度匹配的变体做配对，砍掉所有长度不匹配的无效循环。
• 对生成的变体做去重，避免相同字符串重复计算分值。

优化后的参考实现：

from collections import defaultdict

def max_points(s, t, ga, la, ldif, lgap, n = 1):
    # 提前按长度分组，避免遍历中重复判断长度
    def group_by_len(lst):
        group = defaultdict(list)
        for item in lst:
            group[len(item)].append(item)
        # 去重，避免重复计算相同字符串
        for k in group:
            group[k] = list(set(group[k]))
        return group
    
    lst_s_group = group_by_len(generate_n_gaps(s, n))
    lst_t_group = group_by_len(generate_n_gaps(t, n))
    
    score_map = defaultdict(list)
    point_max = -9999
    
    for str_len, s_candidates in lst_s_group.items():
        # 只取相同长度的t变体做配对
        t_candidates = lst_t_group.get(str_len, [])
        if not t_candidates:
            continue
        for i in s_candidates:
            for j in t_candidates:
                current_score = pointage(i, j, ga, la, ldif, lgap)
                if current_score > point_max:
                    point_max = current_score
                score_map[current_score].append([i, j])
    
    return point_max, score_map[point_max]

3. 高性能方案（适配更长字符串、更大n的场景） #

如果调整完上述逻辑后，在n>3、字符串长度>6的场景下还是达不到耗时要求，就不要用「先生成所有缺口变体再暴力配对」的思路——这个思路的复杂度是指数级的，n越大性能下降越快。
这个场景本质是带gap罚分的双序列比对问题，直接用动态规划（DP）求解即可：

• DP状态定义为dp[i][j]表示s前i个字符、t前j个字符对齐时的最高分值，状态转移只需要考虑匹配、s插gap、t插gap三种情况，时间复杂度为O((len(s)+n)*(len(t)+n))，比暴力枚举的指数级复杂度低几个量级，n到10、字符串长度到20的时候也能毫秒级返回。
• DP填充完成后，通过回溯DP数组就能直接收集到所有达到最高分值的对齐组合，不需要枚举所有可能的缺口变体。

内容的提问来源于stack exchange，提问作者Nicholas Boscolo