List of Lists
稀疏矩阵的一种可能表示是列表嵌套 (List of Lists, LIL). 其中一个列表用于表示行, 每行包含三元组列表: 列索引, 值 (非零元素) 和非零元素的地址字段. 为了获得最佳性能, 两个列表都应按升序键的顺序存储.
以下面的矩阵为例:
[ 00304005700000002600 ]
这个矩阵用数组存放, 效果如下图:
这种存储方式的特点是:
- 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
}
}
}