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

introduction

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

---

稀疏矩陣保存

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

---

原始矩陣轉成稀疏矩陣

1. 遍歷矩陣，如果發現有元素之值不為默認值，創建一個有值節點(Node)
2. 將其放入對應切片中

   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. 遍歷稀疏矩陣
   • 讀取行、列、值在原數組上進行修改

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)
	}
	}