Question

How to compact a sparse matrix in Go

Answer 1

package main

import (
    "fmt"
)

// A sparse matrix is a matrix in which the majority of elements are zero.

// To compact a sparse matrix, use a method to store only the non‑zero
// entries using a triplet representation (row, column, value). 
// This reduces memory usage.

// Convert a sparse matrix into compact (triplet) form
func compactMatrix(matrix [][]int) [][]int {
    rows := len(matrix)
    cols := len(matrix[0])

    // Count non-zero elements
    count := 0
    for i := 0; i < rows; i++ {
        for j := 0; j < cols; j++ {
            if matrix[i][j] != 0 {
                count++
            }
        }
    }

    // Compact matrix has 3 rows: row index, col index, value
    compact := [][]int{
        make([]int, count),
        make([]int, count),
        make([]int, count),
    }

    k := 0

    // Fill compact matrix
    for i := 0; i < rows; i++ {
        for j := 0; j < cols; j++ {
            if matrix[i][j] != 0 {
                compact[0][k] = i      // row
                compact[1][k] = j      // column
                compact[2][k] = matrix[i][j] // value
                k++
            }
        }
    }

    return compact
}

func main() {
    matrix := [][]int{
        {0, 0, 3, 0, 8, 0, 0, 0, 0},
        {0, 0, 5, 7, 0, 0, 1, 0, 0},
        {0, 0, 0, 0, 0, 0, 0, 0, 0},
        {0, 2, 6, 0, 0, 4, 0, 0, 0},
        {0, 0, 0, 0, 9, 0, 0, 0, 0},
    }

    compact := compactMatrix(matrix)

    fmt.Println("Compact matrix:")
    for i := 0; i < 3; i++ {
        for j := 0; j < len(compact[0]); j++ {
            fmt.Printf("%d ", compact[i][j])
        }
        fmt.Println()
    }
}



/*
run:

Compact matrix:
0 0 1 1 1 3 3 3 4 
2 4 2 3 6 1 2 5 4 
3 8 5 7 1 2 6 4 9 

*/

 

70+ SQL courses for beginners and professionals