Python三角矩阵压缩（高效存储与访问技巧）

为什么要压缩存储？

对于一个 n×n 的三角矩阵，非零元素只有 n(n+1)/2 个，而完整存储需要 n² 个空间。当 n 很大时（比如10000），浪费的空间非常可观！通过稀疏矩阵优化Python技术，我们只存储有效数据，大幅提升内存利用率。

压缩存储的核心思想

我们将二维矩阵“压平”成一维数组，并建立原矩阵坐标 (i, j) 到一维索引 k 的映射关系。

1. 下三角矩阵压缩（含对角线）

假设我们有一个 n×n 的下三角矩阵，只存储 i ≥ j 的元素。

元素 a_ij 在一维数组中的位置为：

k = i*(i+1)//2 + j  

其中 i 和 j 从 0 开始计数。

2. 上三角矩阵压缩（含对角线）

对于上三角矩阵（i ≤ j），元素 a_ij 的一维索引为：

k = i*n - i*(i-1)//2 + (j - i)  

这个公式可以简化为：k = n*i - i*(i+1)//2 + j。

Python 实战：实现下三角矩阵压缩类

下面是一个完整的 Python 类，用于存储和访问下三角矩阵：

class LowerTriangularMatrix:    def __init__(self, n):        self.n = n        # 只分配 n(n+1)/2 个空间        self.data = [0] * (n * (n + 1) // 2)        def _index(self, i, j):        """计算 (i, j) 对应的一维索引"""        if i < j:            raise IndexError("上三角区域无数据")        return i * (i + 1) // 2 + j        def set(self, i, j, value):        """设置元素值"""        k = self._index(i, j)        self.data[k] = value        def get(self, i, j):        """获取元素值"""        if i < j:            return 0  # 上三角默认为0        k = self._index(i, j)        return self.data[k]        def __str__(self):        """打印完整矩阵（用于调试）"""        rows = []        for i in range(self.n):            row = []            for j in range(self.n):                row.append(str(self.get(i, j)))            rows.append("[" + ", ".join(row) + "]")        return "\n".join(rows)# 使用示例matrix = LowerTriangularMatrix(4)matrix.set(0, 0, 1)matrix.set(1, 0, 2)matrix.set(1, 1, 3)matrix.set(2, 1, 5)print(matrix)  

应用场景与优势

这种上三角矩阵压缩算法广泛应用于：

• 动态规划（如编辑距离、最长公共子序列）
• 图论中的邻接矩阵（若图为有向无环图）
• 科学计算中的系数矩阵

相比完整存储，压缩后内存占用减少近50%（当 n 很大时），且访问速度更快（缓存友好）。

总结

通过本文，你已经掌握了Python三角矩阵压缩的基本原理和实现方法。记住关键点：

1. 只存储有效元素（下三角或上三角）
2. 建立二维坐标到一维索引的映射公式
3. 封装成类，便于复用和维护

希望这篇教程能帮助你在数据结构与算法学习中更进一步！如果你觉得有用，欢迎分享给其他正在学习稀疏矩阵优化Python的朋友。