题目重点：定义 COO 训练输入、重复坐标合并与 shape 校验，只枚举可能产生非零乘积的配对。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- A 形状 M×K、B 形状 K×N，输入为 COO (row,column,value) 列表；同坐标可重复出现并在计算前求和。
- 坐标越界与形状不匹配报错，零值不保留在结果 dict；使用浮点数，生产环境需另定数值精度与误差容忍。
解题路线
- 先按坐标合并 A/B 的重复项，并校验边界；将 B 按行 k 建索引，列出该行所有 (j,B[k,j])。
- 对 A 的每个非零 (i,k)，只与 B 第 k 行的非零项相乘，并把结果加到 C[i,j]。这是矩阵乘法 C[i,j]=Σ_k A[i,k]B[k,j] 的稀疏实现。
- 累积后去掉相加抵消为零的坐标；遍历顺序不影响数学结果，但浮点实际舍入顺序可能变化。
- 若 B 采用 CSR、A 采用 CSR/CSC，可更紧凑地定位行列；COO 适合展示接口和重复项语义，实际性能应按稀疏结构测试。
手动走一遍
A 只有 (0,1,2)、(1,0,3)，B 有 (1,2,4)、(0,2,5)，输出 C[(0,2)]=8、C[(1,2)]=15。若 A 同坐标 (0,1,2) 又出现 (0,1,-2)，该位置先合并为零，不贡献结果。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
"""Multiply COO sparse matrices, summing duplicate coordinates."""
def sparse_matmul(
shape_a: tuple[int, int],
entries_a: list[tuple[int, int, float]],
shape_b: tuple[int, int],
entries_b: list[tuple[int, int, float]],
) -> dict[tuple[int, int], float]:
rows, inner = shape_a
other_inner, columns = shape_b
if min(rows, inner, other_inner, columns) < 0 or inner != other_inner:
raise ValueError("incompatible matrix shapes")
def combine(entries, shape):
combined = {}
for row, column, number in entries:
if not (0 <= row < shape[0] and 0 <= column < shape[1]):
raise ValueError("COO coordinate out of bounds")
combined[(row, column)] = combined.get((row, column), 0.0) + number
return {coordinate: number for coordinate, number in combined.items() if number}
a = combine(entries_a, shape_a)
b = combine(entries_b, shape_b)
b_rows: dict[int, list[tuple[int, float]]] = {}
for (row, column), number in b.items():
b_rows.setdefault(row, []).append((column, number))
result: dict[tuple[int, int], float] = {}
for (row, middle), left in a.items():
for column, right in b_rows.get(middle, []):
coordinate = (row, column)
result[coordinate] = result.get(coordinate, 0.0) + left * right
return {coordinate: number for coordinate, number in result.items() if number}
复杂度
设 A 非零项 a，B 的第 k 行非零数 b_k，则枚举乘积数 P=Σ_(i,k)∈A b_k，时间 O(a+b+P)，结果字典最多 O(min(MN,P))；B 行索引 O(b)，A/B 合并字典 O(a+b)。高度稠密时退化到常规乘法量级。
易错点与追问
容易失分的边界
- 用三重循环扫描全部 MKN 组合，未利用稀疏性。
- 忽略重复 COO 坐标，覆盖而非求和。
- 把 B 的列索引误当成共享维 k，算出错误乘积。
- 没有检查 A 的列数等于 B 的行数。
继续深挖
- 若 A/B 极度不均匀，哪一行会形成热点，如何并行分片？
- CSR/CSC 相比 COO 在乘法中有哪些内存和访问优势？
- 浮点累加次序变化如何影响可复现性？
