密集和稀疏矩阵的高效(时间和空间复杂度)数据结构

Question

我必须读取一个文件,其中存储了一个带有汽车的矩阵(1 = BlueCar,2 = RedCar,0 = Empty).

我需要编写一个算法来以这种方式移动矩阵的汽车:

该文件被读出之前,我不知道矩阵的大小,如果它是密集或稀疏,所以我要实现两个数据结构(一个用于密,一个用于稀疏)和两种算法.

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

由于未知的矩阵大小,我认为将数据存储在堆上.

如果矩阵密集,我想使用类似的东西:

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].

现在问题是为稀疏情况选择的结构,我还必须考虑如何以最简单的方式将汽车移动通过算法:例如,当我评估汽车时,我需要轻松找到,如果在下一个位置(向下或向右)有另一辆车或如果它是空的.

最初我想要定义继承自一般Car对象的BlueCar和RedCar对象.在这个对象中,我可以保存矩阵坐标,然后将它们放入:

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

否则我可以这样做:

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

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

可能这不是最好的方法,所以如何以有效的方式实现稀疏案例呢？(也使用稀疏的独特结构)

Answer 1

为什么不简单地创建一个内存映射为什么不直接在文件上（假设您的数据 0,1,2 存储在文件中的连续字节（或位）中，并且这些字节的位置也代表汽车的坐标）

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

遍历这些行对 L1 缓存是友好的。

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

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

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

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

更新：

我必须使用 openMP 和 MPI 来移动汽车...内存映射也适用于并发线程吗？

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

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

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