BTree

以下面的矩阵为例:

\begin{bmatrix} \ 0 & 0 & 3 & 0 & 4 \\ 0 & 0 & 5 & 7 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 2 & 6 & 0 & 0 \ \end{bmatrix}

这个矩阵用数组存放, 效果如下图:

这种存储方式的特点是:

• BTree 中节点是按照 key 的顺序进行存储的, 而我们选用 (row, column) 作为 key, 这样
  • 首先以行号递增排序
  • 如果行号相同, 以列号递增排序
• 查找/插入/删除矩阵中某个节点的值时的性能是 O(log(m * n)), 其中 m 和 n 是矩阵中非 0 元素的最大行列数
• 比较适合存放随时增减节点的矩阵, 插入或者删除元素的成本比较低, 很灵活
• 支持范围查找, 比如查找某一行中所有的列
• 实现简单

算法的实现

使用 BTree 进行存储, 实现起来最简单, 因为我们要求的接口与 BTreeMap 本身的接口非常匹配, 需要额外 花费的精力很少.

#![allow(unused)]
fn main() {
use std::collections::BTreeMap;

use crate::traits::IsZero;

#[derive(Debug, Default, Clone, Copy, Eq, PartialEq, Ord, PartialOrd, Hash)]
pub struct MatrixIndex {
    row: usize,
    column: usize,
}

/// Store sparse matrix with btree.
#[derive(Debug, Default, Clone)]
pub struct BTreeSparseMatrix<T: IsZero> {
    map: BTreeMap<MatrixIndex, T>,
}

impl<T: IsZero> BTreeSparseMatrix<T> {
    #[must_use]
    pub fn construct<I, I2>(sparse_matrix: I) -> Self
    where
        I: IntoIterator<Item=I2>,
        I2: IntoIterator<Item=T>,
    {
        let mut map = BTreeMap::new();

        for (row, row_list) in sparse_matrix.into_iter().enumerate() {
            for (column, element) in row_list.into_iter().enumerate() {
                if element.is_not_zero() {
                    map.insert(MatrixIndex { row, column }, element);
                }
            }
        }
        Self { map }
    }

    #[must_use]
    #[inline]
    pub fn len(&self) -> usize {
        self.map.len()
    }

    #[must_use]
    #[inline]
    pub fn is_empty(&self) -> bool {
        self.map.is_empty()
    }

    /// Get node value at (row, column).
    #[must_use]
    pub fn value(&self, row: usize, column: usize) -> Option<T> {
        self.map.get(&MatrixIndex { row, column }).copied()
    }

    /// Get mutable reference to node value at (row, column).
    #[must_use]
    pub fn value_mut(&mut self, row: usize, column: usize) -> Option<&mut T> {
        self.map.get_mut(&MatrixIndex { row, column })
    }

    /// If found old node at (row, column), returns old value; otherwise returns None.
    pub fn add_element(&mut self, row: usize, column: usize, value: T) -> Option<T> {
        self.map.insert(MatrixIndex { row, column }, value)
    }

    /// If found node at (row, column), returns value of that node; otherwise returns None.
    pub fn remove_element(&mut self, row: usize, column: usize) -> Option<T> {
        self.map.remove(&MatrixIndex { row, column })
    }
}
}