稠密矩阵和稀疏矩阵的高效（时间和空间复杂度）数据结构

Question

我需要读取一个文件，其中存储了一辆车的矩阵（1=蓝色汽车，2=红色汽车，0=空）。

我需要编写一个算法来移动矩阵中的汽车：

• 蓝色的向下移动；
• 红色的向右移动；
• 有一个“回合”，蓝色全部移动，然后再轮到红色。

在读取文件之前，我不知道矩阵的大小以及是否密集或稀疏，因此我必须实现两种数据结构（一种用于密集矩阵，另一种用于稀疏矩阵）和两个算法。

我需要达到尽可能的最佳时间和空间复杂度。

由于矩阵大小未知，我考虑将数据存储在堆上。

如果矩阵是密集的，我考虑使用类似以下的东西：

short int** M = new short int*[m];
short int*  M_data = new short int[m*n];

for(int i=0; i< m; ++i) 
{
    M[i] = M_data + i * n;
}

使用这种结构，我可以分配一段连续的内存空间，并且还可以通过M[i][j]轻松访问。

现在问题是要为稀疏情况选择合适的结构，我还必须考虑如何以最简单的方式通过算法移动汽车：例如，当我评估一辆汽车时，我需要轻松找到下一个位置（向下或向右）是否有另一辆汽车或者是空的。

起初，我想定义BlueCar和RedCar对象，它们从通用Car对象继承而来。在这些对象中，我可以保存矩阵坐标，然后将它们放入：

std::vector<BluCar> sparseBlu;
std::vector<RedCar> sparseRed;

否则我可以这样做：

vector< tuple< row, column, value >> sparseMatrix

但是仍然存在找到下一个位置所在的问题。

可能这不是最好的方法，那么如何以高效的方式实现稀疏情况？（同时使用稀疏的唯一结构）

- rh0x

---

这个问题其实是一个经过深入研究的领域，目的是保持访问速度（以及减少缓存未命中），同时控制内存开销。可以参考这里的各种稀疏存储方案。但实际上这取决于你的矩阵，比如它是对称的吗？带宽是多少？是否可以重新排序等等。其中一种比较流行、易于编码且性能优秀的方法是Yale存储方案，也被称为“真正的稀疏存储方案”。 - Cory Kramer

@CoryKramer 这些元素似乎代表着汽车的位置。汽车可以移动。对称性似乎不太可能... - user2672165

我会避免使用多态方法，而是考虑两个（可能已排序的）向量，每个向量只包含坐标。 - Galik

@UmNyobe 我只有在读取文件时才知道矩阵的大小，所以在运行时。 - rh0x

不完全正确。与排序向量相比，map对插入/删除更加优化，但是堆上的情况是一样的，不像向量那样在内存中是连续的。如果您只有几辆车，则无需对向量进行排序以进行快速查找。可以简单地使用map开始。您还可以简要查看空间索引。 - user2672165

Answer 1

为什么不直接在文件上创建内存映射呢？（假设您的数据0、1、2以连续的字节（或位）存储在文件中，并且这些字节的位置也表示汽车的坐标）

这样，您就不需要分配额外的内存并读入所有数据，数据可以通过M[i][j]简单高效地访问。

按行遍历对L1缓存友好。

如果数据非常稀疏，您可以扫描数据一次并在内存中保留空区域/块的列表（只需要存储起始位置和大小），然后在进一步运行时跳过它们（并在需要时进行调整）。

使用内存映射，只有频繁访问的页面会保留在内存中。这意味着一旦您扫描了空区域，内存将仅为频繁访问的非空区域分配（所有这些都将由内核自动完成-无需自己跟踪）。

另一个好处是您直接访问操作系统磁盘缓存。因此，无需在内核空间和用户空间之间复制和移动数据。

为进一步优化空间和内存使用，可以将汽车以2位的形式存储在文件中。

更新：

“我必须使用openMP和MPI移动汽车...并发线程是否也能使用内存映射？”

您当然可以使用多线程，但不确定openMP是否是最佳解决方案，因为如果同时处理数据的不同部分，则可能需要检查某些重叠区域（即汽车可能从一个块移动到另一个块）。

或者您可以让线程处理块的中间部分，然后启动其他线程来处理边界（对于红色汽车，这将是一个字节，对于蓝色汽车则是一整行）。

您还需要锁定机制来调整稀疏区域列表。我认为最好的方法是启动单独的线程（当然取决于数据的大小）。

- Danny_ds

---

我没有在下一步中指定我将使用openMP和MPI移动汽车...内存映射是否也适用于并发线程？ - rh0x

谢谢您的建议...它可以通过一个实现解决密集和稀疏情况，但即使您说“简单”，我也找不到有用的网络示例来说明如何做到这一点。唯一的一个是这个：http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n2044.html#ClassFileMappingMembers （我是C++新手） - rh0x

@rh0x - 实际上，两种情况只需要一种实现。使用内存映射，您可以在文件上创建“映射视图”，一旦创建，就可以像访问内存一样访问数据（使用指针或[]等）。- 对于Linux，请查看mmap()，对于Windows，请查看CreateFileMapping() - 它并不像看起来那么难，而且可以非常强大/快速。 - Danny_ds

我必须使用嵌套的for-for循环来访问矩阵单元，因此我认为可以使用openMP。例如，对于红色汽车，我将有一个嵌套的for(row)-for(col)，对于蓝色汽车，我将有一个嵌套的for(col)-for(row)。此外，我在这里找到了一个使用openMP + mmap()的示例：http://beej.us/blog/data/parallel-programming-openmp/（页面底部有源代码）。 - rh0x

1. 是的，每辆汽车都是文件中的一个字节，并且它们以逗号分隔。
2. 这些文件小于1GB。

- rh0x

Answer 2

在一个相似的任务中，我只是使用了压缩行存储。

压缩行和列（下一节）存储格式是最通用的：它们对矩阵的稀疏结构绝对没有任何假设，并且不存储任何不必要的元素。另一方面，它们不是非常高效，在矩阵-向量乘积或预处理器求解中，每个标量操作都需要间接寻址步骤。

你需要更具体地说明时间和空间复杂度要求。如果只进行简单的矩阵运算，则CSR需要额外的索引步骤，但这只是一个小的开销。 已经有现成的C++实现可以在线获取。

- Cloud

---

这对于只读数据可能很有趣，但是如果涉及到删除/插入操作（例如移动汽车），性能会如何呢？ - Danny_ds

从维基百科文章中可以看出：这种格式对于算术运算、行切片和矩阵向量积非常高效。 因此，简单的逻辑操作（例如：设置/取消标志位/位域/状态）也会相对较快。此外，存储节省也是相当可观的。 - Cloud