如何使用Python内存高效将带权边列表转换为对称邻接矩阵

首先明确前提：100000×100000的稠密邻接矩阵没有办法直接加载到普通机器内存中，哪怕使用单精度浮点数存储，总占用量为1e10 * 4字节 = 40GB，远超常规内存上限。因此核心优化思路是优先用稀疏存储格式，特殊场景下用磁盘内存映射替代内存加载。 #

步骤1：节点名转整数索引 #

首先要把字符串格式的节点名映射为连续的整数索引，方便后续矩阵寻址，10万节点的字典仅占用几MB内存，开销极低。

node_to_idx = dict()
idx = 0
rows = []
cols = []
data = []

# 逐行读取边列表文件，不要一次性加载整个大文件
with open("edge_list.txt", "r", encoding="utf-8") as f:
    for line in f:
        u, v, w = line.strip().split()
        w = float(w)
        # 给新出现的节点分配整数ID
        if u not in node_to_idx:
            node_to_idx[u] = idx
            idx += 1
        if v not in node_to_idx:
            node_to_idx[v] = idx
            idx += 1
        u_id = node_to_idx[u]
        v_id = node_to_idx[v]
        # 直接收集对称边的坐标和权重，不需要额外存储全部边列表
        rows.append(u_id)
        cols.append(v_id)
        data.append(w)
        rows.append(v_id)
        cols.append(u_id)
        data.append(w)

逐行读取的方式可以避免GB级边列表文件一次性加载到内存，内存开销仅和单条边的大小相关。 #

步骤2：生成稀疏邻接矩阵（内存最优方案） #

对于对称、绝大多数值为0的邻接矩阵，使用scipy的稀疏矩阵格式，内存开销仅和边数成正比：假设边数为100万条，总内存占用仅为20MB左右。

import scipy.sparse as sp

n_node = len(node_to_idx)
# 直接用COO格式构造稀疏矩阵，对角线默认全为0，无需额外赋值
adj_sparse = sp.coo_matrix((data, (rows, cols)), shape=(n_node, n_node)).tocsr()

如果需要进一步降低内存，可以只收集u_id < v_id的边，构造上三角稀疏矩阵后再对称补全，边存储的内存开销直接减半：

# 优化版：仅存上三角边，后续对称生成
for line in f:
    u, v, w = line.strip().split()
    w = float(w)
    # 省略节点编码逻辑...
    u_id, v_id = sorted([u_id, v_id])
    rows.append(u_id)
    cols.append(v_id)
    data.append(w)

# 构造上三角矩阵后补全对称
triu_adj = sp.coo_matrix((data, (rows, cols)), shape=(n_node, n_node))
adj_sparse = triu_adj + triu_adj.T

如果需要验证输出，针对示例的4节点边列表，调用adj_sparse.todense()即可得到对应的稠密矩阵结果：

matrix([[0, 1, 2, 0],
        [1, 0, 0, 0],
        [2, 0, 0, 3],
        [0, 0, 3, 0]], dtype=float32)

特殊场景：必须使用稠密矩阵的处理方式 #

如果下游逻辑要求必须输入稠密矩阵，可以使用numpy的内存映射机制，把矩阵存储在磁盘上，通过虚拟寻址访问，不会占用运行内存：

import numpy as np

n_node = len(node_to_idx)
# 创建磁盘内存映射数组，初始值全为0
adj_dense = np.memmap("adj_matrix.npy", dtype="float32", mode="w+", shape=(n_node, n_node))
# 逐批写入边权重，避免单次写入过多数据占内存
batch_size = 10000
for i in range(0, len(rows), batch_size):
    batch_rows = rows[i:i+batch_size]
    batch_cols = cols[i:i+batch_size]
    batch_data = data[i:i+batch_size]
    adj_dense[batch_rows, batch_cols] = batch_data
# 把修改刷入磁盘
adj_dense.flush()

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