Golang資料結構-稀疏矩陣(sparse matrix)

introduction

  • 數值分析中,大部分元素為或是同一個值的矩陣。反之,如果大部分元素都非零或為不同值,則這個矩陣是稠密的。
  • 處理方式:
    • 記錄矩陣中共有多少行列(row,col,default(預設值))
    • 記錄有多少個不同的值
    • 把具不同值的元素之行列與值 記錄在一小規模的陣列中,從而縮小程序的規模

稀疏矩陣保存

matrix_storage

  • 其相當於將原稀疏矩陣進行壓縮

原始矩陣轉成稀疏矩陣

  1. 遍歷矩陣,如果發現有元素之值不為默認值,創建一個有值節點(Node)
  2. 將其放入對應切片中
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    package main

    import (
    "bufio"
    "fmt"
    "math/rand"
    "os"
    "time"
    )

    type Matrix_node struct {
    row int
    col int
    val int
    }

    func init(){
    rand.Seed(time.Now().UnixNano())
    }

    func rand_val(matrix *[10][10]int){
    for i:=0;i<20;i++{
    c := rand.Intn(10)
    r := rand.Intn(10)
    v := rand.Intn(100)
    matrix[c][r] = v
    }
    }

    func tranverse_matrix(matrix *[10][10]int,node_array *[]*Matrix_node){
    //標準的稀疏矩陣一開始的節點會記錄元素矩陣的規模(最大行,最大列及預設值)
    init_node := &Matrix_node{
    row:10,
    col:10,
    val:0,
    }
    *node_array = append(*node_array,init_node)
    //遍歷矩陣
    for i, row := range *matrix {
    for j,v := range row {
    //發現有元素之值不為默認值
    if v != 0 {
    //創建節點
    Node := &Matrix_node{
    row:i,
    col:j,
    val:v,
    }
    //於切片中加入節點
    *node_array = append(*node_array,Node)

    }
    }
    }
    }

    func SaveData(filepath string, data []*Matrix_node){
    file,err := os.OpenFile(filepath,os.O_CREATE|os.O_WRONLY|os.O_TRUNC,0666)
    if err != nil {
    fmt.Println("OpenFile Error:",err)
    return
    }
    defer file.Close()
    Writer := bufio.NewWriter(file)
    for _,v := range data {
    line := fmt.Sprintf("%d\t%d\t%d\n",v.col,v.row,v.val)
    _,err := Writer.WriteString(line)
    if err != nil{
    fmt.Println("Write string error:",err)
    return
    }
    _ = Writer.Flush()
    }
    }

    func main(){
    //創建一個原始的數組
    var origin_matrix [10][10]int = [10][10]int{}

    //於matrix中塞入隨機數據
    rand_val(&origin_matrix)

    for _,v := range origin_matrix {
    fmt.Println(v)
    }

    //轉成一個稀疏數組
    Node_array := make([]*Matrix_node,0)
    tranverse_matrix(&origin_matrix,&Node_array)
    //儲存數據
    SaveData("learning_note/data_structure/sparse_matrix/main/matrix.data",Node_array)
    }

稀疏矩陣轉成原始矩陣

  1. 創建一個原始矩陣
    • 可根據稀疏矩陣的第一個節點知道其規模大小
      • 必須跳過第一個節點進行恢復,否則會out of range
  2. 遍歷稀疏矩陣
    • 讀取行、列、值在原數組上進行修改
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
package main

import (
"fmt"
"io/ioutil"
"strings"
)

type intslice []int

func ReadData(fileName string)(data string){
d,err := ioutil.ReadFile(fileName)
if err != nil {
fmt.Println("Read Data Failed",err)
return
}
data = string(d)
return
}

func main(){
filepath := "learning_note/data_structure/sparse_matrix/main/matrix.data"
data := ReadData(filepath)
data_array := strings.Split(data,"\n")
result := make([]intslice,0)
for i,v := range data_array[:len(data_array)-1]{
var row,col,data = 0,0,0
_,err := fmt.Sscanf(v,"%d\t%d\t%d",&row,&col,&data)
if err != nil{
fmt.Println("strconvert Failed:",err)
}
if i == 0 {
for i:=0;i<col;i++{
data := make(intslice,row)
result = append(result,data)
}
}else{
result[row][col] = data
}
}
for _,v := range result{
fmt.Println(v)
}
}