首行含空行时如何正确实现压缩行存储(CSR)格式？

错误根源 #

你的CSR实现问题出在行指针R向量的定义错误，以及adress方法缺失了「未找到对应列时返回默认值」的逻辑：

1. 行指针R的核心作用是标记每行第一个非零元素在V中的起始位置，以及下一行的起始位置（即当前行所有非零元素的结束位置+1）。对于全零行，该行的起始位置和下一行的起始位置必须相等，以此标识空行。
2. 当前R向量[1,2,3,4,5,6]错误地给每一行都分配了非零元素的起始位置，导致全零行被错误关联到其他行的非零元素——比如访问行2（索引2）时，会错误指向V的第2个元素，从而返回1而非0。
3. adress方法中，如果在当前行的非零元素范围内找不到目标列j，会因未定义v_index报错，且未返回默认值。

正确的CSR参数定义 #

针对你的5行3列矩阵（索引从1开始），正确的参数应该是：

• V = [1,1,1,2,2,2]（非零元素值，顺序不变）
• C = [1,2,3,1,2,3]（非零元素的列索引，顺序不变）
• R = [1,1,1,4,4,7]（行指针，解释如下）：
  • R[1] = 1，R[2] = 1 → 第1行无任何非零元素
  • R[2] = 1，R[3] = 1 → 第2行无任何非零元素
  • R[3] = 1，R[4] = 4 → 第3行的非零元素从V[1]到V[3]
  • R[4] = 4，R[5] = 4 → 第4行无任何非零元素
  • R[5] = 4，R[6] = 7 → 第5行的非零元素从V[4]到V[6]

修正后的Python实现 #

import numpy as np

class CRS:
    def __init__(self, N, M):
        self.N = N
        self.M = M
        self.V = [1,1,1,2,2,2]
        self.C = [1,2,3,1,2,3]
        # 修正后的行指针R
        self.R = [1,1,1,4,4,7]
        self.default_value = 0  # 矩阵默认值为0，而非NaN

    def adress(self, i, j):
        # 索引从1开始，完善边界检查
        if i < 1 or i > self.N or j < 1 or j > self.M:
            print("Index out of range.")
            return
        start = self.R[i]
        stop = self.R[i+1]
        # 空行直接返回默认值
        if stop <= start:
            return self.default_value
        # 转换为Python的0索引遍历
        for k in range(start-1, stop-1):
            if self.C[k] == j:
                return self.V[k]
        # 未找到对应列，返回默认值
        return self.default_value

关键修正点说明 #

1. 行指针R修正：用相等的前后值标记全零行，确保空行不会错误关联到其他行的元素。
2. 索引转换：Python列表为0索引，需将R的1索引值减1后再访问V和C。
3. 默认值调整：原矩阵默认值为0，替换np.NAN更符合实际场景。
4. 边界检查完善：补充索引小于1的情况，符合1索引的规则。
5. 未找到列的处理：遍历完当前行非零元素后，未匹配到目标列则返回默认值0。

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