大型原子矩阵Short Circuit检测优化：寻求执行效率提升

核心优化思路：引入虚拟节点 #

直接解决遍历顶部/底部原子的性能瓶颈——在并查集中新增两个虚拟节点：

• top_root：代表矩阵顶部的所有位置
• bottom_root：代表矩阵底部的所有位置

当原子被转化为导体时：

1. 若该原子在第一行，直接与top_root合并
2. 若该原子在最后一行，直接与bottom_root合并
3. 再正常合并它和上下左右的相邻导体原子

之后，短路检测只需要一次查询：判断top_root和bottom_root是否处于同一连通分量即可，操作复杂度接近常数，彻底替代原来的遍历逻辑。

手动实现优化后的并查集 #

以下是不带任何导入的纯手动实现，包含路径压缩和按秩合并（并查集高效运行的两个核心优化）：

class DisjointSet:
    def __init__(self, size):
        # size为矩阵总原子数，额外加2个虚拟节点，总容量为size+2
        self.parent = list(range(size + 2))
        self.rank = [0] * (size + 2)
        # 定义虚拟节点索引：size对应顶部虚拟节点，size+1对应底部虚拟节点
        self.top_root = size
        self.bottom_root = size + 1

    def find(self, x):
        # 路径压缩：直接将节点挂到根节点下，减少后续查询层级
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        # 按秩合并：将秩小的树挂到秩大的树下，避免树结构失衡
        x_root = self.find(x)
        y_root = self.find(y)
        if x_root == y_root:
            return
        if self.rank[x_root] < self.rank[y_root]:
            self.parent[x_root] = y_root
        else:
            self.parent[y_root] = x_root
            if self.rank[x_root] == self.rank[y_root]:
                self.rank[x_root] += 1

    def is_short_circuit(self):
        # 仅需检查两个虚拟节点是否连通
        return self.find(self.top_root) == self.find(self.bottom_root)

结合矩阵操作的使用示例 #

假设矩阵为n×n，用i * n + j将二维坐标转化为一维索引（i为行号，j为列号，从0开始）：

def simulate_short_circuit(n):
    total_atoms = n * n
    ds = DisjointSet(total_atoms)
    # 记录原子是否为导体的状态数组
    is_conductor = [[False for _ in range(n)] for _ in range(n)]

    def convert_and_check(i, j):
        if is_conductor[i][j]:
            return False  # 已是导体，无需操作
        is_conductor[i][j] = True
        atom_idx = i * n + j
        # 关联虚拟节点
        if i == 0:
            ds.union(atom_idx, ds.top_root)
        if i == n - 1:
            ds.union(atom_idx, ds.bottom_root)
        # 合并相邻导体
        directions = [(-1,0), (1,0), (0,-1), (0,1)]
        for di, dj in directions:
            ni, nj = i + di, j + dj
            if 0 <= ni < n and 0 <= nj < n and is_conductor[ni][nj]:
                neighbor_idx = ni * n + nj
                ds.union(atom_idx, neighbor_idx)
        # 直接返回短路状态
        return ds.is_short_circuit()

    # 示例操作：转化左上角和右下角原子，检查短路
    convert_and_check(0, 0)
    convert_and_check(n-1, n-1)
    print(ds.is_short_circuit())

复杂度分析 #

• 单个转化操作：O(α(n²))，其中α是阿克曼函数的反函数，增长极慢——对于2000×2000的矩阵（总原子数4e6），α(4e6)≈5，几乎是常数级开销。
• 短路检测：O(α(n²))，单次查询即可完成，彻底消除了原来O(n)的遍历开销。

额外优化建议 #

1. 提前终止：一旦is_short_circuit()返回True，可直接停止后续转化操作，因为短路已形成。
2. 空间优化：若转化操作不可逆，无需维护完整矩阵状态，用集合存储已转化的原子索引即可，节省内存。

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