Meta 稀疏矩阵相乘：非零连接、形状与抵消

题目重点：用稀疏行字典表示矩阵，沿左矩阵非零中间索引连接右矩阵对应行，跳过无用零乘。

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

A为m×k，B为k×n；输入是行字典列表，缺项0，output_columns明确保留全零列形状。字典列索引须在对应范围内。
值可正负，明确存的0也略过，结果恰好抵消为0时不保存。浮点近零是否截断需要额外容差合同，示例只删精确0。

解题路线

普通三循环对每i/j/k都做乘法，即使大多0。稀疏行组织让A[i,k]非零时直接遍历B[k,*]非零，把乘积加到out[i,j]。
复杂度由实际非零连接数Σ_(i,k∈nzA) nnz(B[k])决定，不简单写O(nnzA+nnzB)：一个密集B行被很多A行引用会重复贡献。
输出用每行字典累积，多个中间k可能贡献同一j；不能覆盖最后乘积。最终删除精确0，避免稀疏结果因正负抵消留下无效条目。
显式形状检查很重要：空行不说明列数0，故B列数单独传入；m=0/k=0/n=0的合法空维度仍保留m行结果。输入不修改。

手动走一遍

A=[[2,2]]、B=[[1],[-1]]，两个中间项对同一输出列贡献2与−2，结果0，稀疏行{}。若直接out[j]=a*b会得到−2。测试将稀疏输出恢复dense，与NumPy矩阵乘法核对3000组。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

def sparse_matrix_multiply(left, right, output_columns):
    """Left: m row dictionaries over k columns. Right: k rows over output_columns.

    Absent entries mean zero. Both inputs may contain explicitly stored zero values.
    Returns m row dictionaries, omitting output entries whose sum is exactly zero.
    """
    if not isinstance(output_columns,int) or output_columns<0:
        raise ValueError('nonnegative output column count required')
    inner=len(right)
    for rows,bound in ((left,inner),(right,output_columns)):
        if any(any(not isinstance(c,int) or not 0<=c<bound for c in row) for row in rows):
            raise ValueError('sparse column index outside shape')
    result=[]
    for row in left:
        out={}
        for k,a in row.items():
            if a==0:continue
            for j,b in right[k].items():
                if b!=0:out[j]=out.get(j,0)+a*b
        result.append({j:value for j,value in out.items() if value!=0})
    return result

复杂度

时间O(nnzA+nnzB+Σ_(i,k∈nzA)nnz(B[k]))含索引检查，输出空间O(nnzC)但累积中间字典可能含最终抵消条目。输入行字典内存与非零数同阶；最坏dense仍O(mkn)。

易错点与追问

容易失分的边界

只有非零数很少不保证输出也稀疏，矩阵乘积可能fill-in变密。
重复连接需要累加，不能把dict赋值当点积求和。
根据最大出现列推断shape会丢尾部全零列或全零矩阵。

继续深挖

若B按列压缩，适于直接行列点积；选择CSR/CSC依据访问模式，不必每题通用一种结构。
多个线程并行按独立输出行分工可避免同元素锁；单行极热可分k块后reduce，需处理数值累加顺序差异。