盒子
盒子
文章目录
  1. Nim编程入门
    1. 构造稀疏矩阵与向量
    2. 初始化
    3. 乘法
    4. 测试

Nim 语言使用哈希表实现稀疏矩阵

Nim编程入门

稀疏矩阵是指,矩阵中非零元素只占总元素很小的比例。使用稀疏矩阵,我们可以高效计算矩阵与向量的乘法。一般的矩阵与向量乘法的时间复杂度为为 O(n^2),而稀疏矩阵与向量乘法的时间复杂度与非零元素的个数有关。

而谷歌著名的 page rank 正是建立在稀疏矩阵的基础上,大幅减少了花费的时间。

构造稀疏矩阵与向量

我们使用哈希表实现稀疏矩阵,key 存储矩阵中非零元素的横纵坐标,而 value 存储非零元素的值。

矩阵和向量则基于 seq

1
2
3
4
5
6
7
8
9
10
import tables

type
Matrix* = object
data*: seq[seq[float]]
rows*: int
cols*: int
Vector* = seq[float]
SparseMatrix* = object
data*: Table[(int, int), float]

初始化

初始化稀疏矩阵,我们只需保存矩阵中非零元素的坐标与值。

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
proc newVector*(size: int): Vector =
newSeq[float](size)

proc newSparseMatrix*(): SparseMatrix =
discard

proc newSparseMatrix*(m: Matrix): SparseMatrix =
for i in 0 ..< m.rows:
for j in 0 ..< m.cols:
let value = m.data[i][j]
if value != 0:
result.data[(i, j)] = value

proc len*(s: SparseMatrix): int =
s.data.len

proc `[]`*(s: SparseMatrix, idx: (int, int)): float =
if idx in s.data:
s.data[idx]
else:
0.0

proc `[]`*(s: SparseMatrix, idx: Slice[int]): float =
let idx = (idx.a, idx.b)
if idx in s.data:
s.data[idx]
else:
0.0

乘法

计算稀疏矩阵与向量的乘法,我们迭代哈希表的 keyvaluekey[0] 是横坐标,key[1] 是纵坐标。

我们将矩阵中(row, col)的值,与 col 列的向量的值相乘,并相加,就可以得到 row 行的结果。

1
2
3
4
proc `*`*(s: SparseMatrix, v: Vector): Vector =
result = newVector(v.len)
for key, value in s.data:
result[key[0]] += v[key[1]] * s[key]

测试

1
2
3
4
5
6
7
when isMainModule:
let m = Matrix(data: @[@[0.0, 0.90, 0.0, 0.0, 0.0], @[0.0, 0.0, 0.36, 0.36, 0.18],
@[0.0, 0.0, 0.0, 0.90, 0.0], @[0.90, 0.0, 0.0, 0.0, 0.0],
@[0.47, 0.0, 0.47, 0.0, 0.0]], rows: 5, cols: 5)
let s = newSparseMatrix(m)
let v: Vector = @[0.05, 0.04, 0.36, 0.37, 0.19]
echo s * v

输出

1
@[0.036, 0.297, 0.333, 0.045, 0.1927]