分治法实现累积和：多进程为何更慢？如何优化？

我用分治法计算列表累积和，输入[1,2,3,4,5]输出[1,3,6,10,15]。尝试用ProcessPoolExecutor实现多进程提速，但结果显示多进程比单进程更慢。请解释原因，并指导如何用纯Python分治法（不依赖第三方库）优化多进程代码，使其快于单进程。

原单进程核心代码：

def cum_sum_dac(lst,new_lst,count):
    if len(lst)==1:
        n=lst[0]
        new_lst[n-1]=(n*(n+1)/2)
    else:
        count[0]+=1
        mid=len(lst)//2
        first_half=lst[:mid]
        second_half=lst[mid:]
        cum_sum_dac(first_half,new_lst,count)
        cum_sum_dac(second_half,new_lst, count)

原多进程核心代码：

def cum_sum_dac_multi(lst,new_lst,count):
    if len(lst)==1:
        n=lst[0]
        new_lst[n-1]=(n*(n+1)/2)
    else:
        count[0]+=1
        mid=len(lst)//2
        first_half=lst[:mid]
        second_half=lst[mid:]
        if count[0]<4:
            with Pool(2) as pool:
                pool.map(cum_sum_dac_multi,[first_half, second_half],[new_lst,new_lst],[count, count])
        else:
            cum_sum_dac_multi(first_half,new_lst,count)
            cum_sum_dac_multi(second_half,new_lst, count)

1. 进程池频繁创建销毁：每次递归满足条件时都用with Pool(2)创建新进程池，进程启动、初始化、销毁的开销远大于并行计算带来的收益。
2. 共享数据的IPC开销：使用mp.Manager().list作为共享列表，进程间修改该列表需要跨进程通信（IPC），比操作本地内存慢几个数量级，直接抵消并行优势。
3. 任务粒度不合理：分治早期的子任务计算量极小，多进程的调度、参数传递成本远高于计算本身，完全没必要并行。
4. 参数传递逻辑错误：pool.map仅支持单参数函数，你传递多个列表的方式会导致每个子进程仅拿到单个参数（比如第一个进程拿到first_half，第二个拿到second_half，new_lst和count根本没正确传递），逻辑出错的同时还增加了无效通信成本。

核心思路：

• 全局仅创建一次进程池，避免重复初始化开销
• 子进程返回计算结果，最后合并，彻底消除共享数据的IPC开销
• 控制并行粒度，仅当子任务规模足够大时才用多进程，小任务用单进程递归

优化代码：

from concurrent.futures import ProcessPoolExecutor
import time

def single_process_dac(lst):
    """单进程分治计算累积和"""
    if len(lst) == 1:
        n = lst[0]
        return [n * (n + 1) // 2]
    mid = len(lst) // 2
    left = single_process_dac(lst[:mid])
    right = single_process_dac(lst[mid:])
    return left + right

def multi_process_dac(lst, pool, min_size=10000):
    """多进程分治计算累积和，仅当任务规模大于min_size时才并行"""
    if len(lst) <= min_size:
        return single_process_dac(lst)
    mid = len(lst) // 2
    # 异步提交两个子任务并行执行
    future_left = pool.submit(multi_process_dac, lst[:mid], pool, min_size)
    future_right = pool.submit(multi_process_dac, lst[mid:], pool, min_size)
    # 获取结果并合并
    left = future_left.result()
    right = future_right.result()
    return left + right

if __name__ == '__main__':
    # 测试数据
    a = list(range(1, 100000))
    
    # 多进程测试
    st = time.process_time()
    with ProcessPoolExecutor() as pool:
        cum_list_multi = multi_process_dac(a, pool)
    et = time.process_time()
    res_multi = et - st
    print(f"多进程CPU执行时间: {res_multi * 1000:.2f} 毫秒")
    
    # 单进程测试
    st = time.process_time()
    cum_list_single = single_process_dac(a)
    et = time.process_time()
    res_single = et - st
    print(f"单进程CPU执行时间: {res_single * 1000:.2f} 毫秒")
    
    # 验证结果一致性
    assert cum_list_multi == cum_list_single
    print(f"多进程比单进程快 {(res_single - res_multi) * 1000:.2f} 毫秒")

1. 进程池复用：在主函数中创建一次ProcessPoolExecutor，整个递归过程复用该池，避免重复创建进程的开销。
2. 无共享数据设计：每个子进程独立计算区间结果，通过返回值合并，完全不需要跨进程修改共享列表，消除IPC开销。
3. 合理并行粒度：设置min_size阈值（示例为10000），仅当子任务规模超过阈值时才用多进程，小任务用单进程递归，避免无意义的并行开销。
4. 正确参数传递：用pool.submit传递完整参数，确保子进程能正确接收所有需要的参数，逻辑正确。

内容的提问来源于stack exchange，提问作者Dinh Quang Tuan