c++ - 为行/列操作设计的稀疏矩阵存储格式？

Question

我正在使用一个需要访问和存储稀疏矩阵中数据的程序。大约 40-60% 的矩阵将是非零的，维度为 14K 到 22K 元素的正方形。

这是我的问题 - 我将执行很多行和列操作。主要是增删改查。我看过大多数现有的众所周知的稀疏矩阵格式(CRS、CCS、COO、 block 格式等)，其中大多数似乎不太接受这些类型的操作。当你开始添加和删除整个行或列时，你不得不将所有元素更新到被操​​作的行/列的任一侧，这是我想尽可能避免的事情(我已经想到了您可能会以这样的方式管理元素，即它们在矩阵中的坐标实际上存储为一对指向公共(public)行或列索引的指针，并通过简单地递增或递减该值来避免手动更新数千个元素)。

那里有这样的东西吗？

Answer 1

我会考虑一个间接层作为交换、插入和删除行和列的有效机制。

这类似于现代操作系统中虚拟内存的管理方式。这只是一个简短的旁白:物理 RAM 地址由 CPU 的 memory management unit 映射。进入线性寻址空间。 MMU 在主机 O/S 的帮助下，将实际物理 RAM 地址映射到每个进程的虚拟地址空间。每个进程中指针和其他对象使用的地址不是真正的 RAM 地址，它们是虚拟的，由硬件 MMU 单元转换为实际的物理 RAM 地址。这就是为什么当系统空间不足时，主机操作系统可以将空闲进程调出到交换文件或分区中，然后稍后将其加载回物理 RAM 的某个完全不同的区域，甚至不需要进程知道发生了什么。

无论如何，回到主题，这将是一种类似的方法。

考虑一个普通的、普通的二维 std::map。这是您的稀疏矩阵:

std::map<size_t, std::map<size_t, value_t>>

第一个 map 的维度或键是行，它为您提供第二个 map ，其维度/键是列，并且最终包含您的值。

这很简单。这里没有什么惊天动地的。但正如您所理解的:移动、交换和插入行和列变得非常困难。

好的，让我们介绍您自己的个性化 MMU:您的 map 管理单元。它几乎可以像硬件 MMU 一样工作:

std::map<size_t, size_t> rows;
std::map<size_t, size_t> columns;

因此，在您的示例中，要查找虚拟行 R、列 C 的值:

1) rows[R] 为您提供“物理”行号。

2) columns[C] 为您提供“物理”列号。

3) 现在，您获取“物理”行号和列号，然后转到您的二维 std::map，并在给定物理行和列的情况下查找您的值。

那么，我们得到了什么？好吧，移动整行或整列现在涉及对 map 管理单元的简单更新。从 rows 或 columns 映射中删除一个值，然后使用不同的键(新的“逻辑”行或列)将其放回原处。 “物理”二维 map 中的值保持不变。

就是这样。移动、交换或插入行成为对您的 mmu 对象的简单操作。

还有两个细节需要注意:

A) 跟踪哪些物理行和列未被使用，并且在添加时可以分配给新的逻辑行和列。

B) 根据您的用例，可能还需要将物理行和列映射回虚拟行号和列号。

这两项都是相当琐碎、简单的任务，可以作为您的家庭作业。