稀疏向量 (SparseVec)

SparseVec 高效地编码一个整数二维矩阵。输入矩阵必须编码为一个带有行长的一维整数向量。给定一个空值，SparseVec 使用 [1] 中描述的行位移进行压缩，并进一步使用 PackedVec 编码结果。

[1] Tarjan, Robert Endre, and Andrew Chi-Chih Yao. "Storing a sparse table." Communications of the ACM 22.11 (1979): 606-611.

用法

extern crate sparsevec;
use sparsevec::SparseVec;

fn main() {
    use sparsevec::SparseVec;
    let v:Vec<usize> = vec![1,0,0,0,
                            0,0,7,8,
                            9,0,0,3];
    let sv = SparseVec::from(&v, 0, 4);
    assert_eq!(sv.get(0,0).unwrap(), 1);
    assert_eq!(sv.get(1,2).unwrap(), 7);
    assert_eq!(sv.get(2,3).unwrap(), 3);
}

工作原理

以下描述了稀疏向量的行位移的一般概念，不包括实现中的某些额外优化。以下以二维向量为例

1 0 0
2 0 0
3 0 0
0 0 4

表示为一个行长为 3 的一维向量 v = [1,0,0,2,0,0,3,0,0,0,0,4]。将此向量存储在内存中是浪费的，因为其大部分元素是 0。我们可以使用行位移压缩此向量，将所有行合并到一个向量中，使得没有两个非零条目映射到同一个位置。对于上述示例，这将产生压缩向量 c = [1,2,3,0,4]

1 0 0
  2 0 0
    3 0 0
    0 0 4
---------
1 2 3 0 4

要从压缩向量中检索值，我们需要一个位移向量，它描述了在压缩过程中每行移动了多少。对于上面的例子，位移向量将是 d = [0, 1, 2, 2]。为了检索位置(2, 0)的值，我们可以使用 pos = d[row] + col 来计算它的压缩位置。

pos = d[2] + 0 // =2
value = c[pos] // =3