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

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

2019.12.01 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

乘法

计算稀疏矩阵与向量的乘法，我们迭代哈希表的 key 与 value，key[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]