Python多线程加速Erdős-Rényi随机图生成失败求助

• GIL锁限制：Python的全局解释器锁（GIL）让同一时间只有一个线程能执行Python代码，你的Erdős-Rényi图生成属于CPU密集型任务（大量循环、随机数计算），用threading根本没法实现真正的并行，反而线程切换会额外消耗资源。
• 共享数据竞争：多个线程同时修改全局字典G里的列表，哪怕append是原子操作，频繁的共享访问也会触发GIL频繁切换，拖慢整体速度。

多进程有独立的内存空间和GIL，能真正利用多核CPU并行处理任务。下面是改好的代码：

import random
import multiprocessing
import time

n = 1000
p = 0.5
B = 5  # 进程数

def generator(start_i, end_i):
    # 每个进程单独生成负责的边集合，避免共享全局变量
    sub_edges = []
    for i in range(start_i, end_i):
        neighbors = []
        for j in range(i + 1, n):
            if random.random() > p:
                neighbors.append(j)
        sub_edges.append((i, neighbors))
    return sub_edges

if __name__ == "__main__":
    G = {k: [] for k in range(n)}
    start_time = time.time()
    
    # 拆分任务：每个进程处理n/B个节点的边
    chunk_size = n // B
    results = []
    
    # 用进程池管理进程
    with multiprocessing.Pool(processes=B) as pool:
        for a in range(B):
            start = a * chunk_size
            # 最后一个进程处理剩余节点
            end = (a + 1) * chunk_size if a != B-1 else n
            results.append(pool.apply_async(generator, args=(start, end)))
        
        # 收集所有进程结果，合并到全局图G中
        for res in results:
            sub_edges = res.get()
            for i, neighbors in sub_edges:
                G[i].extend(neighbors)
                for j in neighbors:
                    G[j].append(i)
    
    # print(G)  # 大节点数下打印耗时极长，建议注释掉
    end_time = time.time()
    print(f"耗时: {end_time - start_time:.2f} 秒")

• 避免全局共享数据：多进程间尽量通过返回值传递结果，减少共享内存的同步问题，像上面的代码那样每个进程生成子边集再合并就很稳妥。
• 使用更快的随机数工具：random模块速度一般，换成numpy批量生成随机数能进一步提速：

  import numpy as np
  
  def generator(start_i, end_i):
      sub_edges = []
      for i in range(start_i, end_i):
          # 批量生成随机数，一次性判断所有j的连接情况
          j_list = np.arange(i+1, n)
          connect_mask = np.random.rand(len(j_list)) > p
          neighbors = j_list[connect_mask].tolist()
          sub_edges.append((i, neighbors))
      return sub_edges
  

• 减少不必要的打印：原代码里print(G)在n=1000时会占用大量时间，测试时建议注释掉，只关注耗时即可。

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