Golang中稀疏CSC矩阵的行排序问题求助

问题分析 #

你需要对CSC格式的稀疏矩阵按行内元素升序排序，同时保留空元素（零）的位置，但直接修改li/lj数组容易导致元素丢失——这是因为CSC是列优先存储结构，行相关的操作需要先提取行数据，处理后再重新构建结构，不能直接在原结构上修改行的元素位置。

解决方案思路 #

1. 提取行数据：从CSC结构中提取每一行的所有非零元素（值+原列索引）
2. 行内排序：对每一行的非零元素按值升序排列
3. 确定目标位置：根据升序规则，将排序后的非零元素放到该行的末尾（零元素在前，非零元素按升序在后）
4. 重构CSC：将所有排序后的元素按列优先顺序重新组织，生成新的CSC结构，确保不丢失任何元素

完整代码实现 #

package main

import (
	"fmt"
	"sort"
)

type CSC struct {
	a, lj, li []int
}

// getEl 根据行号i和列号j获取元素值，不存在则返回0
func getEl(i, j int, el *CSC) int {
	for k := el.lj[j]; k < el.lj[j+1]; k++ {
		if el.li[k] == i {
			return el.a[k]
		}
	}
	return 0
}

// maxSliceEl 获取切片中的最大值
func maxSliceEl(slice []int) int {
	max := 0
	for _, v := range slice {
		if v > max {
			max = v
		}
	}
	return max
}

// extractRowElements 从CSC中提取每一行的非零元素（值+原列索引）
func extractRowElements(csc *CSC) map[int][][2]int {
	rowElements := make(map[int][][2]int)
	numCols := len(csc.lj) - 1
	for j := 0; j < numCols; j++ {
		start := csc.lj[j]
		end := csc.lj[j+1]
		for k := start; k < end; k++ {
			row := csc.li[k]
			val := csc.a[k]
			rowElements[row] = append(rowElements[row], [2]int{val, j})
		}
	}
	return rowElements
}

// sortRowElements 对每一行的非零元素按值升序排序，并确定它们在排序后的行中的目标列位置
func sortRowElements(rowElements map[int][][2]int, numCols int) map[int][][2]int {
	sortedRowElements := make(map[int][][2]int)
	for row, elements := range rowElements {
		// 按元素值升序排序
		sort.Slice(elements, func(i, j int) bool {
			return elements[i][0] < elements[j][0]
		})
		nonZeroCount := len(elements)
		// 升序排序后，零元素在前，非零元素从行的末尾开始填充
		targetColStart := numCols - nonZeroCount
		for idx, elem := range elements {
			targetCol := targetColStart + idx
			sortedRowElements[row] = append(sortedRowElements[row], [2]int{targetCol, elem[0]})
		}
	}
	return sortedRowElements
}

// buildNewCSC 根据排序后的行元素构建新的CSC结构
func buildNewCSC(sortedRowElements map[int][][2]int, numRows, numCols int) CSC {
	// 收集所有元素，格式为 [列号, 行号, 值]
	var elements [][3]int
	for row, elems := range sortedRowElements {
		for _, elem := range elems {
			col := elem[0]
			val := elem[1]
			elements = append(elements, [3]int{col, row, val})
		}
	}

	// 按列优先排序（先列号升序，同列按行号升序）
	sort.Slice(elements, func(i, j int) bool {
		if elements[i][0] == elements[j][0] {
			return elements[i][1] < elements[j][1]
		}
		return elements[i][0] < elements[j][0]
	})

	// 构建新的a, li, lj数组
	a := make([]int, len(elements))
	li := make([]int, len(elements))
	lj := make([]int, numCols+1)

	currentCol := 0
	lj[0] = 0
	ljIdx := 1

	for idx, elem := range elements {
		col := elem[0]
		row := elem[1]
		val := elem[2]

		a[idx] = val
		li[idx] = row

		// 当列号变化时，更新lj指针
		if col != currentCol {
			for currentCol < col {
				lj[ljIdx] = idx
				ljIdx++
				currentCol++
			}
		}
	}

	// 填充lj数组剩余的位置
	for ljIdx <= numCols {
		lj[ljIdx] = len(elements)
		ljIdx++
	}

	return CSC{a: a, li: li, lj: lj}
}

// printMatrix 打印CSC格式的矩阵
func printMatrix(csc *CSC) {
	numCols := len(csc.lj) - 1
	maxRow := maxSliceEl(csc.li)
	numRows := maxRow + 1

	fmt.Println("Matrix:")
	for i := 0; i < numRows; i++ {
		var rowSum int
		for j := 0; j < numCols; j++ {
			val := getEl(i, j, csc)
			fmt.Printf("%d ", val)
			rowSum += val
		}
		fmt.Printf("| sum: %d\n", rowSum)
	}
}

func main() {
	ma := CSC{
		a:  []int{8, 2, 5, 7, 1, 9, 2},
		li: []int{0, 0, 1, 4, 4, 6, 4},
		lj: []int{0, 1, 1, 4, 6, 7},
	}

	numCols := len(ma.lj) - 1
	maxRow := maxSliceEl(ma.li)
	numRows := maxRow + 1
	fmt.Printf("Original matrix - Cols: %d, Rows: %d\n", numCols, numRows)
	printMatrix(&ma)

	// 提取行元素并排序
	rowElements := extractRowElements(&ma)
	sortedRowElements := sortRowElements(rowElements, numCols)

	// 构建新的CSC矩阵
	newCSC := buildNewCSC(sortedRowElements, numRows, numCols)
	fmt.Printf("\nSorted matrix - Cols: %d, Rows: %d\n", len(newCSC.lj)-1, maxSliceEl(newCSC.li)+1)
	printMatrix(&newCSC)
}

关键说明 #

• 避免元素丢失：通过先提取所有非零元素，处理后再重新构建CSC，确保每一个非零元素都被正确映射到新的位置，不会因为直接修改原li/lj数组导致指针错位。
• 空元素保留：排序后零元素的位置由行长度和非零元素数量决定，非零元素被放到行的末尾，原零元素位置保持为空，符合“不破坏空元素”的要求。
• CSC结构正确性：新的lj数组严格按照列优先的规则生成，确保每一列的元素索引范围正确，保证CSC结构的有效性。

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