数组

数组表示法来存储稀疏矩阵, 就是只在数组中存储里面非零的元素.

数组中每个元素项都包含三部分:

• 该元素在矩阵中的行号
• 该元素在矩阵中的列号
• 该元素的值

比如:

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

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

这种存储方式的特点是:

• Row major 风格
• 数组中元素的排序方法是
  • 从头到尾以行编号递增
  • 相同行编号时, 以列编号递增
  • 即整体上行编号有序递增, 整体上列编号无序, 但局部上列编号递增
• 查找矩阵中某个节点的值时的性能是 O(log(m) * log(n)), 其中 m 和 n 是矩阵中非 0 元素的最大行列数, 因为是有序排列的, 可以用二分查找法
• 比较适合存放固定不变的矩阵, 插入或者删除元素的成本比较高

算法的实现

因为数组支持随机索引, 而且都是有序存储的, 向其中插入和移除元素的操作都比较快.

#![allow(unused)]
fn main() {
use std::{fmt, mem};
use std::cmp::Ordering;

use crate::traits::IsZero;

/// Each element node in the array.
pub struct MatrixElement<T: IsZero> {
    /// Row number of element.
    pub row: usize,
    /// Column number of element.
    pub column: usize,
    /// Value of element.
    pub value: T,
}

/// Store sparse matrix with array.
pub struct ArraySparseMatrix<T: IsZero> {
    vec: Vec<MatrixElement<T>>,
}

impl<T: IsZero> ArraySparseMatrix<T> {
    #[must_use]
    pub fn construct<I, I2>(sparse_matrix: I) -> Self
    where
        I: IntoIterator<Item=I2>,
        I2: IntoIterator<Item=T>,
    {
        let mut vec = Vec::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() {
                    let element = MatrixElement {
                        row,
                        column,
                        value: element,
                    };
                    vec.push(element);
                }
            }
        }
        Self { vec }
    }

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

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

    fn find_element(&self, row: usize, column: usize) -> Result<usize, usize> {
        self.vec.binary_search_by(|node| {
            match node.row.cmp(&row) {
                Ordering::Equal => node.column.cmp(&column),
                order => order
            }
        })
    }

    /// Get node value at (row, column).
    #[must_use]
    pub fn value(&self, row: usize, column: usize) -> Option<T> {
        let result = self.find_element(row, column);
        result.ok().map(|index| self.vec[index].value)
    }

    /// Get mutable reference to node value at (row, column).
    #[must_use]
    pub fn value_mut(&mut self, row: usize, column: usize) -> Option<&mut T> {
        let result = self.find_element(row, column);
        result.ok().map(|index| &mut self.vec[index].value)
    }

    /// If found old node at (row, column), returns old value; otherwise returns None.
    pub fn add_element(&mut self, row: usize, column: usize, mut value: T) -> Option<T> {
        let result = self.find_element(row, column);

pub trait IsZero: Copy {
    fn is_zero(self) -> bool;
    fn is_not_zero(self) -> bool {
        !self.is_zero()
    }
}

macro_rules! impl_is_zero {
    ($($t:ty)*) => {$(
    impl IsZero for $t {
        fn is_zero(self) -> bool {
            self == 0
        }
    }
    )*}
}

impl_is_zero! { i8 i16 i32 i64 i128 isize u8 u16 u32 u64 u128 usize }

impl IsZero for f32 {
    fn is_zero(self) -> bool {
        self == 0.0
    }
}

impl IsZero for f64 {
    fn is_zero(self) -> bool {
        self == 0.0
    }
}
}