基于Parallel Miller-Rabin算法的随机素数生成Python并行代码耗时过高问题
并行Miller Rabin素数校验性能不达标的问题分析与修复方案
核心问题原因
你的代码运行速度远低于预期,核心是四个严重的设计/逻辑错误:
- 进程创建开销远大于实际计算开销:每次调用
is_prime函数都要全新启动40个进程,进程创建、跨进程通信、上下文切换的开销远高于单次Miller Rabin轮次测试的计算量,尤其当校验的素数数值不大时,额外开销占比超过90%。 - 等待逻辑存在致命bug:你写的判断event的循环只执行一次就退出,相当于刚启动完40个进程立刻就检查事件状态,此时绝大多数测试进程还没跑完计算,你直接就返回了结果,不仅并行计算完全没生效,还残留了大量未回收的进程资源。
- 进程资源回收不完全:你只对最后一个创建的进程执行了
join和close,剩下39个进程全部变成僵尸进程,持续占用系统资源,调用次数多了之后系统负载会飙升,速度越来越慢。 - 并行粒度过细不合理:给每一轮Miller Rabin测试单独分配进程完全没有必要,进程数量超过CPU物理核心数之后,额外的上下文切换开销会进一步拉低性能。
优化方案
1. 调整并行粒度
不要在单次素数校验的内部开多进程,把并行逻辑移到上层:比如你要批量生成100个随机素数,把100个素数的校验任务拆分到多个进程处理,每个进程复用执行多个校验任务,进程只需要启动一次,大幅降低开销。
2. 使用进程池自动管理进程
用Python内置的concurrent.futures.ProcessPoolExecutor或者multiprocessing.Pool管理进程生命周期,不需要手动创建、终止、回收进程,避免手写逻辑的bug。
3. 修正后的实现示例
首先是单线程高效版Miller Rabin校验函数:
import random from concurrent.futures import ProcessPoolExecutor def is_prime_single(n, k=40): if n == 2 or n == 3: return True if n <= 1 or n % 2 == 0: return False s = 0 r = n - 1 while r & 1 == 0: s += 1 r //= 2 for _ in range(k): a = random.randrange(2, n - 1) v = pow(a, r, n) if v == 1: continue for __ in range(s): if v == n - 1: break v = (v ** 2) % n else: return False return True
然后是上层批量并行校验的实现,适合批量生成素数的场景:
def batch_prime_check(candidates, k=40): # 进程数默认和CPU核心数相等,避免过多进程的开销 with ProcessPoolExecutor() as executor: # 把每个候选素数的校验任务提交到进程池 results = executor.map(is_prime_single, candidates) # 返回素数列表 return [c for c, is_p in zip(candidates, results) if is_p]
4. 特殊场景优化:超大数校验内部并行
如果你要校验的是超大数(比如超过2048位),单轮Miller Rabin计算量足够大,才需要在单次校验内部并行,此时只需要启动和CPU核心数相等的进程,每个进程跑多轮测试,不要启动40个进程:
def is_prime_parallel_big_n(n, k=40): if n == 2 or n == 3: return True if n <= 1 or n % 2 == 0: return False s = 0 r = n - 1 while r & 1 == 0: s += 1 r //= 2 # 每轮测试的逻辑 def _test_round(_): a = random.randrange(2, n - 1) v = pow(a, r, n) if v == 1: return True for __ in range(s): if v == n - 1: return True v = (v ** 2) % n return False # 进程数和核心数一致 with ProcessPoolExecutor() as executor: results = list(executor.map(_test_round, range(k))) return all(results)
内容的提问来源于stack exchange,提问作者fanwer
相关产品推荐
相关产品推荐

