List of Lists

稀疏矩阵的一种可能表示是列表嵌套 (List of Lists, LIL). 其中一个列表用于表示行, 每行包含三元组列表: 列索引, 值 (非零元素) 和非零元素的地址字段. 为了获得最佳性能, 两个列表都应按升序键的顺序存储.

以下面的矩阵为例:

\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(m * n), 其中 m 和 n 是矩阵中非 0 元素的最大行列数, 目前使用的是顺序查找, 效率比较低
• 比较适合存放随时增减节点的矩阵, 插入或者删除元素的成本比较低, 很灵活, 但缓存不友好

算法的实现

为了简化实现, 我们使用了标准库中的双向链表实现.

比较复杂的操作是插入和删除节点, 这个要同时判断行列表和列列表都是有效的.

#![allow(unused)]
#![allow(clippy::linkedlist)]
#![allow(dead_code)]

fn main() {
use std::collections::LinkedList;
use std::fmt;

use crate::traits::IsZero;

#[derive(Debug)]
pub struct ListOfListsSparseMatrix<T: IsZero + fmt::Debug> {
    rows: LinkedList<Row<T>>,
    len: usize,
}

/// Row number in list is ordered ascending.
#[derive(Debug)]
pub struct Row<T: fmt::Debug> {
    row: usize,
    columns: LinkedList<Column<T>>,
}

/// Column number in list is ordered ascending.
#[derive(Debug)]
pub struct Column<T: fmt::Debug> {
    column: usize,
    value: T,
}

impl<T: IsZero + fmt::Debug> ListOfListsSparseMatrix<T> {
    #[must_use]
    pub fn construct<I, I2>(sparse_matrix: I) -> Self
    where
        I: IntoIterator<Item=I2>,
        I2: IntoIterator<Item=T>,
    {
        let mut row_list = LinkedList::new();
        let mut len = 0;

        for (row, rows) in sparse_matrix.into_iter().enumerate() {
            let mut column_list = LinkedList::new();
            for (column, element) in rows.into_iter().enumerate() {
                if element.is_not_zero() {
                    column_list.push_back(Column { column, value: element });
                }
            }
            if !column_list.is_empty() {
                len += column_list.len();
                row_list.push_back(Row { row, columns: column_list });
            }
        }
        Self { rows: row_list, len }
    }

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

    #[must_use]
    #[inline]
    pub const fn is_empty(&self) -> bool {
        self.len == 0
    }

    /// Get node value at (row, column).
    #[must_use]
    pub fn value(&self, row: usize, column: usize) -> Option<T> {
        for row_list in &self.rows {
            if row_list.row == row {
                for column_element in &row_list.columns {
                    if column_element.column == column {
                        return Some(column_element.value);
                    }
                }
                break;
            }
        }
        None
    }

    /// Get mutable reference to node value at (row, column).
    #[must_use]
    pub fn value_mut(&mut self, row: usize, column: usize) -> Option<&mut T> {
        for row_list in &mut self.rows {
            if row_list.row == row {
                for column_element in &mut row_list.columns {
                    if column_element.column == column {
                        return Some(&mut column_element.value);
                    }
                }
                break;
            }
        }
        None
    }

    /// If found old node at (row, column), returns old value; otherwise returns None.
    #[allow(dead_code)]
    pub fn add_element(&self, _ow: usize, _column: usize, _value: T) -> Option<T> {
        // 1. Find the element at (row, column)
        // 2. If no columns_list found in rows, add a new one
        // 3. Add that element to selected column_list
        todo!()
        // 1. if rows list if empty, push to back
        // 2. if front
    }

    /// 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> {
        // 1. Find the element at (row, column)
        // 2. Remove the element in columns list
        // 3. If the columns list is empty, remove it from rows list

        let mut value = None;
        let mut row_index = 0;
        let mut remove_column_list = false;
        for row_list in &mut self.rows {
            row_index += 1;
            if row_list.row == row {
                for column_element in &mut row_list.columns {
                    if column_element.column == column {
                        value = Some(column_element.value);
                        break;
                    }
                }

                if row_list.columns.is_empty() && value.is_some() {
                    remove_column_list = true;
                }

                break;
            }
        }

        if remove_column_list {
            let mut tail = self.rows.split_off(row_index);
            // Remove that columns list.
            tail.pop_front();
            // Then merge together again.
            if !tail.is_empty() {
                self.rows.append(&mut tail);
            }
        }
        if value.is_some() {
            self.len -= 1;
        }
        value
    }
}

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
    }
}
}