0%

Golang 中的稀疏矩阵

发表于 更新于

什么是稀疏矩阵

稀疏矩阵（英语：sparse matrix），在数值分析中，是其元素大部分为零的矩阵。反之，如果大部分元素都非零，则这个矩阵是稠密的。在科学与工程领域中求解线性模型时经常出现大型的稀疏矩阵。

在使用计算机存储和操作稀疏矩阵时，经常需要修改标准算法以利用矩阵的稀疏结构。由于其自身的稀疏特性，通过压缩可以大大节省稀疏矩阵的内存代价。更为重要的是，由于过大的尺寸，标准的算法经常无法操作这些稀疏矩阵[1]。

Golang中的稀疏矩阵

在 Golang 中我们可以使用一个二维数组模拟一个稀疏矩阵：

1
2
3
4
var chessMap [8][8]int
chessMap[1][1] = 1
chessMap[2][2] = 2
chessMap[3][3] = 3

对其打印效果如下：

1
2
3
4
5
6
7
8
0    0    0    0    0    0    0    0
0    1    0    0    0    0    0    0
0    0    2    0    0    0    0    0
0    0    0    3    0    0    0    0
0    0    0    0    0    0    0    0
0    0    0    0    0    0    0    0
0    0    0    0    0    0    0    0
0    0    0    0    0    0    0    0

将二维数组中的数据转换为一个稀疏数组：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
var sparseArr []Node
node := Node{
    row: 8,
    col: 8,
    val: 0,
}
sparseArr = append(sparseArr, node)
for i, v := range chessMap {
    for j, v2 := range v {
        if v2 != 0 {
            node := Node{
                row: i,
                col: j,
                val: v2,
            }
            sparseArr = append(sparseArr, node)
        }
    }
}

将稀疏数组存储到一个名为“chess_data.txt”文件中：

1
2
3
4
5
6
7
8
9
10
11
file, err := os.OpenFile("chess_data.txt", os.O_CREATE|os.O_WRONLY, 0666)
if err != nil {
    fmt.Println("open file failed, err:", err)
    return
}

for _, v := range sparseArr {
    file.WriteString(fmt.Sprintf("%d %d %d\n", v.col, v.row, v.val))

}
file.Close()

重新打开数据存储文件，并将数据恢复至一个稀疏数组中：

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
file, err = os.OpenFile("chess_data.txt", os.O_CREATE|os.O_RDONLY, 0666)
defer file.Close()
var sparseArr2 []Node
reader := bufio.NewReader(file)
for {
    line, err := reader.ReadString('\n')
    if err == io.EOF {
        if len(line) != 0 {
            fmt.Println(line)
        }
        fmt.Println("read file complete.")
        break
    }
    if err != nil {
        fmt.Println("read file failed. err: ", err)
        return
    }
    lineSlice := strings.Split(strings.Replace(line, "\n", "", -1), " ")
    node := Node{}
    for i, num := range lineSlice {
        n, err := strconv.ParseInt(num, 10, 32)
        if err != nil {
            fmt.Println(err)
        }
        if i == 0 {
            node.col = int(n)
        } else if i == 1 {
            node.row = int(n)
        } else {
            node.val = int(n)
        }
    }
    sparseArr2 = append(sparseArr2, node)
}

将稀疏数组中的数据转成原始数组

1
2
3
4
5
6
7
var chessMap2 [8][8]int
for i, v := range sparseArr2 {
    if i == 0 {
        continue
    }
    chessMap2[v.col][v.row] = v.val
}

打印恢复后的数据：

1
2
3
4
5
6
7
8
9
read file complete.
0    0    0    0    0    0    0    0
0    1    0    0    0    0    0    0
0    0    2    0    0    0    0    0
0    0    0    3    0    0    0    0
0    0    0    0    0    0    0    0
0    0    0    0    0    0    0    0
0    0    0    0    0    0    0    0
0    0    0    0    0    0    0    0

完整代码及说明：

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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
package main

import (
    "bufio"
    "fmt"
    "io"
    "os"
    "strconv"
    "strings"
)

// Node 代表稀疏数组中的一条数据
type Node struct {
    row int // 横坐标
    col int // 纵坐标
    val int // 值
}

func main() {
    var chessMap [8][8]int
    chessMap[1][1] = 1
    chessMap[2][2] = 2
    chessMap[3][3] = 3

    for _, v := range chessMap {
        for _, v2 := range v {
            fmt.Printf("%d\t", v2)
        }
        fmt.Println()
    }

    // 将原始数组转成稀疏数组
    var sparseArr []Node
    node := Node{
        row: 8,
        col: 8,
        val: 0,
    }
    sparseArr = append(sparseArr, node)
    for i, v := range chessMap {
        for j, v2 := range v {
            if v2 != 0 {
                node := Node{
                    row: i,
                    col: j,
                    val: v2,
                }
                sparseArr = append(sparseArr, node)
            }
        }
    }

    // 创建一个可写入文件
    file, err := os.OpenFile("chess_data.txt", os.O_CREATE|os.O_WRONLY, 0666)
    if err != nil {
        fmt.Println("open file failed, err:", err)
        return
    }

    for _, v := range sparseArr {
        // 写入数据
        file.WriteString(fmt.Sprintf("%d %d %d\n", v.col, v.row, v.val))

    }
    file.Close()

    // 打开存储稀疏数组数据的文件
    file, err = os.OpenFile("chess_data.txt", os.O_CREATE|os.O_RDONLY, 0666)
    defer file.Close()
    var sparseArr2 []Node
    reader := bufio.NewReader(file)
    for {
        line, err := reader.ReadString('\n')
        if err == io.EOF {
            if len(line) != 0 {
                fmt.Println(line)
            }
            fmt.Println("read file complete.")
            break
        }
        if err != nil {
            fmt.Println("read file failed. err: ", err)
            return
        }
        // 处理每行数据
        lineSlice := strings.Split(strings.Replace(line, "\n", "", -1), " ")
        node := Node{}
        for i, num := range lineSlice {
            n, err := strconv.ParseInt(num, 10, 32)
            if err != nil {
                fmt.Println(err)
            }
            // 将数据恢复到稀疏数组的节点中
            if i == 0 {
                node.col = int(n)
            } else if i == 1 {
                node.row = int(n)
            } else {
                node.val = int(n)
            }
        }
        sparseArr2 = append(sparseArr2, node)
    }

    // 将稀疏数组转成原始数组
    var chessMap2 [8][8]int
    for i, v := range sparseArr2 {
        // 第一条数据为矩阵规格 需要丢弃
        if i == 0 {
            continue
        }
        chessMap2[v.col][v.row] = v.val
    }

    for _, v := range chessMap2 {
        for _, v2 := range v {
            fmt.Printf("%d\t", v2)
        }
        fmt.Println()
    }
}