下三角矩阵映射为一维数组的高效实现优化问询

核心映射数学逻辑 #

行优先（Row-major）映射 #

对于n阶下三角矩阵（索引从0开始）：

• 第i行共有i+1个有效元素（j范围0~i）
• 前i行的总元素数为等差数列求和：1+2+...+i = i(i+1)/2
• 矩阵元素mat[i,j]对应的一维数组索引为：k = i(i+1)/2 + j

列优先（Column-major）映射 #

对于n阶下三角矩阵（索引从0开始）：

• 第j列共有n-j个有效元素（i范围j~n-1）
• 前j列的总元素数为：n + (n-1) + ... + (n-j+1) = nj - j(j-1)/2
• 矩阵元素mat[i,j]对应的一维数组索引为：k = nj - j(j-1)/2 + (i-j)

原代码的效率问题 #

你的实现遍历了整个n×n矩阵（时间复杂度O(n²)），但下三角矩阵仅包含n(n+1)/2个有效元素，近一半的循环属于无效判断（i<j时直接跳过），造成了不必要的性能浪费。

优化实现（理论最优复杂度O(n(n+1)/2)） #

行优先优化版 #

直接遍历下三角的有效元素，避免无效循环，且可通过递增索引替代重复公式计算：

import numpy as np

def Row_major_mapper(mat: np.ndarray, n: int) -> np.ndarray:
    size = int(n * (n + 1) / 2)
    arr = np.zeros(size,)
    k = 0
    for i in range(n):
        # 仅遍历当前行的下三角元素（j从0到i）
        for j in range(i + 1):
            arr[k] = mat[i, j]
            k += 1
    return arr

若需保留映射公式（支持随机访问场景），仍可只遍历有效元素：

import numpy as np

def Row_major_mapper(mat: np.ndarray, n: int) -> np.ndarray:
    size = int(n * (n + 1) / 2)
    arr = np.zeros(size,)
    for i in range(n):
        for j in range(i + 1):
            k = int(i * (i + 1) / 2 + j)
            arr[k] = mat[i, j]
    return arr

列优先优化版 #

按列遍历下三角有效元素，同样通过递增索引精简实现：

import numpy as np

def Column_major_mapper(mat: np.ndarray, n: int) -> np.ndarray:
    size = int(n * (n + 1) / 2)
    arr = np.zeros(size,)
    k = 0
    for j in range(n):
        # 仅遍历当前列的下三角元素（i从j到n-1）
        for i in range(j, n):
            arr[k] = mat[i, j]
            k += 1
    return arr

保留映射公式的版本：

import numpy as np

def Column_major_mapper(mat: np.ndarray, n: int) -> np.ndarray:
    size = int(n * (n + 1) / 2)
    arr = np.zeros(size,)
    for j in range(n):
        for i in range(j, n):
            k = int(n * j - (j - 1) * j / 2 + i - j)
            arr[k] = mat[i, j]
    return arr

关键优化总结 #

• 仅遍历下三角有效元素，减少近一半的循环次数
• 顺序遍历场景下，用递增索引替代重复的映射公式计算，降低算术开销

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