稀疏矩阵是指矩阵中绝大多数元素为0的矩阵，在图计算、推荐系统、有限元分析等场景中应用十分广泛。COO格式全称为坐标格式，通过存储非零元素的行索引、列索引和对应值来表示稀疏矩阵，是构建阶段最常用的稀疏矩阵存储格式之一。无自循环的稀疏矩阵要求矩阵对角线上的元素全部为0，也就是不存在行索引等于列索引的非零元素，这类矩阵在图算法中对应无自环图的邻接矩阵，能避免算法处理时出现无效的自连接逻辑。
COO格式的基本结构
COO格式的核心是用三个数组分别存储非零元素的信息：
- row数组：存储每个非零元素的行索引，长度等于非零元素个数
- col数组：存储每个非零元素的列索引，长度等于非零元素个数
- data数组：存储每个非零元素的对应数值，长度等于非零元素个数
比如一个3x3的稀疏矩阵，非零元素为(0,1)=2、(1,2)=3、(2,0)=1，对应的COO格式表示就是row=[0,1,2]，col=[1,2,0]，data=[2,3,1]。
构建无自循环COO稀疏矩阵的核心思路
构建过程主要分为三步：首先收集所有候选的非零元素，然后过滤掉行索引等于列索引的自循环元素，最后对剩余元素进行去重处理，避免重复存储同一个位置的非零值。
1. 过滤自循环元素
自循环元素的特征是行索引和列索引相等，在收集到候选元素后，直接判断row[i]是否等于col[i]，如果相等则直接丢弃该元素即可。
2. 去重处理
如果输入的元素中存在同一个位置多次出现的情况，需要合并相同位置的元素，通常的做法是将相同(row, col)对应的data值相加，得到最终的非零值。
Python实现示例
下面是用Python实现高效构建无自循环COO稀疏矩阵的完整代码：
from collections import defaultdict
def build_coo_without_self_loop(elements, matrix_size):
"""
构建无自循环的COO格式稀疏矩阵
:param elements: 候选非零元素列表，每个元素为(row, col, value)
:param matrix_size: 矩阵的大小，为N表示NxN矩阵
:return: (row_list, col_list, data_list) 三个COO格式的数组
"""
# 第一步：过滤自循环元素，同时用字典暂存相同位置的元素值
temp_dict = defaultdict(float)
for r, c, v in elements:
# 校验索引合法性
if not (0 <= r < matrix_size and 0 <= c < matrix_size):
continue
# 过滤自循环元素
if r == c:
continue
# 相同位置的元素值累加
temp_dict[(r, c)] += v
# 第二步：拆分字典为COO格式的三个数组
row_list = []
col_list = []
data_list = []
for (r, c), v in temp_dict.items():
# 过滤掉累加后为0的元素
if v == 0:
continue
row_list.append(r)
col_list.append(c)
data_list.append(v)
return row_list, col_list, data_list
# 测试用例
if __name__ == "__main__":
# 候选元素包含自循环元素、重复元素、非法索引元素
test_elements = [
(0, 0, 1.0), # 自循环元素，会被过滤
(0, 1, 2.0),
(0, 1, 3.0), # 和上面的(0,1)重复，值会累加为5.0
(1, 2, 4.0),
(2, 2, 5.0), # 自循环元素，会被过滤
(3, 1, 6.0), # 行索引超出矩阵大小，会被过滤
(1, 3, 7.0), # 列索引超出矩阵大小，会被过滤
]
matrix_size = 3
row, col, data = build_coo_without_self_loop(test_elements, matrix_size)
print("行索引数组:", row)
print("列索引数组:", col)
print("值数组:", data)
性能优化建议
如果处理的元素数量非常大，还可以做进一步的优化：
- 如果输入的元素已经按行或列排序，可以在遍历过程中直接合并相邻重复元素，减少字典的内存开销
- 如果确定输入元素没有重复，可以跳过字典去重步骤，直接过滤自循环元素后生成数组，提升构建速度
- 对于超大规模的稀疏矩阵，可以考虑用数组代替字典存储临时数据，减少哈希操作的开销
通过上述方法构建的COO格式稀疏矩阵，既保证了没有自循环元素，也避免了重复存储的问题，能够直接用于后续的稀疏矩阵运算或图算法处理。