Python对称列表索引性能调优：提速BuildBasis与Indices方法

针对你提到的BuildBasis和Indices步骤性能瓶颈，以下是具体优化思路和实现代码：

核心优化思路 #

1. 对称变换计算优化 #

2x2矩阵的对称变换逻辑固定，直接手动计算变换后的矩阵（避免numpy数组转换开销），同时缓存重复矩阵的变换结果，减少冗余计算：

from functools import lru_cache

@lru_cache(maxsize=None)
def get_symmetries(mat):
    # mat必须是元组格式（支持哈希，适配缓存）
    a, b = mat[0]
    c, d = mat[1]
    # 定义7种对称变换（排除自身）
    flip_v = ((c, d), (a, b))       # 垂直翻转
    flip_h = ((b, a), (d, c))       # 水平翻转
    rot90_ccw = ((b, d), (a, c))    # 逆时针90°旋转
    rot90_cw = ((c, a), (d, b))     # 顺时针90°旋转（270°逆时针）
    transpose = ((a, c), (b, d))    # 转置
    trans_flip_v = ((b, d), (a, c)) # 转置后垂直翻转
    trans_flip_h = ((c, a), (d, b)) # 转置后水平翻转
    
    # 去重（部分变换对对称矩阵会产生相同结果）
    return list(set([flip_v, flip_h, rot90_ccw, rot90_cw, transpose, trans_flip_v, trans_flip_h]))

2. 用并查集（Union-Find）替代线性遍历管理等价类 #

原来逐个检查元素是否属于基元的逻辑是O(n²)复杂度，改用并查集后，查找和合并操作近似O(1)，大幅降低时间消耗：

class UnionFind:
    def __init__(self, size):
        self.parent = list(range(size))
        self.rank = [0] * size
    
    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

3. 预构建值-索引映射，快速定位对称变换结果 #

利用字典存储矩阵到索引的映射，避免每次查找对称变换结果时遍历整个列表：

def build_basis_and_indices(L):
    # 将所有矩阵转为元组（支持哈希和快速比较）
    L_tuples = [tuple(map(tuple, mat)) for mat in L]
    # 构建矩阵到索引的映射
    val_to_idx = {val: idx for idx, val in enumerate(L_tuples)}
    size = len(L_tuples)
    uf = UnionFind(size)
    
    # 合并所有等价索引
    for idx in range(size):
        current_mat = L_tuples[idx]
        for sym_mat in get_symmetries(current_mat):
            if sym_mat in val_to_idx:
                uf.union(idx, val_to_idx[sym_mat])
    
    # 生成基元（原始状态索引）和对称态索引映射
    basis = []
    idx_to_sym_group = {}
    root_groups = {}
    
    for idx in range(size):
        root = uf.find(idx)
        if root not in root_groups:
            basis.append(root)
            root_groups[root] = []
        root_groups[root].append(idx)
    
    for root, group in root_groups.items():
        for idx in group:
            idx_to_sym_group[idx] = group
    
    return basis, idx_to_sym_group

关键优化点总结 #

• 缓存复用：用lru_cache缓存相同矩阵的对称变换结果，避免重复计算。
• 数据结构升级：并查集将等价类管理的时间复杂度从O(n²)降至近似O(n)。
• 快速查找：字典映射替代线性遍历，对称变换结果的索引定位从O(n)变为O(1)。
• 减少开销：手动计算2x2矩阵变换，避免numpy数组转换的额外成本。

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