如何加速Python中字符串权重组合的生成与求和？

我有一个字符串，其中部分字符存在备选权重，示例如下：

• A（无权重选项）
• S [27.0, 0]
• D（无权重选项）
• S [27.0, 0]
• N [1.0, -20.0, 0]
• P（无权重选项）

以字符串ASDSNP为例，每个S对应权重27.0和0.0，每个N对应权重1.0、-20.0和0.0等。我需要为给定字符串生成所有权重组合并计算其总和，每个字符串会根据权重组合得到多个权重和，并将不同字符串及其权重和存入字典。

目前我从长字符串中按规则生成大量子串，通过以下代码计算权重和，但运行耗时极长，已通过限制最大组合数max_totalcomb=2来控制组合爆炸，求加速程序的方法。

import itertools as it
import time
start_time=time.time()

def generate_substr(seq=None):
    for f in range(1,len(seq)):
        for g in range(1,len(seq)):
            if g >f :
                yield seq[f:g]

def wt_combinator(anystr=None,max_totalcomb = 2):
    '''
    Returns sum of a list of combinatorial modification weights
    '''
    wt_list=[]
    
    anystr = anystr.upper()
    wt_sites=char_wt.keys()

    for va in anystr:
        if va in wt_sites:
           wt_list.append(char_wt[va])

    wt_combination=list(it.product(*wt_list))
    filtered_combination=[e for e in wt_combination if 0 <= sum([int(bool(x)) for x in e]) <= max_totalcomb ]
    sumwt_list=[sum(cmb) for cmb in filtered_combination]
    if len(sumwt_list):
        return sumwt_list
    else:
        return [0]


char_wt= {   'N': [1.0, -20.0, 0],
             'Q': [1.0, 0],
             'S': [27.0, 0],
             'T': [27.0, 0],
             'Y': [27.0, 0]}
my_string = "MQIFVKTLTGKTITLEVEPSDTIENVKAKIQDKEGIPPDQQRLIFAGKQLEDGRTLSDYNIQKESTLHLVLRLRGG"

str_db = dict()
dbcounter = 0

for fseq in generate_substr(my_string):
    swt = wt_combinator(fseq)
    for w in swt:
        str_db[dbcounter]={'seq':fseq,'sumw':w}
        dbcounter +=1


end_time=time.time()
print(end_time - start_time)
print(len(str_db))

1. 优化子串生成逻辑 #

原generate_substr函数中，g从1遍历到字符串长度再判断g>f，存在大量无效循环。直接让g从f+1开始遍历，省去多余判断：

def generate_substr(seq=None):
    seq_len = len(seq)
    for f in range(1, seq_len):
        # g直接从f+1起始，避免无效判断
        for g in range(f+1, seq_len):
            yield seq[f:g]

2. 避免全量组合生成，按需计算符合条件的权重和 #

原代码用it.product生成所有组合再过滤，是核心性能瓶颈。可以拆分权重选项，结合max_totalcomb限制直接生成有效组合：

# 预计算字符的非0权重和是否包含0选项
preprocessed_wt = {}
for char, wts in char_wt.items():
    non_zero = [w for w in wts if w != 0]
    has_zero = 0 in wts
    preprocessed_wt[char] = (non_zero, has_zero)

def wt_combinator(anystr=None, max_totalcomb=2):
    anystr = anystr.upper()
    non_zero_weights = []
    has_zero_list = []
    
    for char in anystr:
        data = preprocessed_wt.get(char)
        if not data:
            continue
        nz, has_zero = data
        non_zero_weights.append(nz)
        has_zero_list.append(has_zero)
    
    n = len(non_zero_weights)
    sumwt_list = []
    
    # 处理选0个非0权重的情况（所有可变字符都选0）
    if all(has_zero_list):
        sumwt_list.append(0.0)
    
    # 处理选1到max_totalcomb个非0权重的情况
    for k in range(1, min(max_totalcomb, n)+1):
        # 选择k个可变字符的位置
        for positions in it.combinations(range(n), k):
            # 未选中的位置必须能选0
            if all(has_zero_list[i] for i in range(n) if i not in positions):
                # 生成选中位置的非0权重组合
                selected = [non_zero_weights[i] for i in positions]
                for combo in it.product(*selected):
                    sumwt_list.append(sum(combo))
    
    # 去重减少重复存储（可选）
    sumwt_list = list(set(sumwt_list))
    return sumwt_list if sumwt_list else [0.0]

这种方式只生成符合max_totalcomb限制的组合，避免了全量组合的生成，能大幅降低计算量。

3. 优化存储结构 #

原代码用递增数字作为字典键存储每个(seq, sumw)对，可改用defaultdict将相同子串的权重和归类，减少字典操作开销：

from collections import defaultdict

str_db = defaultdict(list)
for fseq in generate_substr(my_string):
    swt = wt_combinator(fseq)
    str_db[fseq].extend(swt)

# 如需转换为原格式字典：
dbcounter = 0
final_db = {}
for seq, wts in str_db.items():
    for w in wts:
        final_db[dbcounter] = {'seq': seq, 'sumw': w}
        dbcounter += 1

4. 用生成器减少内存占用 #

在wt_combinator中改用生成器返回结果，避免一次性生成大列表占用内存，同时减少列表拷贝：

def wt_combinator(anystr=None, max_totalcomb=2):
    anystr = anystr.upper()
    non_zero_weights = []
    has_zero_list = []
    
    for char in anystr:
        data = preprocessed_wt.get(char)
        if not data:
            continue
        nz, has_zero = data
        non_zero_weights.append(nz)
        has_zero_list.append(has_zero)
    
    n = len(non_zero_weights)
    
    if all(has_zero_list):
        yield 0.0
    
    for k in range(1, min(max_totalcomb, n)+1):
        for positions in it.combinations(range(n), k):
            if all(has_zero_list[i] for i in range(n) if i not in positions):
                selected = [non_zero_weights[i] for i in positions]
                for combo in it.product(*selected):
                    yield sum(combo)

主循环中直接遍历生成器：

for fseq in generate_substr(my_string):
    for w in wt_combinator(fseq):
        str_db[dbcounter]={'seq':fseq,'sumw':w}
        dbcounter +=1

5. 并行处理（可选） #

如果子串数量极大，可使用多进程并行计算每个子串的权重和，适合子串计算成本较高的场景：

from concurrent.futures import ProcessPoolExecutor

def process_subseq(subseq):
    return (subseq, list(wt_combinator(subseq)))

str_db = {}
dbcounter = 0

with ProcessPoolExecutor() as executor:
    for subseq, swts in executor.map(process_subseq, generate_substr(my_string)):
        for w in swts:
            str_db[dbcounter] = {'seq': subseq, 'sumw': w}
            dbcounter +=1

内容的提问来源于stack exchange，提问作者The August