如何快速从百万行文件中查找关联Net？Python性能优化问询

原代码的核心性能问题在于每次搜索一个Net都要重新打开并遍历整个文件，如果有500个关联Net，就会重复读取500次百万行的文件，这是导致总耗时过长的根本原因。

优化思路 #

先一次性读取文件，构建Net的邻接表（字典），把每个Net对应的所有关联Net存储在内存中，之后的关联查找只需要在内存中做图遍历（BFS/DFS），不需要再重复读取文件。

优化后的代码实现 #

def build_net_adjacency(file_path):
    adjacency = {}
    with open(file_path, 'r') as fi:
        for line in fi:
            line = line.strip()
            if not line or line[0].lower() != 'r':
                continue
            parts = line.split()
            if len(parts) < 3:
                continue  # 跳过格式错误的行
            rname, net1, net2 = parts[0], parts[1].lower(), parts[2].lower()
            # 双向添加关联关系
            if net1 not in adjacency:
                adjacency[net1] = set()
            adjacency[net1].add(net2)
            if net2 not in adjacency:
                adjacency[net2] = set()
            adjacency[net2].add(net1)
    return adjacency

def get_nets(net, adjacency):
    target_net = net.lower()
    if target_net not in adjacency:
        return {target_net}
    
    related_nets = set()
    unsearched = [target_net]
    
    while unsearched:
        current_net = unsearched.pop()
        if current_net in related_nets:
            continue
        related_nets.add(current_net)
        # 添加所有未搜索过的关联Net
        unsearched.extend(adj for adj in adjacency[current_net] if adj not in related_nets)
    
    return related_nets

# 使用示例
# 先构建邻接表（只需执行一次）
net_adjacency = build_net_adjacency('your_file_path.txt')
# 查找指定Net的关联Net
result = get_nets('target_net', net_adjacency)
print(result)

性能说明 #

1. 构建邻接表：只需要读取一次文件，时间复杂度为O(n)（n为文件行数），百万行文件的读取和处理通常只需要几秒。
2. 关联Net查找：基于内存中的邻接表做DFS遍历，时间复杂度为O(k)（k为关联Net的数量），500个关联Net的遍历几乎是瞬间完成。
3. 整体总耗时从原来的约1000秒，可降低到10秒以内（主要耗时在第一次文件读取）。

额外优化点 #

• 如果需要多次查询不同的Net，邻接表可以缓存起来，不需要重复构建。
• 对于超大文件（比如数亿行），可以考虑分块读取构建邻接表，或者使用内存映射文件（mmap模块）减少内存占用，但对于百万级别的文件，直接读取到内存完全可行。

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