You need to enable JavaScript to run this app. 基于Parallel Miller-Rabin算法的随机素数生成Python并行代码耗时过高问题
优惠活动
大模型
产品
解决方案
定价
更多

基于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

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.10.15 18:45:01