优化处理2^24元素布尔列表的多进程Python代码执行时间

核心性能瓶颈分析 #

原代码存在几个严重的性能损耗点：

• 无差别遍历所有2**24=16777216个元素，忽略了evaluated_f_bool_func_lst[y] == '0'的情况，这类项对求和结果无贡献，可以直接跳过
• 内层循环反复构造字符串、执行幂运算，没有做预计算缓存
• 多进程通信时传递完整的大列表，产生巨大的内存复制开销
• 字符串拼接方式低效，反复生成临时字符串对象
• 浮点数类型的chunk_size会导致遍历异常

具体优化措施 #

1. 跳过无效项计算 #

判断evaluated_f_bool_func_lst[y] == '0'时直接跳过当前y的所有计算，若列表中0占比高，这一步即可减少90%以上的计算量。

2. 预计算公共模板 #

提前生成所有(1+1*x[i])和(1+-1*x[i])的字符串，内层循环直接查表拼接，避免重复计算幂运算和字符串构造。

3. 优化多进程参数传递 #

只给子进程传递对应分片的列表切片，而非完整大列表，减少进程间通信开销。

4. 修正chunk_size类型，使用整数避免遍历错误 #

5. 可选：直接构造Sage符号表达式替代字符串拼接 #

如果后续是要在Sage中做符号计算，完全不需要生成字符串再转表达式，直接构造符号乘积和求和对象，效率提升至少一个数量级。

优化后代码示例 #

from sage.all import *
import time
from multiprocessing import Pool
import multiprocessing

# 预生成所有位对应的表达式模板
def precompute_expr_templates(dim):
    templates = []
    for i in range(dim):
        templates.append([f'(1+1*x[{i}])', f'(1+-1*x[{i}])'])
    return templates

def create_ext_component_function_i(args):
    dim, chunk_start, chunk_end, sub_f_list, templates = args
    sum_y_str = []
    # 子进程内的y是分片内的偏移，对应原列表的索引是chunk_start + offset
    for offset in range(chunk_end - chunk_start):
        f_val = sub_f_list[offset]
        if f_val == '0':
            continue
        y = chunk_start + offset
        prod_parts = []
        for i in range(dim):
            bit = (y >> i) & 1
            prod_parts.append(templates[i][bit])
        prod = '*'.join(prod_parts)
        sum_y_str.append(f'{prod}*{f_val}')
    return '+'.join(sum_y_str)

def create_ext_component_function(dim, evaluated_f_bool_func_lst, process_num=32):
    total = 2 ** dim
    chunk_size = total // process_num
    templates = precompute_expr_templates(dim)
    pool = Pool(process_num)
    tasks = []
    for i in range(process_num):
        chunk_start = i * chunk_size
        # 最后一个分片处理剩余的元素
        chunk_end = total if i == process_num - 1 else (i + 1) * chunk_size
        sub_f_list = evaluated_f_bool_func_lst[chunk_start:chunk_end]
        tasks.append((dim, chunk_start, chunk_end, sub_f_list, templates))
    join_results = pool.map(create_ext_component_function_i, tasks)
    pool.close()
    pool.join()
    full_expr = '+'.join(join_results)
    # 如果不需要打印完整表达式可以注释下面这行，打印超大规模字符串本身也会消耗大量时间
    print(full_expr)
    return full_expr

if __name__ == '__main__':
    evaluated_f_bool_func_lst = load("evaluated_f_bool_func_lst.obj")
    dim = 24
    start = time.time()
    create_ext_component_function(dim, evaluated_f_bool_func_lst)
    print(f"耗时: {time.time() - start}s")

额外优化建议 #

如果你的最终目的是得到Sage中的符号表达式而非输出字符串，可将子进程中的字符串拼接逻辑替换为直接构造符号乘积，避免字符串转表达式的额外开销：

# 子进程内逻辑修改示例
x = var('x', n=dim)
sum_expr = 0
for offset in range(chunk_end - chunk_start):
    f_val = int(sub_f_list[offset])
    if f_val == 0:
        continue
    y = chunk_start + offset
    prod = 1
    for i in range(dim):
        bit = (y >> i) & 1
        sign = -1 if bit else 1
        prod *= (1 - sign * x[i])
    sum_expr += prod * f_val
return sum_expr

这种方式可以完全规避字符串操作的开销，性能会有进一步提升。

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